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

Aus VoWi
Zur Navigation springen Zur Suche springen

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
Ä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!