Lineare Ordnung Logik

Neue Frage »

Lipton Auf diesen Beitrag antworten »
Lineare Ordnung Logik
Meine Frage:
a) Sei A ein Alphabet mit 100 Buchstaben. Gibt es eine lineare Ordnung < auf den Wörtern über A, so dass jedes Wort nur endlich viele < - Vorgänger hat.
b) Sei nun A ein abzählbar unendliches Alphabet. Gibt es eine lineare _Ordnung < auf den Wörtern über A, so dass jedes Wort nur endlich viele <-Vorgänger ha.t

Meine Ideen:
a) Ja, weil die Wörter über A abzählbar sind und hat jedes Wort nur endliche viele < - Vorgänger.
b) Nein, weil A abzählbar unendlich ist, gibt es auch unendlich viele Möglichkeiten Wörter darüber zu bilden, und es gibt nicht für jedes Wort endlich viele < - Vorgänger.
Mazze Auf diesen Beitrag antworten »

Zitat:
a) Ja, weil die Wörter über A abzählbar sind und hat jedes Wort nur endliche viele < - Vorgänger.


Das ist keine hinreichende Begründung. Betrachte etwa das Alphabet (a,b) und die Wörter W über diesem Alphabet. Dann definieren wir als Ordnung die alphabetische Ordnung. Dann gibt es Wörter die unendlich viele Vorgänger haben. Etwa hat das Wort

b

unendlich viele Vorgänger, nämlich

a
aa
aaa
aaaa
aaaaa
aaaaaa

usw.

Damit ist deine Antwort zu a) natürlich falsch. Es gibt allerdings eine solche Ordnung , überlege mal etwas, diese ist nicht schwer anzugeben.

b) Auch bei endlichen Alphabeten gibt es unendlich viele Möglichkeiten Wörter zu bilden. Das allein reicht nicht aus um endlich viele Vorgänger auszuschließen. Du musst ganz klar zwischen den beiden Eigenschaften unterscheiden.

Einmal hat das Alphabet unendlich viele Buchstaben. Einmal hat ein Wort endlich viele Vorgänger. Das sind zwei verschiedene Paar Schuhe.
Lipton Auf diesen Beitrag antworten »

Danke smile erstmal für deine Hilfe Tanzen

denk ich mir das jetzt richtig?
Also gibt es eine lineare Ordnung < über den Wörtern über A. Also < ist ja meine Fkt. und meine Menge sind die Wörter über dem Alphabet, wenn ich mir jetzt irgendein Wort rauspicke, dann hat das ja nur endlich viele Vorgänger also indem man einfach immer ein Buchstaben hinten wegnimmt zum Beispiel. Also gibt es eine lineare Ordnung über den Wörtern, denn es gibt zu jeder Funktion eine kleinste unter f abgeschlossene OBermenge von M.


Und wo is dann der Unterschied zu dem unendlichen Alphabet, denn da werden die Wörter ja dann auch nur unendlich oder werden die dadurch überabzählbar unendlich?
Mazze Auf diesen Beitrag antworten »

Zitat:
Also gibt es eine lineare Ordnung < über den Wörtern über A. Also < ist ja meine Fkt. und meine Menge sind die Wörter über dem Alphabet, wenn ich mir jetzt irgendein Wort rauspicke, dann hat das ja nur endlich viele Vorgänger also indem man einfach immer ein Buchstaben hinten wegnimmt zum Beispiel. Also gibt es eine lineare Ordnung über den Wörtern, denn es gibt zu jeder Funktion eine kleinste unter f abgeschlossene OBermenge von M.


Mir ist nicht ganz klar was Du meinst. Ja es gibt eine lineare Ordnung in der jedes Wort nur endlich viele Vorgänger hat, aber das ist hier noch nicht bewiesen. Die Ordnung ist entsprechend einfach. Nehmen wir an wir haben das Alphabet {a,b,c} , dann Ordnen wir die Wörter so :

a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
...

überlege dir welche Idee dieser Ordnung zugrunde liegt, und wende das auf das Alphabet mit den 100 Buchstaben an, dann hast Du die Ordnung.

Zitat:
Und wo is dann der Unterschied zu dem unendlichen Alphabet, denn da werden die Wörter ja dann auch nur unendlich oder werden die dadurch überabzählbar unendlich?


Solange das alphabet abzählbar bleibt, ist die Anzahl der endlichen Wörter auch abzählbar. Über die unendlichen langen Wörter muss ich in dem Fall mal kurz nachdenken.
Lipton Auf diesen Beitrag antworten »

also gibt es eine lineare ordnung wenn a<b<c<..... und gilt |w| < |w+1| d.h. egal welcher Buchstabe, wenn das Wort kürzer ist ist es kleiner und dadurch is es endlich?

Und für b) unendliches Alphabet gilt ja das gleiche oder?
Mazze Auf diesen Beitrag antworten »

Zitat:
d.h. egal welcher Buchstabe, wenn das Wort kürzer ist ist es kleiner und dadurch is es endlich?


Es geht hier nicht um die Endlichkeit von Wörtern sondern um die Endlichkeit einer bestimmten Menge, nämlich der Menge der Wörter die kleiner als ein Wort sind.

Zitat:
Und für b) unendliches Alphabet gilt ja das gleiche oder?


Eben nicht, nehmen wir an, wir haben ein unendliches Alphabet. Wir bezeichnen die Zeichen des Alphabets mit



usw.

Nehmen wir die obige Ordnung, die übrigens Standardordnung heißt. Wieviele Vorgänger hat dann das Wort



? Denke mal genau drüber nach.
 
 
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »