TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 110

Aus VoWi
Zur Navigation springen Zur Suche springen

Man zeige, dass durch für alle eine Äquivalenzrelation in der Menge erklärt wird, und bestimme die zugehörige Partition.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:
{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches[Bearbeiten | Quelltext bearbeiten]

Äquivalenzrelation
Äquivalenzrelation[Bearbeiten | Quelltext bearbeiten]

Eine binäre Relation R auf einer Menge A heißt Äquivalenzrelation, wenn folgende drei Eigenschaften erfüllt sind:

Reflexivität: ,

Symmetrie: ,

Transitivität: . Partition (Seite 38 in Mathematik für Informatik) (4. Auflage: Seite 40)
Satz 1.59: Sei R eine Äquivalenzrelation auf A. Dann bilden die (verschiedenen) Äquivalenzklassen der Elemente von A eine Partition von A. (Ebenfalls Seite 38)

Lösungsversuch[Bearbeiten | Quelltext bearbeiten]

Zeigen der Äquivalenzrelation[Bearbeiten | Quelltext bearbeiten]

Reflexivität[Bearbeiten | Quelltext bearbeiten]

6 teilt 0 also ist es Reflexiv.

Symmetrie[Bearbeiten | Quelltext bearbeiten]



Wenn 6 teilt dann teilt es auch da es die selben Zahlen sind nur mit anderem Vorzeichen.

Transitivität[Bearbeiten | Quelltext bearbeiten]








Somit ist es Transitiv

Anmerkung zur Transitivität[Bearbeiten | Quelltext bearbeiten]

Mir ist es der obige Nachweis nicht ganz einleuchtend, daher hier ein alternativer Weg:

Da waren ein paar Tippfehler im obigen Beweis… jetzt sollte er verständlicher sein. -- hop

Alle Vorraussetzungen sind erfüllt, somit ist es eine Äquivalenzrelation

--MatheFreak 01:29, 15. Dez. 2010 (CET)

Bestimmen der Partition[Bearbeiten | Quelltext bearbeiten]

Anwendung von Satz 1.59

Allgemein[Bearbeiten | Quelltext bearbeiten]


Um die Klassen bestimmen zu können, formen wir mal unsere Relation um:


Und das erinnert doch schon sehr stark an die Kongruenzrechnung. D.h. man kann die Relation auch wie folgt betrachten:



Das bedeutet, man würde auf jeden Fall 6 Äquivalenzklassen erwarten. Wenn man sich das aber genauer überlegt erkennt man, dass manche von diesen leer sind. Das liegt daran, dass hier das Quadrat im Spiel ist. z. B. für 2: aber
.

Das muss man für alle Möglichkeiten durchspielen, um zu sehen, in welchen Mengen tatsächlich Elemente enthalten sein werden:






Äquivalenzklasse 0[Bearbeiten | Quelltext bearbeiten]



Äquivalenzklasse 1[Bearbeiten | Quelltext bearbeiten]



Äquivalenzklasse 2[Bearbeiten | Quelltext bearbeiten]



Äquivalenzklasse 3[Bearbeiten | Quelltext bearbeiten]



Äquivalenzklasse 4[Bearbeiten | Quelltext bearbeiten]



Äquivalenzklasse 5[Bearbeiten | Quelltext bearbeiten]



Partition[Bearbeiten | Quelltext bearbeiten]

Edit: Wie oben bewiesen sind und leere Teilmengen, die Partition ist jedoch ein System von nichtleeren Teilmengen.

Links zu anderen Lösungen des gleichen Beispiels[Bearbeiten | Quelltext bearbeiten]

TU Wien:Mathematik 1 UE (diverse)/Übungen SS10/Beispiel 18