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

Fundierte Mengen erlauben die Anwendung der noetherschen Induktion, einer Version der transfiniten Induktion: Sei   eine Eigenschaft von Elementen einer unter einer Ordnungsrelation   fundierten Menge   und sei die folgende Aussage wahr:

Wenn   ein Element von   ist und   für alle   wahr ist, dann ist auch   wahr.

Dann ist   wahr für alle Elemente   aus  .

Verwendung in der Informatik

Bearbeiten

Siehe auch: Termersetzungssystem#Terminierung

Terminiertheit ist ein zentrales Konzept in der theoretischen Informatik. Obige Begriffe werden dazu von Ordnungen auf homogene Relationen   abgeschwächt, wobei   etwa den Schritt einer Berechnung repräsentiert. In diesem Zusammenhang ist ein Element   einer Teilmenge    -minimal, wenn für alle   mit   folgt  .[1] Neben der Terminiertheit von Algorithmen kann vermittels der Noethersche Induktion dann deren Eigenschaften nachgewiesen werden.

Beispiele

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
  genau dann, wenn   ein Teiler von   ist
  genau dann, wenn  
  • die Menge   aller Paare natürlicher Zahlen mit der Ordnung
  genau dann, wenn   und  
  • die Menge der endlichen Wörter über einem vorgegebenen Alphabet mit der Ordnung
  genau dann, wenn   eine Teilzeichenkette von   ist
  genau dann, wenn   ein Teilausdruck von   ist
  • jede Menge von Mengen mit der Ordnung
  genau dann, wenn   ist ein Element von   (wirklich Element, nicht Teilmenge!)

Länge absteigender Ketten

Bearbeiten

Ist   eine fundierte Menge und  , 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

  genau dann, wenn   oder  

Darin sind z. B.   und  .   ist fundiert, aber es gibt bei   beginnende absteigende Ketten beliebiger (endlicher) Länge.

Siehe auch

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Wolfgang Wechler: Universal Algebra for Computer Scientists. Springer-Verlag, Berlin 1992, ISBN 3-540-54280-9, S. 35–39.