TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 122

Aus VoWi
Wechseln zu: Navigation, Suche

Für k,n \in \lbrace 2,3,4,...,10 \rbrace sei kRn, falls k ein Teiler von n ist und k und \frac{n}{k} teilerfremd sind. Man untersuche, ob die Relation R eine Halbordnung ist und ermittle gegebenfalls das Hassediagramm.

Lösungsvorschlag von --Bobsch 11:39, 12. Nov 2007 (CET)[Bearbeiten]

Reflexivität:
\forall  k \mid k(eine Zahl teilt immer sich selbst) ggT(k,\frac{k}{k}) = ggT(k,1) = 1 \Rightarrow - Reflexivität gegeben;

Antisymmetrie:
Annahme: k \mid n \, \land \, n \mid k
k > n \rightarrow k \mid n \,\,\, \nexists \, \forall \, n \neq 0
k < n \rightarrow n \mid k \,\,\, \nexists \, \forall \, k \neq 0
- Antisymmetrie gegeben;

Transitivität
Annahme: k \mid m \, \land \, m \mid n \Rightarrow k \mid n
Folgerung: m = k*x
k*x \mid n \Rightarrow k \mid n
- Transitivität gegeben;

Relation ist Halbordnung

Anmerkung von m4rS bezüglich Transitivität[Bearbeiten]

mMn ist die Folgerung falsch, denn aus k \mid m \, \land \, m \mid n \Rightarrow k \mid n folgt ja, dass m und n gar nicht miteinander in Relation stehen können, weil ggT(m,n)=k

Lösungsvorschlag von ADmiral[Bearbeiten]

- reflexiv:
Zu bew.: nRn muss generell stimmen.

\forall  n \mid n stimmt immer.
ggT(n,\frac{n}{n}) = 1 ebenfalls => Relation ist reflexiv.

- antisymmetrisch:
Zu bew.: kRn \wedge nRk \Rightarrow k = n

(k \mid n) \wedge (n \mid k) \Rightarrow n = k (das ggT-Zeug brauchen wir für den Beweis der Antisymmetrie gar nicht.)
=> Relation ist antisymmetrisch.

- transitiv: (Anm.: Ich verwende hier a, b, c statt n, k, [l,m,o,?], weil ich das für leichter lesbar halte):
Zu bew.: aRb \wedge bRc \Rightarrow aRc

(a \mid b) \wedge (b \mid c) \Rightarrow a \mid c sollte klar sein.
Zu beweisen ist ggT(a, \frac{c}{a}) = 1, also ggT(a, \frac{b}{a} \cdot \frac{c}{b}) = 1.
ggT(a, \frac{b}{a}) = 1 \Rightarrow zu beweisen wäre "nur noch" ggT(a, \frac{c}{b}) = 1.
Dies beweisen wir durch den Schluss:
ggT(a, \frac{b}{a}) = 1 \Rightarrow b = a \cdot x, \neg(a \mid x) (d.h. im b ist das a nur einmal als Faktor drin).
ggT(b, \frac{c}{b}) = 1 \Rightarrow c = b \cdot y, \neg(b \mid y) (d.h. im c ist das b und damit das a nur einmal als Faktor drin).
\Longrightarrow \neg(a \mid \frac{c}{b})
=> Relation ist transitiv.

Links[Bearbeiten]

  • Diskussion Informatik-Forum WS07 Beispiel 105