Algebra Seminar talk

2011-11-04
Martin Goldstern
Der Satz von Nash-Williams

Abstract:
Der Satz von Ramsey besagt, dass es zu jeder Partition von [N]^k (=Menge der k-elementigen Teilmengen der natürlichen Zahlen) in endlich viele Klassen eine unendliche "homogene" Menge gibt, d.h., eine Menge A, deren k-elementige Teilmengen alle in derselben Klasse liegen.


Eine Verallgemeinerung der k-elementigen Teilmengen ist die Barriere: Sei X eine unendliche Menge; eine "Barriere" von X ist eine Familie F von endlichen Teilmengen von X mit der Eigenschaft, dass es zu jeder unendlichen Teilmenge von X genau einen Anfangsabschnitt in F gibt.


Satz von Nash-Williams: Sei F eine Barriere einer unendlichen Menge

A, und sei F in endlich viele Teile partitioniert. Dann gibt es unendliche Teilmenge A' und eine Unterbarriere F' (von A'), die ganz in einer Partitionsklasse liegt.

Ich werde einen Beweis dieses Satzes skizzieren, und auf Anwendungen in der Theorie der "better quasi orders" hinweisen.