Fundierte Menge

Ein Grund warum fundierte Mengen interessant ist die Anwendbarkeit einer Version der transfiniten Induktion : Ist ( X <=) eine fundierte Menge P eine von Elementen aus X und man möchte zeigen dass P( x ) für alle Elemente x aus X wahr ist dann kann man versuchen zu beweisen:

1. P( x ) ist wahr für alle minimalen Elemente X .
2. Ist x ein Element von X und P( y ) wahr für alle y < x dann ist auch P( x ) wahr.

Beispiele fundierter Mengen:

• jede wohlgeordnete Menge
• jede endliche halbgeordnete Menge

Beispiele fundierter Mengen die nicht totalgeordnet

• die natürlichen Zahlen N ={1 2 3 ...} mit der Ordnung a <= b gdw. a teilt b
• die Menge N × N aller Paare natürlicher Zahlen mit der ( m n )<=( a b ) gdw. m <= a und n <= b
• die Menge der endlichen Zeichenketten über vorgegebenen Alphabet mit der Ordnung s <= t gdw. s ist eine Teilzeichenkette von t
• die Menge der regulären Ausdrücke über vorgegebenen Alphabet mit der Ordnung s <= t gdw. s ist ein Teilausdruck von t
• jede Menge von Mengen mit der A <= B gdw. A ist ein Element von B (wirklich Element nicht Teilmenge!)

Beispiele von nicht fundierten Mengen:

• die ganzen Zahlen rationalen Zahlen reellen Zahlen in ihrer natürlichen Anordnung
• die Potenzmenge einer unendlichen Menge mit Teilmengenbeziehung als Ordnung

Ist ( X <=) eine fundierte Menge und x aus X dann sind die bei x beginnenden absteigenden Ketten allesamt endlich aber Länge muss nicht beschränkt sein. Betrachte z.B. Menge

X := {( a b ) | a b aus N ₀ a >= b > 0 oder a = b =0}

(wobei N ₀ ={0 1 2 3 ...}) mit der

( m n )<=( a b ) gdw. ( a b )=(0 0) oder ( m = a und n >= b )

Darin ist z.B. (0 0)>(4 1)>(4 3)>(4 4) und (0 0)>(2 1)>(2 2). X ist fundiert aber es gibt bei 0) beginnende absteigende Ketten beliebiger (endlicher) Länge.

Bücher zum Thema Fundierte Menge

Dieser Artikel von Wikipedia unterliegt der GNU FDL.