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

Aus VoWi
Wechseln zu: Navigation, Suche

Stellen Sie die folgende Relation im kartesischen Koordinatensystem und auch als gerichteten Graphen dar, und untersuchen Sie weiters, ob eine Äquivalenzrelation vorliegt.

mRn \Leftrightarrow ggT(m,n) = 1, m,n \in \{1,2,3,...\} = M, wobei ggT(m,n) den größen gemeinsamen Teiler der Zahlen m und n bezeichnet.

Hilfreiches[Bearbeiten]

Äquivalenzrelation[Bearbeiten]

Eine binäre Relation R auf einer Menge A heißt Äquivalenzrelation, wenn folgende drei Eigenschaften erfüllt sind:

Reflexivität: \forall a\, \in A: aRa,

Symmetrie: \forall a,b\, \in A: aRb \Rightarrow bRa,

Transitivität: \forall a,b,c\, \in A: (aRb \wedge bRc) \Rightarrow aRc.

Theoretische Grundlagen (von mnemetz)[Bearbeiten]

Ein Element d heißt größter gemeinsamer Teiler von a und b (dargestellt durch d = ggT(a,b), wenn gilt:

  • d ist ein gemeinsamer Teiler, d.h. d|a \wedge d|b
  • Jeder gemeinsamer Teiler teilt d, d.h. t|a \wedge t|b \Rightarrow t|d
  • Gilt 1 = ggT(a,b), so heißen a und b relativ prim

Relation: Eine Relation ist - allgemein - eine "Verwandtschaftsbeziehung", formal dargestellt:

  • Die Teilmenge R \subseteq M \times M

Äquivalenzrelation: Eine solche trifft zu, wenn von der Menge A folgende Eigenschaften erfüllt sind:

  1. Reflexivität: aRa, \forall A \in A
  2. Symmetrie: aRb, \forall a,b \in A
  3. Transitivität: (aRb \wedge bRc) \Rightarrow aRc, \forall a,b,c \in A

Lösungsvorschlag von mnemetz[Bearbeiten]

Cartestisches Koordinatensystem[Bearbeiten]

6 | .       .
5 | . . . .   .
4 | .   .   .
3 | . .   . .
2 | .   .   .
1 | . . . . . .
---------------
  | 1 2 3 4 5 6

gerichteter Graph[Bearbeiten]

(folgt) bitte selber zeichnen, ist nicht sehr schwer. Einfach jeden Punkt lt. Tabelle oben miteinander verbinden. Eine Zeichnung hier rein stellen ist nicht grad leicht.

Äquivalenzrelation[Bearbeiten]

Reflexivität[Bearbeiten]

ggT(m,n) = 1, \forall n \in M ist nicht gegeben (ausser m = 1)

Symmetrie[Bearbeiten]

ggT(m,n) = 1 \Rightarrow ggT(n,m) = 1 ist gegeben, denn 1|m \wedge 1|n \Rightarrow 1|n \wedge 1|m - die Reihenfolge von m und n ist nicht von Bedeutung

Transitivität[Bearbeiten]

ggT(m,n) = 1 \wedge ggT(n,p) = 1 \Rightarrow ggT(m,p) = 1 ist nur bedingt gegeben, denn (1|m \wedge 1|n) \wedge (1|n \wedge 1|p) ist nur bedingt gegeben, da auch m = p sein kann (z.B. m = 3, n = 5, p = m) //das is blödsinn, 1 teilt jede natürliche zahl...

Ein einfaches Gegenbeispiel:

m = 4, n = 5, p = 2:

  • 4R5 <=> ggT(4,5) = 1
  • 5R2 <=> ggT(5,2) = 1
  • 4R5 & 5R2 => 4R2 <=> ggT(4,2) = 2 =/= 1 => nicht transitiv

Schlussfolgerung[Bearbeiten]

Es liegt keine Äquivalenzrelation vor!