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

Für $k,n\in \{1,3,4,\dots ,10\}$ 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: $\mathrm{\forall }a\in A:aRa$,
• Antisymmetrie: $\mathrm{\forall }a,b\in A:(aRb\wedge bRa)\Rightarrow a=b$,
• Transitivität: $\mathrm{\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(k,\frac{n}{k})=1$ ($k$ und $\frac{n}{k}$ teilerfremd).

Reflexivität

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

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

Antisymmetrie

$\mathrm{\forall }n,k\in \{1,3,4,\dots ,10\}:(kRn\wedge 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

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

Hier prüfen wir ob $(k|l\wedge 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(k,\frac{l}{k})=1$ und $ggT(l,\frac{n}{l})=1$ dann auch $ggT(k,\frac{n}{k})=1$ ergibt, diese Eigenschaft also auch transitiv ist.

Aus unseren Überlegungen von vorher wissen wir:

$ggT(l,\frac{n}{l})=1=ggT(k\cdot p_1,\frac{l\cdot p_2}{l})=ggT(k\cdot p_1,p_2)=1$

Das können wir nun anwenden:

$ggT(k,\frac{n}{k})=ggT(k,\frac{l\cdot p_2}{\frac{l}{p_1}})=ggT(k,p_1\cdot p_2)=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