Wohlfundierte Relation

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

Wohlfundierte Relationen sind stets irreflexiv.

Unter Verwendung des Satzes vom ausgeschlossenen Dritten und dem Axiom der abhängigen Auswahl sind folgende Aussagen über äquivalent:

  • ist wohlfundiert.
  • Die transitive Hülle von ist wohlfundiert.
  • Jede nichtleere Teilmenge 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

Beziehungen zwischen den Definitionen

Mit sind folgende Definitionen dafür möglich, dass wohlfundiert ist:

  1. ist klassisch wohlfundiert (bewohnte Teilmengen von haben ein -minimales Element): .
  2. ist wohlfundiert (wohlfundierte Induktion ist gültig): .
  3. Bezüglich gibt es keinen unendlichen Abstieg (relational formuliert): .
  4. Bezüglich gibt es keinen unendlichen Abstieg: .

(1) und (3) sind offenkundig äquivalent zueinander, wenn klassische Logik verwendet wird.

Konstruktiv kann man jedes Glied der Implikationskette beweisen, die jeweils andere Richtung aber im Allgemeinen nicht.

erfordert eine Instanz des Axioms der abhängigen Auswahl.

Für wird klassische Logik benötigt, und zwar in einem sehr starken Sinn: Aus der Existenz einer klassisch wohlfundierten Relation und Elementen mit folgt bereits der Satz vom ausgeschlossenen Dritten (siehe unten). In diesem Sinn ist die klassische Wohlfundiertheit (1) zu stark für konstruktive Mathematik. Da es aber bewohnte, nach (2) wohlfundierte Relationen üblicherweise gibt, impliziert klassische Logik.

Klassische Wohlfundiertheit impliziert den Satz von ausgeschlossenen Dritten

Es wird gezeigt, dass aus der Existenz einer bewohnten, klassisch wohlfundierten Relation der Satz vom ausgeschlossenen Dritten folgt. Es seien eine Menge, eine klassisch wohlfundierte Relation darauf, und . Zu zeigen ist, dass für beliebige Aussagen gilt: . Dafür sei beliebig. Die Menge ist nun eine Teilmenge von und bewohnt, da sie enthält. Es gibt also ein mit . Aus ergeben sich zwei Fälle:

  1. . In dem Fall gilt .
  2. . In dem Fall gilt , denn angenommen, gelte, ist und somit , was widerspricht.

In beiden Fällen folgt .

Siehe auch

Literatur

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