Inhalt

Eigenschaften

Reflexiv

Reflexiv heissen diejenigen Relationen, für die die Pärchen (a,a) in der Relation sind. Das (a) ist ein Element aus der Menge in der die Relation definiert ist.

Symmetrie

Symmetrische Relationen besizten sowohl das Pärchen (a,b) sowie das vertauschte Pärchen (b,a). a und b sind Elementeder Menge in der die Relation definiert ist.

Antisymmetrie

Antisymmetrische Relationen besizten sowohl das Pärchen (a,b) sowie das vertauschte Pärchen (b,a), wobei a = b ist. a und b sind Elemente der Menge in der die Relation definiert ist.

Transitivität

Eine Relationen ist Transitiv, wenn sich aus dem Pärchen (a,b) und dem Pärchen (b,c) ein drittes Pärchen (a,c) ergibt. a,b und c sind Elemente der Menge in der die Relation definiert ist.

Äquivalenzrelationen

Um nachzuweisen ob es sich um eine Äquivalenzrelation handelt, muss man Reflexivität, Transitivität und Symmetrie nachweisen.Als erstes sollte man schauen, ob es ein Gegenbeispiel für eines der genannten Eigenschaften gibt. Das würde reichen um dieVermutung zu wiederlegen. An sonsten müssen alle drei Eigenschaften aufgezeigt werden.

Ordnungsrelation

Eine Relation die reflexiv, antisymetisch und transitiv ist, nennt man Ordnungsrelation.

Binäre Relationen

Eine binäre Relation zwichen zwei Mengen A und B ist eine Teilmenge fi des kartesischen Produktes (siehe Mengen) von A und B. Man schreibt statt (a,b) element fi auch a fi b.

Wohlfundierte Relationen

Gegeben sei eine Menge M .
Eine binäre Relation

$\succ\subseteq M\times M$

heisst wohlfundiert wenn gilt: BREs gibt keine unendlichen Folgen

$x_{1},x_{2},x_{3} ,  x_{n}\in M$

mit

$x_{1}\succ x_{2}\succ x_{3}\succ...$

(binäre Relation). Das Paar

$\left(M,\succ\right)$

heisst wohlfundierte Menge.

Beispiele

Auf

$\mathbb{N}$

ist > eine wohlfundierte Relation, auf

$\mathbb{Z}$

nicht.

Die Relation

$l>l'\Longleftrightarrow S\left(l\right)>S\left(l'\right)$

ist wohlfundiert.

Sei

$N\subseteq M$

einer wohlfundierten Menge

$\left(M,\succ\right)$

.

$x\in N$

heisst minimales Element wenn es kein

$y\in N$

gibt so dass

$x\succ y$

gilt. Jede nichtleere Teilmenge eine wohlfundierten Menge hat mindestens ein minimales Element (Beweis durch Widerspruch möglich).

KategorieInformatik KategorieMathematik KategorieAlgebraischeStrukturen KategorieTheoretischeInformatik