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

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.

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
}}

Lösungsvorschlag von --Bobsch 11:39, 12. Nov 2007 (CET)[Bearbeiten | Quelltext 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 | Quelltext 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 | Quelltext 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.