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 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[Bearbeiten]