Ich habe eine Frage bezüglich eines Beweises. Zunächst einmal die Aufgabe und was gegeben ist.
Seien X := {1, 2, 3}, Y := {4, 5}, Z := {−12,−14,−16} und P := X × Y × Z.
Wir definieren eine Relation ≡ auf P wie folgt: Für alle (x1, y1, z1), (x2, y2, z2) ∈ P gelte (x1, y1, z1) ≡ (x2, y2, z2)
genau dann, wenn x1 + y1 − 1/2z1 = x2 + y2 − 1/2z2 gilt. Diese Relation ist eine Äquivalenzrelation. (Das dürfen Sie ohne Beweis verwenden.) (Die Zahlen hinter x,y,z sind lediglich zum zweck der Nummerierung und sind eigentlich tiefgestellt.)
Verwenden Sie Definition 7.1.6 für folgende Aufgaben:
(a) Geben Sie ohne weitere Begründung jede Äquivalenzklasse von ≡ in expliziter Darstellung an.
(b) Geben Sie mit detailliertem Beweis die Anzahl der Vertretersysteme von ≡ an. (Vorsicht: Es
wird nicht gefordert, dass jede Klasse durch genau ein Element vertreten wird.)
Zu a) Die Äquivalenzklassen habe ich bestimmt, es sind folgende.
[(1,4,-12)]≡={(1,4,-12)},
[(1,4,-14)]≡={(1,4,-14), (1,5,-12), (2,4,-12)},
[(1,4,-16)]≡={(1,4,-16), (1,5,-14), (2,4,-14), (2, 5,-12), (3,4,-12)},
[(1,5,-16)]≡={(1,5,-16), (2,4,-16), (2,5,-14), (3,4,-14), (3,5,-12)},
[(2,5,-16)]≡={(2,5,-16), (3,4,-16), (3,5,-14)},
[(3,5,-16)]≡={(3,5,-16)}.
Zu b) Hier meine Frage, wie ich die Anzahl der Vertretersysteme beweisen kann?
Mein Ansatz:
Wie wir in a) erkennen können, haben wir 6 Äquivalenzklassen mit einer unterschiedlichen Menge an Tripeln. Das bedeutet jedes unser Vertretersysteme ist 6 Tripel lang. Damit ein Vertretersystem als solches bezeichnet werden kann müssen alle Äquvalenzklassen vertreten sein.
Wir brauchen nun eine Formel in expliziter und deskriptiver Schreibweise die beweist wie viele Vertretersysteme ≡ hat.
Dort liegt mein Problem: Ich gehe davon aus das ich die Anzahl der Vertretersysteme mithilfe der Mächtigkeit der Potenzmenge beweisen kann.
Die Mächtigkeit der Potenzmenge wird wie folgt berechnet: |P(M)|=2^|M|
Wir müssen nun also zunächst M berechnen. Wir können sagen das die 6 Äquivalenzklassen Mengen sind, wir sagen also die Äquivalenzklassen sind die Mengen A-F mit folgenden Mengen an Elementen. A=1, B=3, C=5, D=5, E= 3, F=1.
Ich habe jetzt zwei verschiedene Berechnungen und weiß nicht welche Berechnung wenn überhaupt richtig ist. (Das dies noch kein formaler Beweis ist, ist mir bewusst.)
1. Variante: |P(M)|=2^|M| = |P(A*B*C*D*E*F)|=2^|225|=5,391989333x10^67
2. Variante: |P(M)|=2^|M| = |P(A+B+C+D+E+F)|=2^|18|= 262144
Es wäre super wenn mir jemand bei der Lösung dieser aufgabe helfen könnte und mir sagen kann ob ich die richtigen Überlegungen getroffen habe oder wie ich den richtigen Beweis aufstellen kann.
Vielen Dank!
Vielleicht kannst du mir ja nochmal weiterhelfen. ─ travelurmel 12.01.2023 um 13:05