Wohlfundierte Relation

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

In der Mathematik heißt eine auf einer Menge definierte zweistellige Relation wohlfundiert, wenn es keine unendlichen Ketten in dieser Relation gibt, d. h. wenn es keine unendliche Folge von Elementen in mit für alle gibt. Insbesondere enthält eine wohlfundierte Relation keine Zyklen.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

Wohlfundierte Relationen sind stets irreflexiv.

Unter Verwendung des Satzes vom ausgeschlossenen Dritten und dem beschränkten Auswahlaxiom sind folgende Aussagen über äquivalent:

  • ist wohlfundiert.
  • Die transitive Hülle von ist wohlfundiert.
  • Jede nichtleere Teilmenge von hat ein minimales Element, d.h. ein , für das es kein gibt mit .
  • Wohlfundierte Induktion über ist ein gültiges Prinzip, um Aussagen über alle Elemente von zu beweisen.

Beispiele[Bearbeiten | Quelltext bearbeiten]

  • Die Vorgängerrelation auf , definiert durch , ist wohlfundiert. Das dazugehörige Induktionsprinzip ist das der vollständigen Induktion. Ihre transitive Hülle ist das übliche . Das dazugehörige Induktionsprinzip heißt starke Induktion; mit klassischer Logik äquivalent zum unendlichen Abstieg.
  • Alle wohlfundierten Ordnungen und alle Wohlordnungen sind wohlfundierte Relationen, wenn man nur den irreflexiven Teil betrachtet. Die Umkehrungen gelten nicht, da wohlfundierte Relationen nicht transitiv sein müssen.
  • Ein Modell der Zermelo-Fraenkel-Mengenlehre definiert eine Relation , die aufgrund des Fundierungsaxioms wohlfundiert ist. Das dazugehörige Induktionsprinzip heißt Epsilon-Induktion.

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Literatur[Bearbeiten | Quelltext bearbeiten]

  • Paul Taylor: Practical Foundations of Mathematics, Cambridge University Press, 1999, ISBN 0 521 63107 6, Seiten 97ff