Fundierte Menge - LinkFang.de





Fundierte Menge


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

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

  1. P(x) ist wahr für alle minimalen Elemente von X.
  2. Ist x ein Element von X und P(y) wahr für alle y<x, dann ist auch P(x) wahr.

Dann ist P(x) wahr für alle Elemente x aus X.

Beispiele

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:

ab, falls a ein Teiler von b ist
  • die Menge N×N aller Paare natürlicher Zahlen mit der Ordnung
(m,n)≤(a,b), falls ma und nb
  • die Menge der endlichen Wörter über einem vorgegebenen Alphabet mit der Ordnung
st, falls s eine Teilzeichenkette von t ist
st, falls s ein Teilausdruck von t ist
  • jede Menge von Mengen mit der Ordnung
AB, falls A ist ein Element von B (wirklich Element, nicht Teilmenge!)

Länge absteigender Ketten

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, ab > 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 nb)

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.

Siehe auch


Kategorien: Ordnungstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Fundierte Menge (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.