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

Für $k,n\in \lbrace 1,3,4,\ldots ,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
}}

Hilfreiches

Halbordnung

Halbordnung

Eine binäre Relation R auf einer Menge A heißt Halbordnung oder partielle Ordnung, wenn folgende drei Eigenschaften erfüllt sind:

• Reflexivität: $\forall a\,\in A:aRa$,
• Antisymmetrie: $\forall a,b\,\in A:(aRb\wedge bRa)\Rightarrow a=b$,
• Transitivität: $\forall a,b,c\,\in A:(aRb\wedge bRc)\Rightarrow aRc$.

Lösung

Wir untersuchen also, ob die Relation reflexiv, antisymmetrisch und transitiv ist. Erfüllt sie diese drei Eigenschaften, so sprechen wir von einer Halbordnung.

Unsere Kriterien für die Relation ist also, dass $k|n$ ($k$ teilt $n$) und $ggT\left(k,{\frac {n}{k}}\right)=1$ ($k$ und ${\frac {n}{k}}$ teilerfremd).

Reflexivität

$\forall k\in \{1,3,4,\ldots ,10\}:kRk$

Nachdem $k|k$ stimmt, und $ggT\left(k,{\frac {k}{k}}\right)=ggT(k,1)=1$ ist, also teilerfremd, ist die Relation reflexiv.

Antisymmetrie

$\forall n,k\in \{1,3,4,\ldots ,10\}:(kRn\land nRk)\Rightarrow n=k$

Damit $k|n$ und $n|k$ wahr ist, müssen $k$ und $n$ gleich sein:

$n=k\cdot p$

$k=n\cdot q$

Daraus ergibt sich aber nun $n=n\cdot p\cdot q\,{\text{bzw.}}\,k=k\cdot p\cdot q\Rightarrow 1=p\cdot q$. Somit können $p$ und $q$ in unserer Menge aber nur $1$ sein und somit ergibt sich, dass $n=k$. Die Prüfung des zweiten Kriteriums (ggT) können wir uns sparen, da wir nur den Fall $k=n$ betrachten müssen und das haben wir bereits für die Reflexivität erbracht. Die Relation ist also antisymmetrisch.

Transitivität

$\forall n,k,l\in \{1,3,4,\ldots 10\}:(kRl\land lRn)\Rightarrow kRn$

Hier prüfen wir ob $(k|l\land l|n)\Rightarrow k|n$ wahr ist.

$l=k\cdot p_{1}$

$n=l\cdot p_{2}$

Daraus ergibt sich nun $n=k\cdot p_{1}\cdot p_{2}$, also dass $k|n$ gilt.

Nun müssen wir noch prüfen, ob sich aus $ggT\left(k,{\frac {l}{k}}\right)=1$ und $ggT\left(l,{\frac {n}{l}}\right)=1$ dann auch $ggT\left(k,{\frac {n}{k}}\right)=1$ ergibt, diese Eigenschaft also auch transitiv ist.

Aus unseren Überlegungen von vorher wissen wir:

$ggT\left(l,{\frac {n}{l}}\right)=1=ggT\left(k\cdot p_{1},{\frac {l\cdot p_{2}}{l}}\right)=ggT(k\cdot p_{1},p_{2})=1$

Das können wir nun anwenden:

$ggT\left(k,{\frac {n}{k}}\right)=ggT\left(k,{\frac {l\cdot p_{2}}{\frac {l}{p_{1}}}}\right)=ggT\left(k,p_{1}\cdot p_{2}\right)=1$

Somit ist die Relation transitiv.

Halbordnung

Da die Relation reflexiv, antisymmetrisch und transitiv ist, handelt es sich um eine Halbordnung.

Hassediagramm

Edit: Ursprüngliches Diagramm war falsch, wurde korrigiert