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.