Sei A = {1, 2, 3}. Bestimmen Sie alle Äquivalenzrelationen auf A als Teilmengen von A²?

Hat das was mit reflexiv/transitiv/symmetrisch zu tun ?

Natürlich hat das etwas damit zu tun. Denn die Äquivalenzrelationen auf A sind genau diejenigen Relationen auf A, die reflexiv und transitiv und symmetrisch sind.

====== Ergänzung ======

Hinweise zur Lösung:

• Schritt 1: Du kannst dir überlegen, dass R₁ := {(1, 1), (2, 2), (3, 3)} die kleinste reflexive Relation auf A ist. [Da diese außerdem symmetrisch und transitiv ist, hast du bereits die erste Äquivalenzrelation auf A gefunden.]
• Schritt 2: Gehe jetzt alle Paare (a, b) in A² durch und füge (a, b) und (b, a) zu R₁ hinzu [(b, a) wegen der Symmetrie], um eine neue Relation zu erhalten. Diese ist dann auch transitiv, und somit eine weitere Äquivalenzrelation.
• Schritt 3: Gehe jetzt für alle Relationen aus Schritt 2 durch, und ergänze wieder Paare (a, b) und (b, a). Prüfe auf Transitivität. Falls die Relation nicht transitiv ist, ergänze die für die Transitivität notwendigen Paare. [Du wirst dann merken, dass du bereits bei der Potenzmenge von A² bist. Also keine weiteren Paare mehr für einen weiteren Schritt hinzufügen kannst.]

------------

Wenn man etwas faul ist, kann man natürlich auch einem Rechner die Lösung überlassen. Beispielsweise habe ich meinen Rechner mit dem folgenden Python-Skript alle zweistelligen Relationen R auf A durchgehen lassen, was übrigens 2^(3*3) = 2^9 = 512 Relationen sind, und habe für jede dieser Relationen R prüfen lassen, ob sie eine Äquivalenzrelation (also reflexiv und symmetrisch und transitiv) ist.

from itertools import product, chain, combinations

def powerset(iterable):
    s = list(iterable)
    return(chain.from_iterable(combinations(s, r) for r in range(len(s)+1)))

def is_reflexive(R, A):
    for a in A:
        if not (a, a) in R:
            return(False)
    return(True)

def is_symmetric(R):
    for a, b in R:
        if not (b, a) in R:
            return(False)
    return(True)

def is_transitive(R):
    for a, b in R:
        for c, d in R:
            if b == c:
                if not (a, d) in R:
                    return(False)
    return(True)

A = [1, 2, 3]
AA = product(A, A)

n = 0
for R in powerset(AA):
    if is_reflexive(R, A):
        if is_symmetric(R):
            if is_transitive(R):
                n += 1
                print(f"R{n} =", R)

Ergebnis:

R1 = ((1, 1), (2, 2), (3, 3))
R2 = ((1, 1), (1, 2), (2, 1), (2, 2), (3, 3))
R3 = ((1, 1), (1, 3), (2, 2), (3, 1), (3, 3))
R4 = ((1, 1), (2, 2), (2, 3), (3, 2), (3, 3))
R5 = ((1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3))

Als Lösung der Aufgabe also:

Die gesuchten Äquivalenzrelationen auf A = {1, 2, 3} sind...

• R₁ = {(1, 1), (2, 2), (3, 3)}
• R₂ = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)}
• R₃ = {(1, 1), (1, 3), (2, 2), (3, 1), (3, 3)}
• R₄ = {(1, 1), (2, 2), (2, 3), (3, 2), (3, 3)}
• R₅ = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}

Kurze Begründung der Richtigkeit und Vollständigkeit: Ich habe bin (mit dem genannten Python-Skript) alle Relationen R von A×A durchgegangen, also alle 512 Teilmengen R der Potenzmenge P(A×A) durchgegangen. Diese habe ich (entsprechend der Definition einer Äquivalenzrelation) jeweils auf Reflexivität, Symmetrie und Transitivität untersucht.

Du kannst die Übung deutlich abkürzen, wenn Du weißt, dass eine Äquivalenzrelation die Grundmenge A in Äquivalenzklassen zerlegt. Bestimme also zuerst alle möglichen Zerlegungen von A (nicht-leere, disjunkte Teilmengen, die A überdecken). Davon gibt es nur 8.

Die zugehörige Äquivalenzrelation konstruierst Du dann nach dem Schema „jeder mit jedem aus derselben Klasse“. Der Beweis der Reflektivität, Symmetrie und Transitivität ist bei diesem Schema ( xRy ⇔ x, y liegen in derselben Klasse) trivial.

Hat das was mit reflexiv/transitiv/symmetrisch zu tun ?

Ja klar. Du sollst alle Relationen auf A² bestimmen, die reflexiv, transitiv und symmetrisch sind. Also fängst du an alle möglichen Relationen mal hin zu schreiben.