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.
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:
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.
Der Ursprungsartikel stammt von der deutschsprachigen Wiki pedia (siehe oben: "Original Artikel & Autoren Liste").
Der Text steht unter der GNU Freie Dokumentation Lizenz. |
Webtipps: Reise Infos