www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Aussagenlogik" - Wörter,Alphabet,überabzählbar
Wörter,Alphabet,überabzählbar < Aussagenlogik < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Wörter,Alphabet,überabzählbar: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:12 Mi 07.11.2007
Autor: susimarie

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.

        
Bezug
Wörter,Alphabet,überabzählbar: Antwort
Status: (Antwort) fertig Status 
Datum: 12:29 Mi 07.11.2007
Autor: generation...x

Schau mal []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).

Bezug
                
Bezug
Wörter,Alphabet,überabzählbar: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 12:45 Mi 07.11.2007
Autor: susimarie

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.

Bezug
                        
Bezug
Wörter,Alphabet,überabzählbar: Tipp
Status: (Antwort) fertig Status 
Datum: 13:31 Mi 07.11.2007
Autor: generation...x

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[...

Bezug
                                
Bezug
Wörter,Alphabet,überabzählbar: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:20 Mi 07.11.2007
Autor: susimarie

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....

Bezug
                                        
Bezug
Wörter,Alphabet,überabzählbar: Antwort
Status: (Antwort) fertig Status 
Datum: 21:36 Mi 07.11.2007
Autor: Hugo_Sanchez-Vicario

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


Bezug
                                                
Bezug
Wörter,Alphabet,überabzählbar: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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...

Bezug
                                                
Bezug
Wörter,Alphabet,überabzählbar: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 01:14 Do 08.11.2007
Autor: generation...x

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).

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Aussagenlogik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.vorhilfe.de