TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 88

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

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

Theoretische Grundlagen (von mnemetz)

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 f, 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,\mathrm{\forall }A\in A$
2. Symmetrie: $aRb,\mathrm{\forall }a,b\in A$
3. Transitivität: $(aRb\vee bRc)\Rightarrow aRc,\mathrm{\forall }a,b,c\in A$

Lösungsvorschlag von mnemetz

Cartestisches Koordinatensystem

(folgt)

gerichteter Graph

(folgt)

Äquivalenzrelation

Reflexivität

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

Symmetrie

$ggtT(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

$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)

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

Es liegt keine Äquivalenzrelation vor!