TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 134

From VoWi
Jump to navigation Jump to search

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) .

Hilfreiches[edit]

Äquivalenzrelation
Äquivalenzrelation[edit]

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

Reflexivität: ,

Symmetrie: ,

Transitivität: .

Antisymmetrie
Antisymmetrie[Bearbeiten, Wikipedia, 1.60 Definition]

Äquivalenzklasse
Äquivalenzklasse[edit]

Sei R eine Äquivalenzklasse auf A. Für heißt die Menge

die von a erzeugte Äquivalenzklasse.

Injektivität
Injektivität[Bearbeiten, Wikipedia, 1.65 Definition]

"Verschiedene Elemente der Definitionsmenge werden auf verschiedene Elemente der Zielmenge abgebildet": oder äquivalent:

Lösungsvorschlag[edit]

Reflexivität[edit]

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[edit]


Symmetrie ist also auch gegeben

Transitivität[edit]


Formel hier einfügen


jetzt setzt man in die obere Gleichung die untere ein

Daher ist auch Transitivität gegeben.

Äquivalenzrelation[edit]

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[edit]


(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[edit]

(a) [edit]



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.

(b)[edit]


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) [edit]



Hier gilt das gleiche wie in (a)

Anmerkung zu (c)[edit]

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: