Wohlfundierte Relation

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

Eigenschaften

Wohlfundierte Relationen sind stets irreflexiv.
Wohlfundierte Relationen sind azyklisch.
Ist <math>R\subseteq M \times M</math> wohlfundiert und <math>S \subseteq R</math>, so ist <math>S</math> wohlfundiert.

Unter Verwendung des Satzes vom ausgeschlossenen Dritten und dem Axiom der abhängigen Auswahl sind folgende Aussagen über <math>\mathord{\prec} \subseteq M\times M</math> äquivalent:

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

Beispiele

Die Vorgängerrelation auf <math>\mathbb N</math>, definiert durch <math>n \prec m :\Longleftrightarrow n+1=m</math>, ist wohlfundiert. Das zu <math>\prec </math> gehörige Induktionsprinzip ist das der vollständigen Induktion. Ihre transitive Hülle ist die übliche {{#if:trim|<math><</math>-Relation}} mit dem zugehörigen Induktionsprinzip der starken (vollständigen) Induktion, mit klassischer Logik äquivalent zum unendlichen Abstieg.
Die Relation <math>{\prec} \subseteq \mathbb N \times \mathbb N</math>, definiert durch <math>n \prec m :\Longleftrightarrow n\neq 0 \land (m = 0 \lor \exists p\text{ prim}.\, p\cdot n=m)</math>, ist wohlfundiert, ebenso dieselbe Relation eingeschränkt auf <math>\mathbb N\setminus\{1\}</math>, welche viele minimale Elemente hat. Die transitive Hülle von <math>\prec</math> ist die (echte) Teilerrelation auf <math>\mathbb N</math>.
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 <math>V</math> der Zermelo-Fraenkel-Mengenlehre definiert eine Relation <math>\epsilon\subseteq V\times V</math>, die aufgrund des Fundierungsaxioms wohlfundiert ist. Das dazugehörige Induktionsprinzip heißt Epsilon-Induktion.
Die Adjazenzrelation eines endlichen gerichteten azyklischen Graphen ist wohlfundiert.

Beziehungen zwischen den Definitionen

Mit <math>\mathord{\prec} \subseteq M \times M</math> sind folgende Definitionen dafür möglich, dass <math>\prec</math> wohlfundiert ist:

<math>\prec</math> ist klassisch wohlfundiert (bewohnte Teilmengen von <math>M</math> haben ein <math>\prec</math>-minimales Element): <math>\forall X \subseteq M.\, \forall x_0 \in X.\, \exists x\in X.\, \forall y\in X.\, y \not\prec x</math>.
<math>\prec</math> ist wohlfundiert (wohlfundierte Induktion ist gültig): <math>\forall X\subseteq M.\, (\forall x \in M.\, (\forall y \in M.\, y \prec x \to y \in X) \to x \in X) \to \forall x \in M.\, x \in X</math>.
Bezüglich <math>\prec</math> gibt es keinen unendlichen Abstieg (relational formuliert): <math>\lnot\exists X \subseteq M.\, \exists x_0\in X.\, \forall x\in X.\, \exists y\in X.\, y \prec x</math>.
Bezüglich <math>\prec</math> gibt es keinen unendlichen Abstieg: <math>\lnot\exists f\in M^\N.\, \forall n\in\N.\, f(n+1)\prec f(n)</math>.

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

Konstruktiv kann man jedes Glied der Implikationskette <math>(1)\implies(2)\implies(3)\implies(4)</math> beweisen, die jeweils andere Richtung aber im Allgemeinen nicht.

<math>(4)\implies(3)</math> erfordert eine Instanz des Axioms der abhängigen Auswahl.

Für <math>(3)\implies(1)</math> wird klassische Logik benötigt, und zwar in einem sehr starken Sinn: Aus der Existenz einer klassisch wohlfundierten Relation <math>\prec</math> und Elementen <math>x,y</math> mit <math>x\prec y</math> 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 <math>(3)\implies(1)</math> klassische Logik.

Oft anzutreffen ist eine Variante von (2), die sich folgendermaßen ergibt: Offensichtlich ist die Formel in (2) äquivalent zu

<math>\forall x \in M.\, \forall X\subseteq M.\, (\forall x \in M.\, (\forall y \in M.\, y \prec x \to y \in X) \to x \in X) \to x \in X,</math>

und dies wiederum offensichtlich äquivalent zu

<math>\forall x \in M.\, x \in \bigcap \{X\subseteq M \mid \forall x \in M.\, (\forall y \in M.\, y \prec x \to y \in X) \to x \in X\}.</math>

Mit der Abkürzung <math>\mathrm{Acc}_\prec</math> (“accessible”) für den Mengendurchschnitt, dessen Elemente „<math>\prec</math>-zugänglich“ heißen, hat man dann: <math>{\prec}\subseteq M \times M</math> ist wohlfundiert genau dann, wenn alle Elemente von <math>M</math> <math>\prec</math>-zugänglich sind, also <ref> {{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}| |}}}}{{#if:|{{{autor}}}: }}{{#if:|{{#if:Rocq Core Library, Library Corelib.Init.Wf|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=Rocq Core Library, Library Corelib.Init.Wf}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=Rocq Core Library, Library Corelib.Init.Wf}}}}|[{{#invoke:URLutil|getNormalized|1=https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=Rocq Core Library, Library Corelib.Init.Wf}}}}]}}{{#if:| ({{{format}}}{{#if:{{#if: 2025-08-01 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}

          | )
          | {{#if:{{#ifeq:de|de||{{#if:|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded}}%7C%7C URL ungültig}}}}{{#if:Rocq Core Library, Library Corelib.Init.Wf|{{#if:{{#invoke:WLink|isValidLinktext|1=Rocq Core Library, Library Corelib.Init.Wf|lines=0}}|| Linktext ungültig}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: | {{{hrsg}}}{{#if: |,|{{#if: 2025-08-01 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | {{#if:{{#invoke:DateTime|format|{{{datum}}}|noerror=1}}
            |{{#invoke:DateTime|format|{{{datum}}}|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum={{{datum}}}|class=Zitationswartung}} }}{{#if: |,|{{#if: 2025-08-01 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2025-08-01 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}|{{{archiv-datum}}}{{#if:1336435||(?)}}}}}}{{#if: 2025-08-01|;}}}}{{#if: 2025-08-01| {{#if:{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2025-08-01 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2025-08-01|class=Zitationswartung}} }} {{#invoke:DateTime|format|2025-08-01|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}}{{#if:{{#ifeq:de|de||{{#if:|1}}}}|{{#if:{{#if: 2025-08-01 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:de|de|de}}|de||
          {{#invoke:Multilingual|format|{{{sprache}}}|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:de|de|de}}|de||, }}{{{kommentar}}}}})}}{{#if: {{#if: 2025-08-01 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}|{{#if: |: {{
 #if: 
 | „{{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}“
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if:

   |  (<templatestyles src="Person/styles.css" />{{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}}

   | {{#if: 
       | {{#if: {{{zitat}}}
           | Vorlage:": Text= und 1= gleichzeitig, bzw. Pipe zu viel }} }}
   | Vorlage:": Text= fehlt }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | Vorlage:": Ungültiger Wert: ref=
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded
      | {{#if:{{#invoke:URLutil|isWebURL|https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded
       | {{#if:{{#invoke:URLutil|isWebURL|https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive (T)){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
    }}{{#if: https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded
      | {{#if:{{#invoke:URLutil|isWebURL|https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
      | {{#if: 
           |  Fehler bei Vorlage:Toter Link: 'text' angegeben, aber 'url'' fehlt.{{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. (T).)  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   =  @@@
         |preview  = 1
       }}{{#if: https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded
       | {{#if:{{#invoke:URLutil|isWebURL|https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded}}
          ||  Fehler bei Vorlage:Toter Link: Wert in 'url' ist ungültig.{{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             ||  Fehler bei Vorlage:Toter Link: Wert in 'date' ist ungültig.{{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=   Fehler bei Vorlage:Toter Link: Wert in 'botlauf' ist ungültig.{{#if:  ||  }}
    }}[https://rocq-prover.org/doc/v9.0/corelib/Corelib.Init.Wf.html#well_founded }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}} {{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }} </ref>

<math>\forall x \in M.\, x \in \mathrm{Acc}_\prec</math>.

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 <math>M</math> eine Menge, <math>\mathord{\prec} \subseteq M \times M</math> eine klassisch wohlfundierte Relation darauf, <math>y,z \in M</math> und <math>y \prec z</math>. Zu zeigen ist, dass für beliebige Aussagen <math>P</math> gilt: <math>P \lor \lnot P</math>. Dafür sei <math>P</math> beliebig. Die Menge <math>X := \{ x \in M \mid P \lor x = z\}</math> ist nun eine Teilmenge von <math>M</math> und bewohnt, da sie <math>z</math> enthält. Es gibt also ein <math>x \in X</math> mit <math>\forall y\in X.\, y \not \prec x</math>. Aus <math>x \in X</math> ergeben sich zwei Fälle:

<math>P</math>. In dem Fall gilt <math>P</math>.
<math>x = z</math>. In dem Fall gilt <math>\lnot P</math>, denn angenommen, <math>P</math> gelte, dann ist <math>y \in X</math> und somit <math>y \not\prec x = z</math>, was <math>y \prec z</math> widerspricht.

In beiden Fällen folgt <math>P \lor \lnot P</math>. <math>\square</math>

Siehe auch

Literatur

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

Einzelnachweise