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.
, wobei ggT(m,n) den größen gemeinsamen Teiler der Zahlen m und n bezeichnet.
Theoretische Grundlagen (von mnemetz)[Bearbeiten | Quelltext 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.
- Jeder gemeinsamer Teiler teilt f, d.h.
- Gilt 1 = ggT(a,b), so heißen a und b relativ prim
Relation: Eine Relation ist - allgemein - eine "Verwandtschaftsbeziehung", formal dargestellt:
- Die Teilmenge
Äquivalenzrelation: Eine solche trifft zu, wenn von der Menge A folgende Eigenschaften erfüllt sind:
- Reflexivität:
- Symmetrie:
- Transitivität:
Lösungsvorschlag von mnemetz[Bearbeiten | Quelltext bearbeiten]
Cartestisches Koordinatensystem[Bearbeiten | Quelltext bearbeiten]
(folgt)
gerichteter Graph[Bearbeiten | Quelltext bearbeiten]
(folgt)
Äquivalenzrelation[Bearbeiten | Quelltext bearbeiten]
Reflexivität[Bearbeiten | Quelltext bearbeiten]
ist nicht gegeben (ausser m = 1)
Symmetrie[Bearbeiten | Quelltext bearbeiten]
ist gegeben, denn - die Reihenfolge von m und n ist nicht von Bedeutung
Transitivität[Bearbeiten | Quelltext bearbeiten]
ist nur bedingt gegeben, denn 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[Bearbeiten | Quelltext bearbeiten]
Es liegt keine Äquivalenzrelation vor!