Wörter,Alphabet,überabzählbar < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | (a)
Zeigen Sie mit Hilfe der Aussage [mm] \IN [/mm] x [mm] \IN [/mm] ist abzählbar, dass die Menge aller Wörter über einem abzählbaren Alphabet abzählbar ist.
(b)
Sei A mindestens 2-elementig. Zeigen Sie, dass [mm] A^\IN [/mm] überabzählbar ist. |
Hallo.
Ich höre zum ersten Mal Logik an der Uni und muss sagen, dass ich das alles unlogisch finde. Diese Aufgabe wurde mir bereits in der ersten Wochen gestellt und ich habe überhaupt keinen Ansatz, da mir diese ganzen Begriffe, wie Wörter und Alphabet nur aus dem Deutsch-Unterricht bekannt sind.
Es wäre daher wirklich super, wenn mir jemand zeigen könnte, wie ich bei diesen Aufgaben vorgehen muss um zum gewünschten Ergebnis zu gelangen.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Schau mal ![[]](/images/popup.gif) hier. Generell ist Wikipedia in solchen Fällen ziemlich hilfreich - was an Tiefe fehlen mag, wird durch Breite wettgemacht. Soll heißen: wenn man nur ein paar Brocken hat, kann man sich entlang der Querverweise weiterhangeln.
Zum Thema: Grob gesagt, ist ein Alphabet eine Menge von Elementen (z.B. Buchstaben) und ein Wort über diesem Alphabet ist dann eine endliche Folge von Elementen aus diesem Alphabet. Wie im richtigen Leben kommt es auf die Reihenfolge an.
Für die Aufgabe a) scheint mir wesentlich, dass Worte immer nur endlich lang sein dürfen, wenn auch beliebig lang.
Zur b) musst du dir überlegen, wie die Elemente von [mm]A^{\IN}[/mm] aussehen könnten. Nimm dir als Beispiel [mm]A=\{0, 1\}[/mm]. Vielleicht kennst du eine überabzählbare Menge, auf die [mm]A^{\IN}[/mm] sich bijektiv abbilden lässt... (also mir würde spontan eine einfallen).
|
|
|
| |
|
Hallo.
Danke für die schnelle Antwort. Habe mir das in der Wiki mal angeschaut und festgestellt, dass es ja doch nicht so kompliziert ist, wie am Anfang gedacht habe.
(a) Laut Definition handelt es sich bei "Einem Wort über die Menge A um eine
endliche Folge über A". Somit ist die Menge aller Wörter über der abzählbaren Menge A gleich mächtig zu [mm] \IN [/mm] und somit ist die Menge aller Wörter abzählbar.
(das kann es doch aber eigentlich nicht sein, oder?)
(b) Also ich war noch nie gut in finden von Abbildungen, die zu irgendeiner anderen Abbildung bijektiv sind. Vielleicht hast du da noch mal einen tipp für mich, in welcher Richtung ich suchen muss.
Dankeschön.
|
|
|
| |
|
Zur a)
Wie sieht die Menge der Wörter über A aus? Wörter der Länge 1 sind gerade A. Wörter der Länge 2 sind [mm]A \times A = A^2[/mm] usw. Vielleicht lässt sich aus der Voraussetzung etwas machen, wenn man sie 2mal anwendet - jeweils einmal für die Menge der Wörter der Länge n und am Schluss für die Folge der Wörter (*absichtlich-etwas-in-Rätseln-sprech*).
Zur b)
Denk mal an binäre Zahlen (daher mein Beispiel) und das (reelle und damit überabzählbare) Intervall [0, 1[...
|
|
|
| |
|
Hallo.
Habe jetzt den ganzen nachmittag versucht irgendetwas zusammen zu basteln, aber das klappt leider alles nicht.
(a) Die Wörter der Länge 1 sind A. Die Wörter der Länge 2 sind A x A = [mm] A^2. [/mm] Die Wörter der Länge 3 sind A x A x A = [mm] A^3. [/mm] Die Wörter der Länge n sind A x A x A x ... x A = [mm] A^n. [/mm] Weiter gilt die Menge aller Wörter ist gleich A [mm] \cup A^2 \cup A^3 \cup [/mm] ... [mm] \cup A^n [/mm] = ...
An dieser Stelle komme ich jetzt leider nicht weiter. Ich finde es eigentlich ligsch, aber ich habe keine Ahnung, wie ich das nun formal beweisen muss.
(b) Hier stehe ich leider immer noch völlig auf dem Schlauch....
|
|
|
| |
|
Hallo susimarie,
bei der Aufgabe a) darfst du davon ausgehen, das [mm]\IN\times\IN[/mm] abzählbar ist, dass man also die Mengen aller Paare [mm] (n_1,n_2) [/mm] von natürlichen Zahlen durchnummerieren kann. Diese Paarbildung kann man wiederholen, das war wohl mit dem "in Rätseln sprechen" gemeint.
Man hat ein spezielles Abzählverfahren benutzt, um von der Abzählbarkeit von Menge [mm] $M_1$ [/mm] und Menge [mm] $M_2$ [/mm] auf die Abzählbarkeit von [mm]M_1\times M_2[/mm] zu schließen.
Wir nehmen nun an, dass [mm]A\times A[/mm] abzählbar ist. Wenn man nun aufpasst und [mm]A\times A\times A[/mm] als [mm](A\times A)\times A[/mm] schreibt... na dann hat man mit der abzählbaren Menge [mm](A\times A)[/mm] als [mm] $M_1$ [/mm] und der abzählbaren Menge [mm]A[/mm] als [mm] $M_2$ [/mm] die Möglichkeit, den alten Beweis zu recykeln (recyclen? riesajkeln? ...egal) wieder zu verwenden. Und das geht auf diese Weise induktiv für die Menge aller endlichen Wörter.
Das war der erste Teil, bei Aufgabe b) musst du zeigen, dass es nicht geht, eine Abzählung von [mm] $A^{\IN}$ [/mm] anzugeben, einfach weil es keine gibt. Ein sehr interessanter Beweis stammt von Herrn Cantor und ist bei der deutschen Wikipedia zu finden: http://de.wikipedia.org/wiki/Cantors_zweites_Diagonalargument
Ein besseres Argument fällt mir momentan auch nicht ein.
Hugo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:02 Mi 07.11.2007 | | Autor: | susimarie |
Hallo.
Also den Teil (a) habe ich nun verstanden und das ganze ich auch logisch. Bei (b) tue ich mich noch ein wenig schwer, aber ich werde nochmal drüber schlafen...
|
|
|
| |
|
Richtig, so hatte ich das mit der a) gemeint. Es sei noch angemerkt, dass man eventuell (falls nicht in der Vorlesung passiert) zeigen muss, dass die abzählbare Vereinigung abzählbarer Mengen wieder abzählbar ist. Vom Argument her ist das aber auch nichts anderes als bei [mm]\IN \times \IN[/mm].
Zur b)
Wenn [mm]A=\{0 , 1 \}[/mm], dann ist [mm]A^{\IN}[/mm] die Menge aller unendlichen binären Folgen (ein Beispiel: [mm]\pmat{ 1 & 0 & 0 & 1 & \dots }[/mm]). Die lässt sich direkt mit dem Intervall [0, 1[ identifizieren, wenn man jeder Zahl in diesem Intervall ihre Binärdarstellung zuordnet und nur die Zahlen nach dem Komma betrachtet. Damit kann man eine Bijektion mit einer überabzählbaren Menge angeben (man hat natürlich z.z., dass es auch wirklich eine Bij. ist, aber das sollte nicht zu schwer sein).
|
|
|
|
