∀ Mathe 1 PrepDiskrete Mathematik · Folien 1–3

Äquivalenzrelationen & mod

ca. 15 min0 / 4 Übungen

Äquivalenzrelationen sortieren eine Menge in Schubladen: Was in derselben Schublade liegt, gilt als „gleich“. Das wichtigste Beispiel ist das Rechnen modulo m.

Definition · Äquivalenzrelation, KlasseDef. 1.31, Folien 3 S. 2
R heißt Äquivalenzrelation, wenn R reflexiv, symmetrisch und transitiv ist. Die Äquivalenzklasse von a ist [a]R = {b ∈ A : aRb}.
Definition · PartitionDef. 1.34, Kor. 1.35, Folien 3 S. 5–8
Eine Zerlegung von A in nichtleere, paarweise disjunkte Teilmengen, die zusammen A ergeben. Äquivalenzrelationen und Partitionen entsprechen sich genau: Die Klassen bilden eine Partition, und zu jeder Partition gehört die Relation „liegt im selben Block“.
Intuition: Schubladen
Satz 1.33 sagt: Zwei Klassen sind entweder gleich oder disjunkt. Jede Sache liegt in genau einer Schublade. Im Graphen einer Äquivalenzrelation ist jeder Block „komplett verbunden“: alle Pfeile innerhalb, Schlingen überall, keine Pfeile zwischen Blöcken.
Beispiel · Äquivalenzhülle
A = {1, 2, 3, 4, 5}, R = {(1, 2), (2, 3), (4, 4)}. Ergänze möglichst wenige Paare, sodass eine Äquivalenzrelation entsteht.
    0 / 4
    ✏️ Übung · Zur Äquivalenzrelation ergänzenmittel
    Ergänze möglichst wenige Pfeile, sodass eine Äquivalenzrelation entsteht. Die Startpfeile bleiben fest. Wenn alles stimmt, werden die Klassen angezeigt.
    abcd
    ✗ reflexiv
    (a, a) fehlt.
    ✗ irreflexiv
    (c, c) ist enthalten.
    ✗ symmetrisch
    (a, b) ∈ R, aber (b, a) ∉ R.
    ✓ antisymmetrisch
    Zwischen zwei verschiedenen Elementen nie Hin- und Rückpfeil.
    ✓ transitiv
    Jeder Weg aus zwei Pfeilen hat schon eine direkte Abkürzung.
    Knoten anklicken, dann Zielknoten: Pfeil an/aus. Neue Pfeile sind farbig.
    R = {(a, b), (c, c)}
    ✏️ Übung · Partition oder nicht?leicht
    Ist das eine Partition von A = {1, 2, 3, 4, 5, 6}?
    {{1, 2}, {3, 4}, {5, 6}}
    {{1, 2, 3}, {3, 4, 5}, {6}}
    {{1, 2, 3, 4, 5, 6}}
    {{1}, {2}, {3}, {4}, {5}}
    {{1, 3, 5}, ∅, {2, 4, 6}}

    Kongruenz modulo m

    Definition · a ≡ b (mod m)Bsp. 1.36, Folien 3 S. 9–10
    a und b lassen bei Division durch m denselben Rest. Das ist eine Äquivalenzrelation auf ℤ mit genau m Klassen (Restklassen) {mq + r : q ∈ ℤ} für r = 0, 1, …, m − 1.
    Division mit Rest
    a = q·m + r mit 0 ≤ r < m; q und r sind eindeutig. Für negative a wird q negativ genug gewählt: −7 = (−3)·3 + 2, also Rest 2 (nicht −1!). Und der wichtigste Trick: a ≡ b (mod m) ⇔ m | (a − b).
    Auch negative Zahlen richtig einsortieren. Eigene Animation der KI zu Bsp. 1.36.
    ✏️ Übung · Reste und Kongruenzen (Zufall)leicht
    Fünf richtige = gelöst (0/5).
    Welchen Rest hat 15 bei Division durch 6? (also 15 mod 6)
    ✏️ Übung · Klassen einer Relation auf ℤmittel
    Auf ℤ sei a ∼ b :⇔ a − b ist durch 3 teilbar. Wie viele Äquivalenzklassen gibt es, und welche ist [7]?