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

Aus VoWi
Zur Navigation springen Zur Suche springen

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:

  1. Reflexivität:
  2. Symmetrie:
  3. 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!