Fundierte Menge
Eine fundierte Menge ist eine halbgeordnete Menge, die keine unendlichen absteigenden Ketten enthält. Eine halbgeordnete Menge ist genau dann fundiert, wenn jede nichtleere Teilmenge ein minimales Element enthält. Ist die Ordnung total, dann ist die Menge wohlgeordnet (jede nichtleere Teilmenge enthält ein kleinstes Element).Ein Grund, warum fundierte Mengen interessant sind, ist die Anwendbarkeit einer Version der transfiniten Induktion: Ist (X,<=) eine fundierte Menge, P eine Eigenschaft 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, folgendes zu beweisen:
- P(x) ist wahr für alle minimalen Elemente von X.
- Ist x ein Element von X und P(y) wahr für alle y<x, dann ist auch P(x) wahr.
- jede wohlgeordnete Menge
- jede endliche halbgeordnete Menge
- 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 Ordnung (m,n)<=(a,b) gdw. m<=a und n<=b
- die Menge der endlichen Zeichenketten über einem vorgegebenen Alphabet mit der Ordnung s<=t gdw. s ist eine Teilzeichenkette von t
- die Menge der regulären Ausdrücke über einem vorgegebenen Alphabet mit der Ordnung s<=t gdw. s ist ein Teilausdruck von t
- jede Menge von Mengen mit der Ordnung A<=B gdw. A ist ein Element von B (wirklich Element, nicht Teilmenge!)
- die ganzen Zahlen, rationalen Zahlen, reellen Zahlen in ihrer natürlichen Anordnung
- die Potenzmenge einer unendlichen Menge mit der Teilmengenbeziehung als Ordnung
- X := {(a,b) | a,b aus N0, a >= b > 0 oder a=b=0}
- (m,n)<=(a,b) gdw. (a,b)=(0,0) oder (m=a und n>=b)