Wohlfundierte Relation

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

Ein Element $a\in M$, für das kein Element $a^\prime$ existiert mit $(a,a^\prime)\in R$ nennt man eine Normalform bezüglich R oder R-Normalform. Ist $(a,a^\prime)\in R$ und $a^\prime$ eine R-Normalform, dann nennt man $a^\prime$ eine R-Normalform "von a".

Ist eine wohlfundierte Relation konfluent, so hat jedes Element $a\in M$ eine eindeutige R-Normalform $a^\prime$. Man sagt dann auch $a^\prime$ ist "die" R-Normalform von a und schreibt $a^\prime = a\downarrow_R$

Alle wohlfundierten Ordnungen und alle Wohlordnungen sind wohlfundierte Relationen.

Siehe auch

• Wohlfundierte Induktion
• Abstiegsfunktion