|
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.
Beispiele fundierter Mengen:
- jede wohlgeordnete Menge
- jede endliche halbgeordnete Menge
Beispiele fundierter Mengen die nicht totalgeordnet sind:
- 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!)
Beispiele von nicht fundierten Mengen:
- die ganzen Zahlen, rationalen Zahlen, reellen Zahlen in ihrer
natürlichen Anordnung
- die Potenzmenge einer unendlichen Menge mit der Teilmengenbeziehung als Ordnung
Ist (X,<=) eine fundierte Menge und x aus X, dann sind die bei x beginnenden
absteigenden Ketten allesamt endlich, aber ihre Länge muss nicht beschränkt sein. Betrachte z.B. die Menge
- X := {(a,b) | a,b aus N0, a >=
b > 0 oder a=b=0}
(wobei N0={0, 1, 2, 3, ...}) mit der Ordnung
- (m,n)<=(a,b) gdw. (a,b)=(0,0)
oder (m=a und n>=b)
Darin ist z.B. (0,0)>(4,1)>(4,2)>(4,3)>(4,4) und (0,0)>(2,1)>(2,2). X ist fundiert, aber es gibt
bei (0,0) beginnende absteigende Ketten beliebiger (endlicher) Länge.
|
