Wohlfundierte Relation

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


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Wohlfundierte Induktion — Die wohlfundierte Induktion ist eine formale mathematische Beweismethodik, welche auch in der Informatik (zum Beispiel in funktionalen Programmiersprachen) Anwendung findet. Das Prinzip lautet: Zeige, dass eine Aussage A für alle Elemente wahr… …   Deutsch Wikipedia

  • Wohlfundiert — 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 von Elementen in M mit für alle i gibt. Insbesondere… …   Deutsch Wikipedia

  • Mostowski-Kollaps — Der Mostowski Kollaps (auch: Mostowski scher Isomorphiesatz) ist ein Satz aus der Mengenlehre, der zuerst 1949 von dem polnischen Mathematiker Andrzej Mostowski formuliert wurde. Er ist vor allem bei der Konstruktion von Modellen ein wichtiges… …   Deutsch Wikipedia

  • Abstiegsfunktion — Eine Abstiegsfunktion ist in der Mathematik und in der Informatik eine Funktion, mit der nachgewiesen werden kann, dass eine Rekursion terminiert. Inhaltsverzeichnis 1 Prinzip 2 Beispiele 2.1 Mathematik …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”