Aufgabe:
Sei R ⊆ N x N. Für die Relation R gilt: aRb <=> ggT(a,b) > 1.
Entscheide ob es sich um eine Äquivalenzrelation oder Halbordnung handelt.
Ansatz:
Damit die Relation eine Äquivakenzrelation ist, müsste sie reflexiv, symmetrisch und transitiv sein.
i) reflexiv: ∀ a ∈ N: a R a <=> ggT(a,a) > 1
Ich würde behaupten, die Relation ist reflexiv, da ja nur alle Tupel in der Relation liegen, die tatsächlich die Bedingung ggT(a,b) > 1 erfüllen, und ggT(a,a) ja die natürliche Zahl a sein müsste.
ii) symmetrisch: ∀ a,b ∈ R: aRb => bRa <=> ggT(a,b) => ggT(b,a)
Ich würde auch sagen, dass die Relation symmetrisch ist, denn wenn wenn es eine Zahl d für die gilt, dass d I a und d I b gilt, dann gilt ja auch d I b und d I a.
iii) transitiv: ∀ a,b,c ∈ R: aRb und bRc => aRc
Ich würde auch sagen, dass die Relation transitiv ist, da wenn d I a und d I b und d I b und d I c gilt, auch gelten muss, dass aRc ist.
Damit wäre die Relation ja dann eine Äquivalenzrelation.
Ich bin mir sehr sicher, dass meine Lösungen falsch sind, und ich weiß nicht wie ich an diese Aufgabe rangehen soll.
