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.
