Eine Relation ist in der Mathematik eine Zusammenstellung oder Zuordung von Elementen aus einer oder mehr Mengen. Eine 2-stellige (binäre) Relation ordnet den Elementen einer Menge die Elemente einer zweiten Menge zu. Die zwei Mengen müssen nicht verschieden sein, so können die sich zugeordneten Elemente auch aus ein und derselben Menge stammen.

Table of contents

1 Definition 2 Erläuterungen 3 Beispiel 4 Eigenschaften 5 Klassen von Relationen 6 Siehe auch

Definition

Erläuterungen

Für "(a, b) " schreibt man meist "a R b". Sehr oft ist dabei die Menge A = B, also . Relationen können als Funktionenen gesehen werden, deren Definitionsmenge das kartesische Produkt der Mengen ist und deren Wertemenge lediglich wahr und falsch umfasst. (Was etwas verwirrend sein könnte, denn eine Funktion ist eine spezielle Relation, siehe Tabelle unten.) Man könnte also auch R(a,b) für den Ausdruck der Relation schreiben.

Beispiel

Eigenschaften

Wichtige Eigenschaften von binären Relationen sind: {| border="1" ! Die Relation heißt ! wenn gilt ! und das bedeutet |----- | reflexiv (A = B)

|

| Jedes Element steht in Relation zu sich selbst |----- | irreflexiv (A = B)

|

| Kein Element steht in Relation zu sich selbst |----- | symmetrisch (A = B)

|

| Die Relation ist ungerichtet |----- | antisymmetrisch bzw. identitiv (A = B)

|

| Es kann z.B. nicht a kleiner b und b kleiner a sein. |----- | transitiv (A = B)

| ∀ a,b,c ∈ A: a R b ∧ b R c ⇒ a R c

| Anfang und Ende einer verbundenen Sequenz sind verbunden |----- | intransitiv

| nicht transitiv

| nicht bei jeder verbundenen Sequenz sind Anfang und Ende verbunden |----- | antitransitiv

| ∀ a,b,c ∈ A: a R b ∧ b R c ⇒ ¬ a R c

| bei keiner verbundenen Sequenz sind Anfang und Ende verbunden |----- | Funktion

|

| Jedem a wird genau ein b zugeordnet. A heißt Definitionsmenge und B Wertemenge |----- | total bzw. linear (A = B)

|

| Je zwei Elemente stehen in Relation |----- | linkstotal

| ∀ a ∈ A ∃ b ∈ B: a R b

| Jedes El. aus A hat einen Partner in B |----- | rechtstotal

| ∀ b ∈ B ∃ a ∈ A: a R b

| Jedes El. aus B hat einen Partner in A |----- | linkseindeutig

| ∀ a,c ∈ A ∀ b ∈ B: a R b ∧ c R b ⇒ a = c

| Kein El. aus B hat mehr als einen Partner in A |----- | rechtseindeutig

| ∀ a ∈ A ∀ b,c ∈ B: a R b ∧ a R c ⇒ b = c

| Kein El. aus A hat mehr als einen Partner in B |----- | alternativ (A = B)

| ∀ a,b: a R b ¬ b R a

| Es gilt stets genau eine der Relationen a R b oder b R a |}

Relationen werden oft auch mit N:1 oder N:N und dergleichen charakterisiert. Dabei steht 1, wenn es rechts steht, für linkstotal und rechtseindeutig (und umgekehrt). N steht meistens für gar nichts. Manchmal wird auch 0 statt 1 verwendet, um die Totalität wegzulassen.

Klassen von Relationen

Wichtige Klassen von Relationen:

• Eine Funktion ist linkstotal und rechtseindeutig (d.h. N:1).
• Eine Ordnungsrelation ist reflexiv, transitiv und antisymmetrisch.
• Eine Äquivalenzrelation ist reflexiv, transitiv und symmetrisch.