Abzählbare Mengen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:02 Mo 17.01.2005 | | Autor: | Ate |
Hallo,
ich bin vor folgende Aufgabe gestellt, für die ich auch eine Lösungsidee habe. Mein Problem dabei ist, dass mathematische Formulierungen sehr schwer für mich sind.
Darum geht es:
Gegeben sei ein Alphabet mit |[mm]\Sigma[/mm]|=1
F([mm]\Sigma[/mm]*) ist die Menge aller endlichen Teilmengen von [mm]\Sigma[/mm]*.
Ist F([mm]\Sigma[/mm]*) abzählbar?
Grundsätzlich gilt ja, dass F([mm]\Sigma[/mm]*) abzählbar ist, wenn eine totale und bijektive Abbildung existiert f: F([mm]\Sigma[/mm]*)[mm]\to N_{0}[/mm] , die jedem Element, in dem Fall jeder endlichen Sprache als Teilmenge von F([mm]\Sigma[/mm]*) eine natürliche Zahl zuordnet.
Schaue ich mir die Teilmengen an, so sind sie entweder leer oder bestehen aus einer Menge von Wörtern, die alle aus dem gleichen Buchstaben bestehen und sich nur in der Länge unterscheiden. Könnte ich den Symbolen aus [mm]\Sigma[/mm]* nicht immer eine Binärzahl zuordnen um sie abzuzählen, z.B. a wäre 1, aa wäre 10, aaa wäre 110 usw.
Dann könnte man eine Teilmenge binär beschreiben, der Binärzahl die ihr entsprechende natürliche Zahl zuweisen und dann könnte man das Ganze abzählen.
Oje, kann das überhaupt jemand verstehen, wie ich das geschrieben habe? Und wie bringe ich das in eine mathematische Ausdrucksweise?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:13 Mo 17.01.2005 | | Autor: | DaMenge |
hi Ate,
leider hast du nicht beschrieben, was Sigma* sein soll - also was dieses Stern bedeuten soll.
noch ein Hinweis: jedes endliche Wort kann man über sein Länge eindeutig erkennen, also wenn dein Zeichen jetzt mal "A" ist, dann kann man natürlich {AA, AAA, AAAAA}={2,3,5} setzen...
aber dennoch wäre es interessant zu erfahren, was der Stern bedeuten soll !
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:27 Mo 17.01.2005 | | Autor: | Ate |
Hi DaMenge,
ich dachte, das ist so ein geläufiger Ausdruck ...
Also bei unserem Prof ist [mm]\Sigma[/mm]* die Menge aller Wörter, die über dem Alphabet [mm]\Sigma[/mm] gebildet werden kann,
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:34 Mo 17.01.2005 | | Autor: | Ate |
Hallo,
in diesem Fall bekomme ich keine totale bijektive Funktion hin, oder?
> noch ein Hinweis: jedes endliche Wort kann man über sein
> Länge eindeutig erkennen, also wenn dein Zeichen jetzt mal
> "A" ist, dann kann man natürlich {AA, AAA, AAAAA}={2,3,5}
> setzen...
>
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:43 Mo 17.01.2005 | | Autor: | DaMenge |
Hi Ate,
ich antworte mal hier (auch auf deine Mitteilungen).
Also wenn Sigma Stern die Menge aller Wörter ist und ich schon gesagt habe, dass du jedem Wort mittels seiner Länge eindeutig (weil es nur ein Zeichen also ein Wort mit bestimmter Länge gibt) eine natürliche Zahl zuordnen kannst ist Sigma Stern isomorph zu den natürlichen Zahlen (mit 0 für das leere Wort).
F soll dann die Menge der endlichen Teilmenge sein?
also praktisch gesehen ist das dann die Potenzmenge von den natürlichen Zahlen - und das diese überabzählbar ist, kannst du entweder voraussetzen oder überall nachlesen.
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:01 Mo 17.01.2005 | | Autor: | Ate |
>
> Also wenn Sigma Stern die Menge aller Wörter ist und ich
> schon gesagt habe, dass du jedem Wort mittels seiner Länge
> eindeutig (weil es nur ein Zeichen also ein Wort mit
> bestimmter Länge gibt) eine natürliche Zahl zuordnen kannst
> ist Sigma Stern isomorph zu den natürlichen Zahlen (mit 0
> für das leere Wort).
>
Ich denke mir aber Folgendes: es geht doch nicht um einzelne Wörter, sondern um Teilmengen, in denen Wörter unterschiedlicher Länge sein können. Und ich muss doch die Abzählbarkeit der Teilmengen beweisen. Soll ich dann die Länge der Wörter in einer solchen Teilmenge einfach aufgrund addieren? Das ist dann aber nicht total und bijektiv.
> F soll dann die Menge der endlichen Teilmenge sein?
> also praktisch gesehen ist das dann die Potenzmenge von
> den natürlichen Zahlen - und das diese überabzählbar ist,
> kannst du entweder voraussetzen oder überall nachlesen.
>
> viele Grüße
> DaMenge
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:46 Mo 17.01.2005 | | Autor: | DaMenge |
Hi,
also eine solche Teilmenge wäre doch:
{ AA , AAAAA, AAAAAAAAAAA, AAAAAAAAAAAAA}
aber solche Teilmenge können beliebig lang werden (aber endlich), deshlab wäre doch eine Darstellung:
{2,5,11,13} besser, oder?
es ist nur eine andere Darstellung ! Sonst nichts
so, und deine Aufgabe ist nun zu entscheiden, ob die Anzahl der Teilmengen abzählbar ist, also
ob es abzählbar viele {1} {1,2} {1,2,3} {2,3} {2} usw
gibt - dies ist aber gerade die Potenzmenge von IN !
hattet ihr die schon? und deren abzählbarkeit?
viele grüße
DaMenge
btw: bin heut abend nicht mehr on
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:06 Di 18.01.2005 | | Autor: | Ate |
Hi,
das Ersetzen mit den natürlichen Zahlen leuchtet mir ein (nebenbei gefragt: das geht aber auch nur, weil die Anzahl = 1 ist, oder?). Und ich weiß (in der Theorie) auch, dass die Potenzmenge P (N) überabzählbar ist.
Aber: P ist doch definiert als die Menge aller Teilmengen einer Menge M. Das heißt ja eigentlich die endlichen und unendlichen Teilmengen, oder? In meiner Aufgabe ist aber gefragt nach der Menge aller endlichen Teilmengen. Was mache ich damit?
Ich glaube, ich werde das nie verstehen...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:55 Mi 19.01.2005 | | Autor: | Hexe |
So ich hab mir da mal gedanken macht und meine Die Menge ist abzählbar, weil man sie bijektiv auf [mm] \IQ [/mm] abbilden kann und das ist abzählbar.
Also Mengen mit einem Wort werden den ganzen Zahlen zugeordnet, der Länge des betroffenen Wortes nach. Mengen aus zwei Wörtern werden den Halben Zahlen zugeordnet nach {1,2} ist 1/2, {1,3} ist 3/2, {2,3} ist 5/2 {1,4} ist 7/2 und so weiter . Allgemein werden Mengen mit n Wörtern den Brüchen vom Nenner n zugeordnet wobei nur gekürzte Brüche verwendet werden.
|
|
|
|
