TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 115
Stellen Sie die folgende Relation im kartesischen 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.
{{Beispiel|1= Angabetext }}
oder
{{Beispiel| Angabetext }}
zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)
{{Beispiel|status=solved|1= Angabetext }}
Hilfreiches[Bearbeiten | Quelltext bearbeiten]
Äquivalenzrelation[Bearbeiten | Quelltext bearbeiten]
Eine binäre Relation R auf einer Menge A heißt Äquivalenzrelation, wenn folgende drei Eigenschaften erfüllt sind:
Reflexivität: ,
Symmetrie: ,
Transitivität: .
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 d, 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]
6 | . . 5 | . . . . . 4 | . . . 3 | . . . . 2 | . . . 1 | . . . . . . --------------- | 1 2 3 4 5 6
gerichteter Graph[Bearbeiten | Quelltext 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 | 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) //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 | Quelltext bearbeiten]
Es liegt keine Äquivalenzrelation vor!