1.1 Relationen

Definition (Relation)

Relationen

Eine Menge R heißt eine (zweistellige) Relation, falls jedes Element von R ein geordnetes Paar ist. Gilt R ⊆ A × A für eine Menge A, so heißt R eine Relation auf A. Anstelle von (a, b)  ∈  R schreiben wir auch a R b.

Definitions- und Wertebereich

Für eine Relation R setzen wir (mit dom und rng für engl. domain bzw. range):

Def (R) = dom(R) = { a | es gibt ein b mit a R b }, (Definitionsbereich)

Bild(R) = rng(R) = { b | es gibt ein a mit a R b }, (Bild oder Wertebereich)

Eigenschaften einer Relation R bzgl. einer Menge A

R heißt … auf A	falls für alle a, b, c  ∈  A gilt:
reflexiv	a R a
irreflexiv	nicht(a R a)
symmetrisch	a R b impliziert b R a
antisymmetrisch	(a R b und b R a) impliziert a = b
transitiv	(a R b und b R c) impliziert a R c

Drei Darstellungen einer Relation R auf { 1, 2, 3, 4 }. Es gilt

1 R 1, 1 R 2, 2 R 1,

2 R 4, 2 R 3, 4 R 3,

Def (R) = { 1, 2, 4 },

Bild(R) = { 1, 2, 3, 4 }.

In einer Relation R sind alle Paare (a, b), die in einer „bestimmten Beziehung“ stehen, versammelt. Statt (a, b)  ∈  R wird meistens a R b geschrieben, wie man es etwa von a ≤ b oder a = b gewohnt ist. Wir vereinbaren zudem:

a R b R c bedeutet a R b und b R c.

Man vergleiche hierzu wieder a ≤ b ≤ c und a = b = c.

Beispiele

(1)

Die Kleinergleich-Relation auf ℕ kann definiert werden durch

≤ = { (n, m)  ∈  ℕ² | es gibt ein k  ∈  ℕ mit n + k = m }, (Kleinergleich auf ℕ)

oder gleichwertig − und besser lesbar − durch die Setzung

n ≤ m, falls es gibt ein k  ∈  ℕ mit n + k = m

für alle n, m  ∈  ℕ. Es gilt

Def (≤) = Bild(≤) = ℕ.

Die ≤-Relation ist reflexiv, antisymmetrisch und transitiv.

(2)

Für alle d, a  ∈  ℤ setzen wir

d | a, falls es gibt ein k  ∈  ℤ mit kd = a. (Teilbarkeit auf ℤ)

Gilt d|a, so heißt d ein Teiler oder Divisor von a und a ein (ganzzahliges) Vielfaches von d. Es gilt

Def (|) = Bild(|) = ℤ.

Die |-Relation ist reflexiv und transitiv. Sie ist nicht antisymmetrisch, da −2|2 und 2|−2, aber 2 ≠ −2.

(3)

Sei m  ∈  ℕ − { 0 }. Dann setzen wir für alle a, b  ∈  ℤ

a ≡ _m b, falls m|(a − b). (Kongruenz modulo m)

Gilt a ≡ _m b, so sagen wir, dass die Zahlen a und b kongruent modulo m sind.

Die Relation ≡ _m ist reflexiv, symmetrisch und transitiv. Wir schreiben oftmals auch a ≡ b mod(m) anstelle von a ≡ _m b. So gilt zum Beispiel

0 ≡ 5 ≡ −25 mod(5),

−5 ≡ 2 ≡ 16 mod(7).