Relation R, Teilergraph zeichnen

Question

Aufgabe:

Auf der Menge \( M_{n} \) der ersten \( n \) natürlichen Zahlen \( \{1, \ldots, n\} \) betrachten wir die folgende Relation \( R \) :
$$ R=\left\{(a, b) \in M_{n} \times M_{n} \mid \exists k \in \mathbb{N}: b=k \cdot a\right\} $$
(mit anderen Worten: \( a \) ist ein Teiler von \( b \) ). Das zu dieser Relation auf \( M_{n} \) gehörige Pfeildiagramm wird auch der Teilergraph von \( R \) genannt.
a) Zeichnen Sie den Teilergraphen zur Menge \( M_{6} \) und den Teilergraphen zur Menge \( M_{8} \).
b) Beweisen Sie: Die Relation \( R \) hat folgende Eigenschaften:
- \( R \) ist reflexiv,
- \( R \) ist transitiv.
Ist die Relation \( R \) symmetrisch?

Ansatz:

a) Muss ich hier die Zahlen von 1-8 nehmen (M₈) und dann die Zahlen von 1-6 (M₆) und dann schaue ich für welche Zahlen aus der Menge M8 durch die Zahlen der Menge M6 ein k aus den natürlichen Zahlen entsteht?

Also 1:1 = 1; 2:1=2 ; 2:2 = 1, 3:1 = 3, 3:3 = 1; 4:1 = 2 ; 4:2 = 2 ; 4:4 = 1; 5:1 = 5 ; 5:5 = 1; 6:1 = 6 ; 6:2 = 3 ; 6:3 = 2 ; 6:6 = 1,

7:1 = 7; 8:1 = 8, 8:2 = 4; 8:4 = 2

Und diese müsste ich mit Pfeilen darstellen oder? Also von der 8 bspw. geht ein Pfeil zur 1,2 und 4. Habe ich das richtig verstanden?

b) reflexiv, weil x in Relation zu y steht

transitiv → die Begründung verstehe ich nicht :( bitte helfen!

es ist nicht symmetrisch, da ich die Reihenfolge nicht ändern kann. Hinsichtlich der vorgegebene Relation ist (6,1) nicht dasselbe wie (1,6) oder?

Answer 1

Hallo :-)

Und diese müsste ich mit Pfeilen darstellen oder? Also von der 8 bspw. geht ein Pfeil zur 1,2 und 4. Habe ich das richtig verstanden?

Nicht ganz. Das Tupel \((a,b)\) ist per Definition genau dann in \(R\) enthalten, wenn \(a|b\) bzw. \(\exists \ k \in \mathbb{N}: \ b=k \cdot a\) gilt.

Es gilt offenbar \(8:1=8\), bzw. nach der Notation aus \(R\) die Gleichheit \(8=8\cdot 1\), also \(1|8\), sodass \((1,8)\in R\) gilt.

Also musst du schonmal eine gerichtete Kante (Pfeil) vom Knoten \(1\) zum Knoten \(8\) zeichnen.

reflexiv, weil x in Relation zu y steht

Nein. Weil \(x\) in Relation zu \(x\) steht. Begründe das formal mit der Definition der Relation \(R\).

transitiv → die Begründung verstehe ich nicht :( bitte helfen!

Betrachte \((a,b),(b,c)\in R\). Also gilt jeweils:

\(\exists \ k \in \mathbb{N}: \ b=k \cdot a\)   und  \(\exists \ l \in \mathbb{N}: \ c=l \cdot b\).

Was kannst du jetzt mit den beiden Gleichheiten miteinander machen.