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

Man untersuche nachstehend angeführte Relationen $R\subseteq {M^{2}}$ im Hinblick auf die Eigenschaften Reflexivität (R), Symmetrie (S), Antisymmetrie (A) und Transitivität (T):

a) $M={\text{Menge aller Einwohner von Wien (Volkszählung 2001)}},aRb\Leftrightarrow a{\text{ ist verheiratet mit }}b$

b) $M{\text{ wie oben}},aRb\Leftrightarrow a{\text{ ist nicht aelter als }}b$

c) $M{\text{ wie oben}},aRb\Leftrightarrow a{\text{ ist so gross wie }}b$

d) $M=\mathbb {R} ,aRb\Leftrightarrow a-b\in \mathbb {Z}$

e) $M=\mathbb {R} ^{n},(x_{1},...,x_{n})R(y_{1},...,y_{n})\Leftrightarrow x_{i}\leq y_{i}\forall i=1,...,n$

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Hilfreiches

Reflexivität

Reflexivität

$\forall a\in M:\quad aRa$

Symmetrie

Symmetrie

$\forall a,b\in M:aRb\Rightarrow bRa$

Antisymmetrie

Antisymmetrie

$\forall a,b\in M:\quad aRb\wedge bRa\Longrightarrow a=b$

Transitivität

Transitivität

$\forall a,b,c\in M:\quad a\circ b\wedge b\circ c\Rightarrow a\circ c$

Lösung von Baccus

(naiv, bitte nochmal überprüfen!): ($\top$= wahr, $\bot$= falsch):

Beispiel (a) $aRb\Leftrightarrow$$a$ ist verheiratet mit $b$

(R) $\forall x\in A:xRx:\bot$ Man kann (noch) nicht mit sich selbst verheiratet sein.

(S) $\forall x,y\in A:xRy\Rightarrow yRx:\top$ Wenn Gattin mit Gatte verheiratet, dann auch Gatte mit Gattin.

(A) $\forall x,y\in A:xRy\wedge yRx\Rightarrow x=y:\bot$ Im Endeffekt wie (R).

(T) $\forall x,y,z\in A:xRy\wedge yRz\Rightarrow xRz:\bot$ Drei Leute müßten untereinander verheiratet sein; möglich, aber (zumindest) der Papst mag das nicht.

Beispiel (b) $aRb\Leftrightarrow$$a$ ist nicht älter als $b$

(R) $\forall x\in A:xRx:\top$ ich bin nicht älter als ich

(S) $\forall x,y\in A:xRy\Rightarrow yRx:\bot$

(A) $\forall x,y\in A:xRy\wedge yRx\Rightarrow x=y:\top$ (*)

(T) $\forall x,y,z\in A:xRy\wedge yRz\Rightarrow xRz:\top$

Beispiel (c) $aRb\Leftrightarrow$$a$ ist so groß wie $b$

(R) $\forall x\in A:xRx:\top$

(S) $\forall x,y\in A:xRy\Rightarrow yRx:\top$

(A) $\forall x,y\in A:xRy\wedge yRx\Rightarrow x=y:\bot$ (*)

(T) $\forall x,y,z\in A:xRy\wedge yRz\Rightarrow xRz:\top$

Beispiel (d) $aRb\Leftrightarrow a-b\in \mathbb {Z}$

(R) $\forall x\in A:xRx:\top$

Beispiel: $x-x=0\in \mathbb {Z}$

(S) $\forall x,y\in A:xRy\Rightarrow yRx:\top$

(A) $\forall x,y\in A:xRy\wedge yRx\Rightarrow x=y:\bot$

(T) $\forall x,y,z\in A:xRy\wedge yRz\Rightarrow xRz:\top$

Beispiel (e) $(x_{1},...,x_{n})R(y_{1},...,y_{n})\Leftrightarrow x_{i}\leq y_{i}\forall i=1,...,n$

(R) $\forall x\in A:xRx:\top$

(S) $\forall x,y\in A:xRy\Rightarrow yRx:\bot$

Gegenbeispiel: $(1,1)\leq (1,2);(1,1)\ngeq (1,2)$

(A) $\forall x,y\in A:xRy\wedge yRx\Rightarrow x=y:\top$

(T) $\forall x,y,z\in A:xRy\wedge yRz\Rightarrow xRz:\top$

Beweis: $x_{i}\leq y_{i}\wedge y_{i}\leq z_{i}\Rightarrow x_{i}\leq z_{i}$

(*) Die Antisymmetrie ist bei Beispiel (b) und (c) eine Definitionsfrage. Es kommt darauf an, wie genau das Alter bzw, die Größe gemessen werden.

Vorsicht: Das hier nur abzuschreiben, ohne es durchzudenken, gibt Ärger. An der Tafel muß man auf Aufforderung dazu bereit sein, für alle Punkte Beweise oder Gegenbeispiele anzuführen (und beim UE-Test sowieso!).

Außerdem ist in einem Punkt da oben ein Hund drin, den ich mir vom Adrenalinrausch an der Tafel nicht mehr gemerkt habe :-).

Nachdenker erwünscht! (bitte auch gleich ausbessern, danke)

--Baccus 05:31, 26. Nov 2006 (CET)

---

Der Fehler war bei c) (A): x=y bedeutet hier nicht, dass beide gleich groß sind, sondern, dass es die gleichen Personen sind. Daher ist die Aussage falsch.

mick: naja, beim unteren beispiel wurde anhand einer funktion das alter ermittelt, was anscheinend das alter in zahlen wiedergibt. wenn man dem ansatz folgt, könnte man genausogut hier auch z.b. größe(a) = größe(b) anwenden mit den rückgabewerten true/false. dann wäre die aussage wahr.

---

andihi: Bei b) war auch ein Fehler bei der Antisymmetrie: Da die Angabe $a$ ist nicht älter als $b$ lautet, ist das gleichbedeutend mit $Alter(a)\leq Alter(b)$ Daraus folgt für mich: $(Alter(a)\leq Alter(b))\wedge (Alter(b)\leq Alter(a))\Rightarrow Alter(a)=Alter(b)$

---

Bsp d ist glaube ich auch falsch: sollte lauten: (A) $\forall x,y\in A:xRy\wedge yRx\Rightarrow x=y:\top$ wegen $aRb\Leftrightarrow a-b\in \mathbb {Z}$ kann $aRb$ immer falsch sein, ausser $a=b\Rightarrow a-a=0$ und $0\in \mathbb {Z}$ Wenn laut Def. der Implikation diese immer wahr ist, wenn die erste Aussage falsch ist, so müßte die gesamte Aussage doch wahr sein und somit die Antisymmetrie ebenso

---

Zu letzter Behauptung: Beispiel: Bei $(1.4,2.4)\in R$ gilt ja auch $(2.4,1.4)\in R$, aber $a\neq b$, deswegen keine Antisymmetrie. Andreas (Diskussion) 16:37, 2. Apr. 2015 (CEST)