Fundierte Menge
aus Wikipedia, der freien Enzyklopädie
Eine fundierte Menge (auch fundierte Ordnung, terminierende Ordnung, noethersche Ordnung) ist eine halbgeordnete Menge, die keine unendlichen absteigenden Ketten enthält.
Äquivalent dazu ist, daß eine partielle Ordnung fundiert heißt, wenn jede nicht-leere Teilmenge S von X (mindestens) ein minimales Element m enthält, d.h. 
.
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, die noethersche 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, falls a ein Teiler von b ist
- die Menge N×N aller Paare natürlicher Zahlen mit der Ordnung
-
- (m,n)≤(a,b), falls m≤a und n≤b
- die Menge der endlichen Zeichenketten über einem vorgegebenen Alphabet mit der Ordnung
-
- s≤t, falls s eine Teilzeichenkette von t ist
- die Menge der regulären Ausdrücke über einem vorgegebenen Alphabet mit der Ordnung
-
- s≤t, falls s ein Teilausdruck von t ist
- jede Menge von Mengen mit der Ordnung
-
- A≤B, falls 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), falls (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.
