TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 121

Aus VoWi
Zur Navigation springen Zur Suche springen

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.

Hilfreiches[Bearbeiten]

Halbordnung[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

\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[Bearbeiten]

\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[Bearbeiten]

\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[Bearbeiten]

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

Hassediagramm[Bearbeiten]

fehlt