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

From VoWi
Jump to navigation Jump to search

Für sei , falls ein Teiler von ist und und teilerfremd sind. Man untersuche, ob die Relation R eine Halbordnung ist und ermittle gegebenfalls das Hassediagramm.

Hilfreiches[edit]

Halbordnung
Halbordnung[edit]

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

  • Reflexivität: ,
  • Antisymmetrie: ,
  • Transitivität: .

Lösung[edit]

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 ( teilt ) und ( und teilerfremd).

Reflexivität[edit]

Nachdem stimmt, und ist, also teilerfremd, ist die Relation reflexiv.

Antisymmetrie[edit]

Damit und wahr ist, müssen und gleich sein:

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

Transitivität[edit]

Hier prüfen wir ob wahr ist.

Daraus ergibt sich nun , also dass gilt.

Nun müssen wir noch prüfen, ob sich aus und dann auch ergibt, diese Eigenschaft also auch transitiv ist.

Aus unseren Überlegungen von vorher wissen wir:

Das können wir nun anwenden:

Somit ist die Relation transitiv.

Halbordnung[edit]

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

Hassediagramm[edit]

fehlt