Question

Reflexiver transitiver Abschluss einer Relation

Text erkannt:

b) Berechnen Sie den reflexiven und transitiven Abschluss \( S \) von
\( R:=\{(x, y) \in \mathbb{Z} \times \mathbb{Z} \mid y=x+2\} . \)
Zeigen oder widerlegen Sie: \( S \) ist eine totale Ordnung (5 Punkte).

Hallo, wüsste wer wie ich da anfangen könnte?

Answer 1

Hat vielleicht S etwas mit der Kongruenz modulo 2 zu tun?

Bedenke aber, dass S wohl nicht symmetrisch ist !

Es riecht eher nach einer Ordnungsrelation ....

Comments

Ich hätte gedacht dass in S alle Paare entweder Paare ungerader bzw Paare gerader Zahlen sind aus Z.

Das mit dem symmetrisch hab ich auch schon bemerkt, heisst es ist weder Quasi-, partielle, totale Ordnung oder Äquivalenzrelation, da für all diese Symmetrie erforderlich ist.

---

Bei einer Totalordnung sind je zwei Elemente

vergleichbar. Wie ist es hier mit x=1 und y=2 ?

---

Hm 1 und 2 wären ja dann eben kein Tupel sondern wenn dann (0,2) oder (1,3) oder nicht? Eine totalordnung kann es ja aber definitiv wegen mangelnder symmetrie nicht sein dachte ich

---

Eine Totalordnung ist nicht symmetrisch !

---

sorry dann hab ichs mit der antisymmetrie verwechselt. dann wäre es ja antisymmetrisch, transitiv aber nicht reflexiv, heisst es würde die anforderungen der partiellen ordnung nicht erfüllen und somit auch nicht die einer totalen ordnung?

---

S ist doch per Definition reflexiv!

---

Ach stimmtttt, das hab ich einfach übersehen. also ich würde dann schreiben:  S beinhaltet alle Paare von 2 geraden bzw 2 ungeraden Zahlen in Z

S ist als transitive reflexive hülle transitiv, reflexiv und antisymmetrisch da es den fall a R b und b R a nicht gibt, somit a = b für a, b element Z. Es erfüllt somit die Anforderungen einer partiellen Ordnung.

Zudem gilt für alle a,b element Z, dass a R b. also totale Ordnung.

---

Was die Antisymmetrie angeht, gebe ich dir Recht.

Aber

Zudem gilt für alle a,b element Z, dass a R b. also totale Ordnung.

kann ich nicht einsehen.

---

aber für jedes a element ganzer zahlen gilt doch dass es ein b gibt sodass b = a + 2? auch für negative zahlen

---

Es ist \((1,2)\notin S\). Deine Aussage ist daher für

\(a=1, \; b=2\) falsch.

---

mirs noch eingefallen dass das wegen der transitiven hülle auch nicht geht da zb

(1,3) und (3,5) enthalten wären aber 1 steht nicht in relation zu 5 da 5 nicht 1+2 ist.

heisst insgesamt keine totale ordnung?

---

Es geht doch um \(S\):

In der transitiven Hülle ist Transitivität erzwungen, also

\((x,y)\in S\iff y=x+2k\) für \(k\in \mathbb{N}\).

---

aber genau wegen dieser transitivität geht ja dann die totalität nicht? und wieso auf einmal das k es ist doch y definiert als x+2 ? oder ist das dann in S als summe von y und vielfaches von 2?

---

und wieso auf einmal das k es ist doch y definiert als x+2

\(S\) ist die transitive Hülle von \(R\):

\((x,y)\in R\wedge (y,z)\in R\Rightarrow (x,.z)\in S\),also

\(y=x+2\; \wedge \; z=y+2\Rightarrow z=x+2\cdot 2=x+4\), etc...

---

macht sinn. aber dann gilt doch die totalität? denn jedes a hat ein b mit dem es in relation steht denn für totalität muss doch gelten: a R b ∨ b R a

---

Aber hier ist doch \((1,2)\notin S\; \wedge (2,1)\notin S\),

also sind 1 und 2 nicht vergleichbar.

---

wenn diese paare nicht in S enthalten sind wieso betrachte ich sie denn dann? ich muss doch die totalität für die tupel enthalten in S anschauen?

---

Nein: ich muss zeigen, dass für jedes Paar

\(a,b\in \mathbb{Z}\) entweder \((a,b)\in S\) oder \((b,a)\in S\) ist.

Es geht um eine Totalordnung in der Grundmenge \(\mathbb{Z}\)

und die Frage ist hier, ob \(\mathbb{Z}\) durch \(S\)

total geordnet wird oder nicht.

---

ah also totalität wäre wenn ich die relation von S auf die allgemeine menge Z übertragen kann und es dann immer noch gilt?

---

Ja. So wie bei der Reflexivität.

---

ahhh okay... heisst ich kann insgesamt sagen dass S eine partielle aber nicht totale Ordnung ist.

vielen vielen dank! :)

---

heisst ich kann insgesamt sagen dass S eine partielle aber nicht totale Ordnung ist.

Ja.