Partielle Ordnung von " x teilt y " beweisen

Question

Ich bereite mich gerade auf die Prüfung vor und komme bei einem Relationsbeweis nicht ganz weiter:

Es sei die Relation \((\mathcal{P}_{90},\sim)\) gegeben, wobei \(\mathcal{P}_{90}=1,2,3,5,...,90\) die Teiler von 90 umfasst und $$x \sim y \Leftrightarrow x \text{ teilt } y.$$

a) Zeigen Sie, dass \((\mathcal{P}_{90},\sim)\) eine partielle Ordnung ist.

Dazu zeige ich, dass \((\mathcal{P}_{90},\sim)\) reflexiv, antisymmetrisch und transitiv ist.

Reflexiv: \( x \sim x\) Wahr, weil jede Zahl auch Teiler von sich selbst ist. \((x \sim x = 1)\)

Antisymmetrisch: \( x \sim y \land y \sim x \Rightarrow x = y \), also \( \left( x\mid y\right)  \land \left(y\mid x\right) \) dann muss natürlich \( x = y\) sein, aber wie kann ich das beweisen? So habe ich es ja einfach nur nach Definition aufgeschrieben und somit würde ich keine Punkte bekommen.

Transitiv: \( a \sim b \land c \sim d \Rightarrow a \sim c  \), also \( \left(a\mid b\right) \land \left(c\mid d\right) \implies a\mid c \)

Hier habe ich auch keinen richtigen Beweis, sondern nur die Definition "abgeschrieben". Das Einzige, was mir einfallen würde, wäre Gleichungen aufzustellen und somit zu zeigen, dass die Ordnung transitiv ist. z.B.:

\( a\mid b = x\)

\( c\mid d = y\)

\(\Rightarrow (a\mid b) \mid (c\mid d) = x\mid y\), was analog zu \(\left( a\mid b\right) \land \left(b\mid c\right) \implies a\mid c\) zu verstehen ist und somit beweist, dass \((\mathcal{P}_{90},\sim)\) transitiv ist?? (Oder ist das ein falscher Ansatz?)

Ich würde mich über schnelle Antworten freuen.

MfG

Doesbaddel

Answer 1

also x|y   ∧     y|x     dann muss natürlich x=yx=y sein, aber wie kann ich das beweisen?

x|y ==> Es gibt ein a∈ℕ  mit  x*a=y

y|x  ==> Es gibt ein b∈ℕ  mit  y*b=x

also wenn man 2 in 1 einsetzt   y*b*a=y

                                yba -y = 0

                                y *(ba-1) = 0

                            y = 0   oder  ba=1

Da y als Teiler von 90 größer 0 ist, bleibt ba=1

und das geht für natürliche Zahlen nur für b=a=1.

Also folgt aus  x*a=y  sofort   x=y.   q.e.d.

Bei c) ähnlich :

x|y ==> Es gibt ein a∈ℕ  mit  x*a=y

y|z  ==> Es gibt ein b∈ℕ  mit  y*b=z

==> (wie oben)  x*a*b = z  und mit a und b ist auch ab∈ℕ ,

Also gibt es ein c∈ℕ  (nämlich c=a*b) mit  x*c=z

==>    x | z.

Comments

Also nochmal für alle, Lu's Ansatz für "antisymmetrisch" verdient es auch nochmal angeschaut zu werden.

Answer 2

Antisymmetrisch: x∼y∧y∼x⇒x=y
x
y
y
x
x
y
, also x|y∧y|x
x
y
y
x
dann muss natürlich x=y
x
y
sein, aber wie kann ich das beweisen? So habe ich es ja einfach nur nach Definition aufgeschrieben und somit würde ich keine Punkte bekommen.

Wenn du Klartext verwendet hättest, könnte ich einfach reinschreiben.

Antisymmetrisch:

x∼y gdw. n*x = y, n € N (ohne 0)

==> y ≥ x 

y∼x gdw. m*y = x, m € N (ohne 0)

==> x ≥ y

Zusammen: "und"

==> y ≥ x und x≥ y

⇒x=y

Reflexiv: x∼x

Wahr, weil jede Zahl auch Teiler von sich selbst ist. 1*x = x, 1 € N(ohne 0) somit  x∼x . 

Comments

Danke Lu! Warum machst du keinen eigenen Beitrag? So kann ich dir gar keinen "Daumen hoch" geben, weil du "nur" kommentiert hast. ;(

---

Umgewandelt. Wollte nicht, dass du zum Schluss keine LaTeX-Antwort hast. :)

---

Oh, danke :D. Übrigens, schöner Ansatz bei der Antisymmetrie - macht durch und durch Sinn.

---

Man, ich kann nur eine Antwort als "Beste Antwort" markieren und jetzt kann ich es nicht mehr rückgängig machen. ;((