TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 139
Sei eine beliebige Funktion. Welche der Eigenschaften Reflexivität, Symmetrie und Transitivität hat die folgende Relation auf ?
Unter welcher Voraussetzung an die Funktion f ist die Relation R auch antisymmetrisch? Ist R eine Äquivalenzrelation? Falls ja, bestimmen Sie auch die durch R induzierte Partition auf für die Funktionen
(a) ,
(b),
(c) .
{{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[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: .
Äquivalenzklasse[Bearbeiten | Quelltext bearbeiten]
Sei R eine Äquivalenzklasse auf A. Für heißt die Menge
die von a erzeugte Äquivalenzklasse.
"Verschiedene Elemente der Definitionsmenge werden auf verschiedene Elemente der Zielmenge abgebildet": oder äquivalent:
Lösungsvorschlag[Bearbeiten | Quelltext bearbeiten]
Reflexivität[Bearbeiten | Quelltext bearbeiten]
Gilt auf jeden Fall, weil eine Funktion für einen bestimmten Wert immer das gleiche Ergebnis haben muss (ansonsten wäre es keine Funktion)
Symmetrie[Bearbeiten | Quelltext bearbeiten]
Symmetrie ist also auch gegeben
Transitivität[Bearbeiten | Quelltext bearbeiten]
Formel hier einfügen
jetzt setzt man in die obere Gleichung die untere ein
Daher ist auch Transitivität gegeben.
Äquivalenzrelation[Bearbeiten | Quelltext bearbeiten]
Nachdem wie oben gezeigt sowohl Reflexivität, Symmetrie und Transitivität gegeben ist sind alle Vorraussetzungen für eine Äquivalenzrelation gegeben.
Daher ist R eine Äquivalenzrelation.
Antisymmetrie[Bearbeiten | Quelltext bearbeiten]
(diese Gleichung tut hier nichts zur Sache weil sie die Gleiche ist wie aRb)
Nun muss man sich überlegen, welche Eigenschaft die Funktion haben muss damit folgendes gilt
Das ist aber nichts anderes als eine Abwandlung der Definition von Injektivität.
Daher muss die Funktion injektiv sein, damit die Relation antisymmetrisch ist.
Partitionnierungen[Bearbeiten | Quelltext bearbeiten]
(a) [Bearbeiten | Quelltext bearbeiten]
Hier alle Mengen niederschreiben zu wollen wäre relativ mühsam, weil es unendlich viele gibt. Es steckt nämlich jedes einzelne Element aus den ganzen Zahlen in einer eigene Menge.
Anmerkung: mMn ist f(x) = 3 injektiv. Was bedeuten würde das diese Relation Anti-Symmetrisch ist. Demnach auch keine Ä-relation woruch es auch keine Klassen zubestimmen gibt
(b)[Bearbeiten | Quelltext bearbeiten]
Die Funktion liefert den Rest einer Zahl x modulo 3 zurück.
D.h. in userem Fall stehen zwei Zalen a,b in Relation, wenn jeweils der Rest der Zahlen modulo drei gleich groß ist, wenn also a und b in der gleichen Restklasse von liegt.
Daraus ergeben sich folgende drei Klassen:
(c) [Bearbeiten | Quelltext bearbeiten]
Hier gilt das gleiche wie in (a)
Anmerkung zu (c)[Bearbeiten | Quelltext bearbeiten]
Zwei Elemente (Zahlen) sind in der selben Klasse, wenn das Quadrat beider Zahlen gleich ist. Für die natürlichen Zahlen stimmt obige Lösung. Für die ganzen Zahlen muss man allerdings die negativen Zahlen berücksichtigen zB.:
Daher folgt, dass die Zerlegung aussieht wie folgt: