Laut den Lösung ist sie jedoch nicht transitiv, warum?

Question

Guten Tag zusammen

Ich habe folgende Aufgabe:

Es sei Σ := {0, 1} und Σ^∗ die Menge aller endlichen Wörter über dem Alphabet Σ (inklusive des leeren Wortes ε). Wir betrachten die Relation R ⊆ Σ^∗ × Σ^∗ mit (x, y) ∈ R :⇔ x^rev = y , wobei x^rev das Wort bedeutet, das Sie erhalten, wenn Sie x von rechts nach links lesen.

Beispiel: Sei x = 11010. Dann ist x^rev = 01011.

Jetzt müssen wir bestimmen, ob diese Relation transitiv ist.

Lösungsversuch

Ich hätte ja gesagt, da es gar keine 3 Verbindungen gibt. Das heisst es gibt ja immer nur eine Verbindung zwischen zwei Werten z.B. 10 <--> 01, da gibt es gar nicht mehr. Daher hätte ich gesagt, durch die Aussagelogik ist dies wahr.

Laut den Lösung ist sie jedoch nicht transitiv, warum?

Vielen Dank im Voraus!

LG
Pfizer

Answer 1

Ich hätte ja gesagt, da es gar keine 3 Verbindungen gibt.

Du musst einfach nur drei Wörter denken x,y,z mit

x^rev = y  und y^rev=z

Dann folgt ja z=x

Es müsste bei "transitiv" aber folgen x^rev=z

Comments

mathef

Entschuldige, ich verstehe nicht den Punkt, welchen Sie mir klar machen wollen.

Die Regel besagt ja, dass eine Relation R transitiv heisst, wenn für alle x, y, z ∈ M gilt:

Aus (x,y) ∈ R und (y,z) ∈ R folgt (x,z) ∈ R

Das heisst zum Beispiel:

x = 10

y=01

Dann besteht ja zwischen x und y eine Relation. Es gibt jedoch weder für x oder für y ein z, welches für diese Relation in Frage kommt.

Oder muss ich das so interpretieren:

x^rev = 01

y=01

y^rev=10

z=10

Die Verbindung wäre ja dann von x^rev zu y und von y^rev zu z. Aber y^rev ist nicht der gleiche Punkt der Menge wie y oder verstehe ich hier etwas falsch?

Vielen Dank im Voraus

LG
Pfizer

---

Du hast das mit deinem Beispiel doch schon ganz gut

nachvollzogen.

Aus (x,y) ∈ R und (y,z) ∈ R folgt (x,z) ∈ R

Und wenn man jetzt mit x=10 beginnt

und sucht ein y, welches mit 10 in dieser Relation steht, dann

muss y=01 sein. Damit (y,z) ∈ R stimmt,

muss z=10 sein. Und wenn es transitiv wäre, dann müsste

jetzt (x,z) ∈ R gelten. Aber ( 10,10) ist nicht in der Relation,

also ist sie nicht transitiv.

---

Guten Tag mathef

Danke vielmals. Jetzt nur noch eine Frage: In Ihrem Beispiel ist x=10 und z=10. Ist das nicht so, dass in einer Menge die Elemente eindeutig sein müssen? Das heisst, dass die Nummer 10 gar nicht mehrmals vorkommen kann.

Vielen Dank im Voraus!

LG
Pfizer

---

Von einer Menge ist doch keine Rede. Es heißt bei "transitiv"

doch: Für alle x,y,z .... gilt.

Da können auch gleiche drunter sein.

---

Guten Tag mathef

Ich dachte eben, dass wir eine Relation aus einem kartesische Produkt von zwei Mengen erstellt wird.

LG
Pfizer

---

Das ist auch richtig. Dann bedeutet aber :

x steht in dieser Relation zu y

<=>   (x;y) ∈ R und R ist eben eine Teilmengen des ganzen

kartesischen Produktes; denn es heißt ja R ⊆ Σ∗ × Σ∗.

Das bedeutet: Manche Paare (x,y) gehören zur Relation und andere

eben nicht. Damit die Relation vernünftig definiert ist, muss man eben

sagen welche dazu gehören sollen. In deinem Fall ist das

geschehen durch   (x, y) ∈ R :⇔ x^rev = y.

Möglicherweise verwirrt dich, dass hier zu jedem x immer nur genau

ein y gehört ( solche Relationen nennt man auch Funktion).

Bei anderen ist das nicht so, etwa Die "kleiner" Relation für nat. Zahlen,

da gehören dann z.B. die Paare ( 2;3) , (2;4) , (2;5 ) ... dazu.

Zurück zu deinem Beispiel:

(10;01) ∈ R. ( also (x;y) )Wenn es um "transitiv" geht braucht man ein

zweites Paar, aber das muss mit y beginnen, also ( 01;?).

Für das ? klappt aber nur ?=10 damit das Paar in der Relation ist,

es muss also hier z=x gewählt werden, mit dem Ergebnis, dass

(x;z)∉R gilt .

Hoffentlich war das etwas verständlicher, sonst frag gerne nach.

---

Guten Tag

Danke vielmals. Entschuldige, dass ich mich so blöd anstellen. Mich verwirrt, wie sie es schon erkannt haben, dass hier zu jedem x immer nur genau ein y gehört (Funktion). Aber da diese Relation ja eine Funktion ist, gibt es ja zu jedem x nur ein y. Das heisst wir können ja gar keine Verbindung mit x,y und z herstellen. Somit ist doch durch die Aussagelogik definiert, dass diese Relation transitiv ist.

LG
Pfizer

---

Das heisst wir können ja gar keine Verbindung mit x,y und z herstellen

Das stimmt nicht.

Die müssen doch nicht unbedingt verschieden sein.

Z.B. die Gleichheitsrelation bei den reellen Zahlen ist

transitiv; denn x=y und y=z hat zur Folge  x=z.

Die sind dann eben alle gleich.