Wohlfundierte Relation

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

In der Mathematik heißt eine auf einer Menge M definierte zweistellige Relation \prec wohlfundiert, wenn es keine unendlichen Ketten in dieser Relation gibt, d. h. wenn es keine unendliche Folge a_0, a_1, a_2, a_3, \dots von Elementen in M mit a_{i+1} \prec a_i für alle i gibt. Insbesondere enthält eine wohlfundierte Relation keine Zyklen.

Eigenschaften[Bearbeiten]

Wohlfundierte Relationen sind stets irreflexiv.

Unter Verwendung des Satzes vom ausgeschlossenen Dritten und dem beschränkten Auswahlaxiom sind folgende Aussagen über {\prec}\subseteq M\times M äquivalent:

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

Beispiele[Bearbeiten]

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

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