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.

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

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{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

Äquivalenzrelation

Äquivalenzrelation

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)

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

Cartestisches Koordinatensystem

6 | .       .
5 | . . . .   .
4 | .   .   .
3 | . .   . .
2 | .   .   .
1 | . . . . . .
---------------
  | 1 2 3 4 5 6

gerichteter Graph

(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

Reflexivität

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

Symmetrie

$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

$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

Es liegt keine Äquivalenzrelation vor!