Fundierte Menge

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Mathematik ist eine fundierte Menge (auch wohlfundierte Menge, fundierte Ordnung, terminierende Ordnung, noethersche Ordnung) eine halbgeordnete Menge, die keine unendlichen echt absteigenden Ketten enthält. Äquivalent dazu heißt eine halbgeordnete Menge fundiert, wenn jede nichtleere Teilmenge mindestens ein minimales Element enthält.

Alle wohlgeordneten Mengen sind fundiert, weil in einer wohlgeordneten Menge jede nichtleere Teilmenge ein kleinstes Element haben muss und das kleinste Element einer Menge immer auch minimal ist. Anders als wohlgeordnete Mengen brauchen fundierte Mengen nicht totalgeordnet zu sein. Alle total geordneten fundierten Mengen sind wohlgeordnet.

Noethersche Induktion[Bearbeiten | Quelltext bearbeiten]

Fundierte Mengen erlauben die Anwendung der noetherschen Induktion, einer Version der transfiniten Induktion: Ist eine Eigenschaft von Elementen einer unter einer Ordnungsrelation fundierten Menge , und sind die folgenden Aussagen wahr:

  1. ist wahr für alle minimalen Elemente von .
  2. Ist ein Element von und wahr für alle , dann ist auch wahr.

Dann ist wahr für alle Elemente aus .

Beispiele[Bearbeiten | Quelltext bearbeiten]

Die ganzen Zahlen, die rationalen Zahlen und die reellen Zahlen enthalten in ihrer natürlichen Anordnung jeweils unendliche absteigende Ketten und sind somit nicht fundiert.

Die Potenzmenge einer Menge mit der Teilmengenbeziehung als Ordnung ist genau dann fundiert, wenn die Menge endlich ist. Alle endlichen halbgeordneten Mengen sind fundiert, weil endliche Mengen nur endliche Ketten haben können.

Die folgenden Mengen sind fundiert, aber nicht totalgeordnet:

  • die natürlichen Zahlen mit der Ordnung
, falls ein Teiler von ist
  • die Menge aller Paare natürlicher Zahlen mit der Ordnung
, falls und
  • die Menge der endlichen Wörter über einem vorgegebenen Alphabet mit der Ordnung
, falls eine Teilzeichenkette von ist
, falls ein Teilausdruck von ist
  • jede Menge von Mengen mit der Ordnung
, falls ist ein Element von (wirklich Element, nicht Teilmenge!)

Länge absteigender Ketten[Bearbeiten | Quelltext bearbeiten]

Ist eine fundierte Menge und aus , dann sind die bei beginnenden absteigenden Ketten allesamt endlich, aber ihre Länge muss nicht beschränkt sein. Betrachte z. B. die Menge

(wobei ) mit der Ordnung

, falls oder

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

Siehe auch[Bearbeiten | Quelltext bearbeiten]