Äquivalenzklassen und Vertretersysteme

Aufrufe: 113     Aktiv: 12.01.2023 um 14:11

0

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!

gefragt

Student, Punkte: 15

 
Kommentar schreiben
1 Antwort
1
Es ist immer sinnvoll hier die Definitionen aller Begriffe beizufügen. Für "Vertretersystem" gibt es keine einheitliche Def., und welche für diese Aufgabe gemeint ist, kann man nur rückschließen aus der Bemerkung "Vorsicht...".
Überlege wieviele Vertretersysteme es für jede EINZELNE Klasse gibt und kombiniere dann alle zusammen. Das kommt Deiner zweiten Variante relativ nahe.
Diese Antwort melden
geantwortet

Lehrer/Professor, Punkte: 31.96K

 

Vielen Dank für deine Hilfe, ich stehe leider noch etwas auf dem Schlauch. Wenn ich dich richtig verstehe muss ich Mächtigkeit der Potenzmenge jeder Klasse einzeln bestimmen. Wenn ich die dann kombieniere komme ich auf den Wert den ich in der zweiten Variante bestimmt habe. Dabei muss ich allerdings ja auch beachten das die Leere Menge nicht Teil des Vertretersystems sein darf da der Vertreter nicht leer sein darf. Ich weiß nur leider nicht wie ich die leere Menge exkludiere und wo mein denk fehler liegt.

Vielleicht kannst du mir ja nochmal weiterhelfen.
  ─   travelurmel 12.01.2023 um 13:05

Ich habe von Vertretersystemen gesprochen, nicht von der Potenzmenge. Aus gutem Grund. Dann hast Du auch mit der leeren Menge nichts zu tun.
Es geht natürlich auch mit der Potenzmenge, wenn man dabei dann die leere Menge ausschließt. Anscheinend ist Dir das ja klar, wo ist also das Problem?
Gehe vor wie in meiner Antwort: "Überlege Dir..."
Also konkret: wieviele VS gibt es für die 1. ÄK? Wieviele für die 2. ÄK, usw.
  ─   mikn 12.01.2023 um 13:12

Ok wenn ich also überlege wie viele Vertretersysteme es für jede Klasse geben kann komme ich auf folgendes:
1. ÄK =1^1=1VS, 2. ÄK =3^3=27VS 3. ÄK =5^5=3125VS. Die anderen sind ja trivial und dann komme ich auf 675000 Vertetersysteme für alle Klassen wenn ich diese mit einander kombiniere. Habe ich den richtigen weg gewählt oder stecke ich immer noch im falschen Denkmuster?
  ─   travelurmel 12.01.2023 um 13:27

Nein. Du willst anscheinend unbedingt eine Formel anwenden. Warum? Schreib die möglichen Vertreter doch einfach mal hin, für die ersten beiden ÄKln z.B. Kannst ja die Elemente abkürzen, damit nicht so viel zu schreiben ist. So viele sind es auch nicht.
Formeln anwenden ohne sie verstanden zu haben ist meist (so auch hier) keine gute Idee.
  ─   mikn 12.01.2023 um 13:31

Das mit der Formel habe ich aus unserem Tutorium. Dort wurde mir gesagt ich soll eine kombinatorische Formel finden weil es zu viele Ergebnisse gibt um die so zu zählen oder zu berechnen.

Anzahl der möglichen Vertreter für ÄK 1,2,3 hätte ich dann 1,3,5
  ─   travelurmel 12.01.2023 um 13:56

Insgesamt sind es zu viele, aber nicht für die einzelnen ÄKln. Deine Vertreterzahlen stimmen, aber ich hatte mich falsch ausgedrückt: Ich meinte Vertretersysteme pro ÄK, wie vorher auch. Also los, nun mach mal.   ─   mikn 12.01.2023 um 14:11

Kommentar schreiben