| |
| Autor |
  Abzählbarkeit und Überabzählbarkeit |
|
X3nion
Aktiv 
Dabei seit: 17.04.2014
Mitteilungen: 1053
 |  Themenstart: 2021-10-16
|
Hallo zusammen,
folgende Aufgabe beschäftigt mich gerade:
Für die Menge $B = \{a,b,c,...,z\}$ von Buchstaben bezeichnet
$$W = \{(b_1,b_2,...,b_n) \; | \; n \in \mathbb{N}, b_i \in B\}$$
die Menge der Wörter (ohne Umlaute).
a) Die Menge $W$ ist abzählbar.
b) Ist die Menge der möglichen Sätze (das sind endliche Folgen von Wörtern), die aus den Wörtern in $W$ gebildet werden, endlich, abzählbar unendlich oder überabzählbar?
- - - - - - - - - - - - - - -
Nun ich möchte mich erst einmal an a) herantasten. Hierzu muss ja eine Bijektion gefunden werden zwischen den natürlichen Zahlen und $W$ gefunden werden.
Besteht $W$ nur aus einem Buchstaben, so kann ja die 1 auf das a, die 2 auf das b, ... und die 26 auf das z abgebildet werden.
Besteht $W$ aus 2 Buchstaben, so bilden wir die 27 auf aa, die 28 auf ab usw. ab.
Wäre der Gedankengang soweit richtig?
Und wie würde die allgemeine Bijektion aussehen für ein beliebiges $n$, also $n$ Buchstaben? Hier weiß ich nicht weiter.
Wie immer bin ich euch für jede Hilfe dankbar!
Viele Grüße,
X3nion
|
 Profil
|
Diophant
Senior 
Dabei seit: 18.01.2019
Mitteilungen: 10686
Wohnort: Rosenfeld, BW
 | Beitrag No.1, eingetragen 2021-10-16
|
Hallo X3nion,
dein Gedankengang bei der a) ist goldrichtig. Wie man das am besten notiert, da fällt mir allerdings momentan auch nichts gescheites ein.
Kennst du Hilberts Hotel? Im Prinzip ist es hier eine ähnliche Situation wie dort mit den unendlich vielen Bussen. Nur dass die Busse bei dir jeweils 'nur' endlich viele Fahrgäste haben...
Gruß, Diophant
|
Profil
|
Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1860
 | Beitrag No.2, eingetragen 2021-10-16
|
Tipp: Dezimalsystem vs. Basis 26.
|
Profil
|
cramilu
Aktiv
Dabei seit: 09.06.2019
Mitteilungen: 2250
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
 | Beitrag No.3, eingetragen 2021-10-16
|
Hallo X3nion,
Kezer hatte schon den Weg gewiesen:
Sei jeweils \(n=\vert W\vert\) die aktuelle Wortlänge.
Anzahl der Wörter der Länge \(1\) : \(26^1\:=\:26\)
Anzahl der Wörter der Längen \(1\) oder \(2\) :
\(26^2\,+\,26^1\:=\:676\,+26\:=702\)
Anzahl der Wörter der Längen \(1\), \(2\) oder \(3\) :
\(26^3\,+\,26^2\,+\,26^1\:=\:17.576\,+\,676\,+26\:=18.278\)
usw.
Also für den "Wert" eines Wortes zunächst
seine Wortlänge \(n=\vert W\vert\) bestimmen,
dann als "Grundwert" die entsprechende Potenzsumme
bis \((w-1)\) ansetzen und um \(1\) erhöhen,
denn »aaa..a« bekommt grundsätzlich den "Eigenwert" \(0\)!
Diesen "Eigenwert" bestimmen:
Den Buchstaben »a« bis »z« Zahlenwerte von \(0\) bis \(25\)
zuordnen und damit die Summe der einzelnen "Stellenwerte"
ermitteln.
"Grundwert" + "Eigenwert" = "Wortwert"
Die Formalisierung ist in der Tat aufwändig!
EDIT
»schlau« hätte als "erhöhten Grundwert"
\(26^5+26^4+26^3+26^2+26+1\:=\:12.356.631\)
und als "Eigenwert"
\(20[u]\cdot26^0+0[a]\cdot26^1+11[l]\cdot26^3+7[h]\cdot26^4+2[c]\cdot26^5+18[s]\cdot25^6\:=\) ...
... \(=\:214.909.208\) ;
also zusammen den eindeutigen "Wortwert" \(227.265.839\) 😎
Sprachlich schön: Der "Wortwert" von »dumm« ist geringer! 😉
EDIT EDIT
Ich hätte Teil »a)« ja dreist als Feststellung
bzw. Vorgabe verstanden. Schließlich steht da
weder »Zeige: ...« noch »Ist \(W\) abzählbar?«.
|
Profil
|
Diophant
Senior
Dabei seit: 18.01.2019
Mitteilungen: 10686
Wohnort: Rosenfeld, BW
| Beitrag No.4, eingetragen 2021-10-16
|
\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}}
\newcommand{\ea}{\end{aligned}}
\newcommand{\bc}{\begin{cases}}
\newcommand{\ec}{\end{cases}}
\newcommand{\bpm}{\begin{pmatrix}}
\newcommand{\epm}{\end{pmatrix}}
\newcommand{\bvm}{\begin{vmatrix}}
\newcommand{\evm}{\end{vmatrix}}
\newcommand{\mb}[1]{\mathbb{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\mf}[1]{\mathfrak{#1}}
\newcommand{\ms}[1]{\mathscr{#1}}
\newcommand{\on}{\operatorname}
\newcommand{\ds}{\displaystyle}\)
@cramilu:
\quoteon(2021-10-16 14:19 - cramilu in Beitrag No. 3)
Die Formalisierung ist in der Tat aufwändig!
\quoteoff
nein, im Gegenteil. Mit dem Tipp von Kezer ist sie denkbar einfach: die Beschaffenheit der gesuchen Bijektion hatte X3nion ja schon richtig beschrieben und der Formalismus ist einfach \(n_{10}\mapsto n_{26}\) (was offensichtlich ebenfalls bijektiv ist).
Gruß, Diophant\(\endgroup\)
|
Profil
|
X3nion
Aktiv
Dabei seit: 17.04.2014
Mitteilungen: 1053
| Beitrag No.5, vom Themenstarter, eingetragen 2021-10-16
|
Hallo zusammen und vielen Dank für eure Antworten und Ausführungen! :)
@Diophant: Könntest du deine Variante vielleicht etwas näher ausführen? Also was du mit $n_{10} \to n_{26}$ meinst?
Viele Grüße,
X3nion
|
Profil
|
Diophant
Senior
Dabei seit: 18.01.2019
Mitteilungen: 10686
Wohnort: Rosenfeld, BW
| Beitrag No.6, eingetragen 2021-10-16
|
Hallo X3nion,
die Tatsache allein, dass man jedem Wort eindeutig eine Nummer zuordnen kann, ist ja schon der Beweis der Abzählbarkeit*.
Indem man diese Nummer im 26er-System (anstatt im Dezimalsystem) notiert, unterstreicht man das auf der einen Seite, da man an der Stellenzahl der betreffenden Nummer jetzt die Wortlänge ablesen kann, auf der anderen Seite hat man etwas greifbares, um die Bijektion kompakt zu notieren.
* Vergleiche mit Hilberts Hotel: bei den unendlich vielen Bussen mit jeweis abzählbar vielen Fahrgästen braucht es ja dann das erste Diagonalverfahren, hier ist das nicht notwendig.
Gruß, Diophant
|
Profil
|
X3nion
Aktiv
Dabei seit: 17.04.2014
Mitteilungen: 1053
| Beitrag No.7, vom Themenstarter, eingetragen 2021-10-16
|
Ich glaube ein Beispiel wäre ganz gut, nehmen wir einmal (acb)
Dann haben wir ja $2 \cdot 26^0 + 3 \cdot 26^1 + 1 \cdot 26^2$ und kommen somit zum gewünschten Wort, wenn wir $2$, $1$ und $1$ als jeweilige Stellenwerte der Buchstaben a c und b nehmen.
Aber wie würde man dies nun formal korrekt aufschreiben?
Einfach die Stellenposition des Buchstabens mit $N(b_i)$ für $1 \le i \le n$ betrachten (also bei abc ist $N(b_2) = 1$, $N(b_1) = 2$ und $N(b_0) = 3$), und dann betrachtet man bei einem gegebenen Wort $b_{n}b_{n-1}...b_1b_0$ die Platznummer $\sum \limits_{i=0}^n 26^i N(b_i)$?
Mir scheint das etwas kurz als Formalität, oder was meint ihr?
Viele Grüße,
X3nion
|
Profil
|
zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 4638
 | Beitrag No.8, eingetragen 2021-10-16
|
Steht eigentlich der Satz, dass höchstens abzählbare Vereinigungen höchstens abzählbarer Mengen höchstens abzählbar sind, schon zur Verfügung?
|
Profil
|
Diophant
Senior
Dabei seit: 18.01.2019
Mitteilungen: 10686
Wohnort: Rosenfeld, BW
| Beitrag No.9, eingetragen 2021-10-16
|
Hallo X3nion,
hier hatte ich mich geirrt, sorry.
Gruß, Diophant
[Die Antwort wurde nach Beitrag No.7 begonnen.]
|
Profil
|
cramilu
Aktiv
Dabei seit: 09.06.2019
Mitteilungen: 2250
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
| Beitrag No.10, eingetragen 2021-10-16
|
X3nion,
wenn Du als Beispiele (a), (z), (aa), (zz),
(aaa), (zzz) und (aaaa) wählst, und es dann
bei den Platznummern keine "Überschneidungen"
gibt - "Lücken" sind erlaubt! - hast Du's.
Dein vorgestellter Formalismus sollte dem genügen,
wie ich nach grober Prüfung meine...
[Die Antwort wurde nach Beitrag No.8 begonnen.]
|
Profil
|
X3nion
Aktiv
Dabei seit: 17.04.2014
Mitteilungen: 1053
| Beitrag No.11, vom Themenstarter, eingetragen 2021-10-16
|
Hallo zusammen,
@zippy: Nein, der Satz steht leider nicht zur Verfügung :|
Ich wollte nun Aufgabenteil b) bearbeiten, aber hier weiß ich nicht sicher, welche Aussage denn stimmt. Ich tippe auf Aussage 3, also überabzählbar unendlich, denn jeder Satz ist bereits abzählbar unendlich, aber jede Möglichkeit an Sätzen sollte überabzählbar sein?
Viele Grüße,
X3nion
|
Profil
|
Diophant
Senior
Dabei seit: 18.01.2019
Mitteilungen: 10686
Wohnort: Rosenfeld, BW
| Beitrag No.12, eingetragen 2021-10-16
|
\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}}
\newcommand{\ea}{\end{aligned}}
\newcommand{\bc}{\begin{cases}}
\newcommand{\ec}{\end{cases}}
\newcommand{\bpm}{\begin{pmatrix}}
\newcommand{\epm}{\end{pmatrix}}
\newcommand{\bvm}{\begin{vmatrix}}
\newcommand{\evm}{\end{vmatrix}}
\newcommand{\mb}[1]{\mathbb{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\mf}[1]{\mathfrak{#1}}
\newcommand{\ms}[1]{\mathscr{#1}}
\newcommand{\on}{\operatorname}
\newcommand{\ds}{\displaystyle}\)
Hallo X3nion,
nachdem der Teil a) jetzt soweit geklärt ist, kannst du ja als gesichert annehmen, dass jedes mögliche Wort aus \(W\) eine eindeutige Nummer aus \(\IN\) hat.
Sätze mit endlich vielen Wörtern sind also wieder endliche Ziffernfolgen aus den Ziffern 0 bis 9 oder wahlweise 0 bis 25. Diese Ziffernfolgen lassen sich sicherlich wieder irgendwie ordnen, zur Not lexikografisch, also ist die Menge dieser Ziffernfolgen selbst wieder abzählbar.
Die ganze Aufgabe kreist ja irgendwie um das erste Cantorsche Diagonalverfahren (daher auch mein Link zu der Geschichte mit dem Hilbertschen Hotel). In welchem Zusammenhang stellt sich dir die Aufgabe denn?
Gruß, Diophant\(\endgroup\)
|
Profil
|
zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 4638
| Beitrag No.13, eingetragen 2021-10-16
|
Du kannst den Teil b) auf den Teil a) zurückführen, indem du das Alphabet $\widetilde B=B\cup\{\,|\,\}$ betrachtest und $|$ als Worttrenner interpretierst.
(Wobei ich hier davon ausgegangen bin, dass $W$ auch das leere Wort enthält bzw. dass bei dir $0\in\mathbb N$ ist.)
|
Profil
|
X3nion
Aktiv
Dabei seit: 17.04.2014
Mitteilungen: 1053
| Beitrag No.14, vom Themenstarter, eingetragen 2021-10-16
|
Hallo Diophant,
die Aufgabe ist im Kontext einer Maß- und Integrationstheorie Vorlesung und mengentheoretischen Vorüberlegungen.
Das was du sagst ergibt Sinn, also dass jedes Wort mit genau einer natürlichen Zahl korrespondiert und ein Satz als endliche Anzahl von Wörtern ist abzählbar unendlich.
Was ist aber nicht ganz verstehe ist, wieso dann alle möglichen Sätze auch abzählbar unendlich sind, weil das können ja ganz schön viele werden.
Viele Grüße,
X3nion
[Die Antwort wurde nach Beitrag No.12 begonnen.]
|
Profil
|
X3nion
Aktiv
Dabei seit: 17.04.2014
Mitteilungen: 1053
| Beitrag No.15, vom Themenstarter, eingetragen 2021-10-16
|
@zippy Stimmt du hast Recht! So kommt man wirklich auf alle Varianten an endlichen Sätzen, einfach als Wort mit Trennung welches n-Stellen lang ist!
Betrachten wir das Alphabet $\tilde{B}:= B \cup \{|\}$. Nach Aufgabenteil a) ist die Menge an Buchstaben mit n Zeichen abzählbar unendlich, und somit ist auch die Menge an n Wörtern, getrennt mit |, was nichts anderes ist als ein endlicher Satz, abzählbar unendlich.
Würde das dann als kurze Begründung so ausreichen?
Viele Grüße,
X3nion
|
Profil
|
zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 4638
| Beitrag No.16, eingetragen 2021-10-16
|
\quoteon(2021-10-16 16:49 - X3nion in Beitrag No. 11)
@zippy: Nein, der Satz steht leider nicht zur Verfügung :|
\quoteoff
Ich hatte gefragt, weil man diese Aufgabe samt Musterlösung von 2018 im Web findet und dort für a) und b) dieser Satz herangezogen wird.
[Die Antwort wurde nach Beitrag No.14 begonnen.]
|
Profil
|
zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 4638
| Beitrag No.17, eingetragen 2021-10-16
|
\quoteon(2021-10-16 17:45 - X3nion in Beitrag No. 15)
Würde das dann als kurze Begründung so ausreichen?
\quoteoff
Wichtig ist, dass du die Aussage in a) nicht für ein bestimmtes $n$, sondern für alle endlichen Alphabete gezeigt hast (denn jetzt geht es ja um den Fall $n+1$) und dass ein Wort über $\widetilde B$ ein Satz über $W$ ist.
|
Profil
|
X3nion
Aktiv
Dabei seit: 17.04.2014
Mitteilungen: 1053
| Beitrag No.18, vom Themenstarter, eingetragen 2021-10-16
|
Hey zippy,
ahh okay, ja aber ich sehe die Musterlösung ist von einer ganz anderen Uni.
Hmm wie meinst du das mit n+1? Ich dachte ein Satz ist nichts anderes als ein ganz langes Wort (halt noch getrennt), und deshalb ist der Satz in $B$ enthalten und kann bijektiv auf eine natürliche Zahl abgebildet werden, so wie ich es in a) gemacht habe?
Viele Grüße,
X3nion
|
Profil
|
Diophant
Senior
Dabei seit: 18.01.2019
Mitteilungen: 10686
Wohnort: Rosenfeld, BW
| Beitrag No.19, eingetragen 2021-10-16
|
Hallo X3nion,
meine persönliche Meinung zur Frage dieser Musterlösung (wobei sich meine paar Mathe-Semester Anfang den 90er-Jahren abgespielt haben und sich das eine oder andere am Aufbau des Studiums seither vermutlich geändert hat): Maßtheorie macht man doch normalerweise in einer Veranstaltung namens Analysis 3 o.ä.? Der von zippy in #8 angeführte Sachverhalt ist aber elementare Mengenlehre und sollte auch heutzutage Stoff aus dem 1. Semester sein. Von daher würde ich mich hier soweit aus dem Fenster lehnen um zu sagen: das darf dann vermutlich auch bei euch vorausgesetzt und verwendet werden.
Gruß, Diophant
|
Profil
|
X3nion
Aktiv
Dabei seit: 17.04.2014
Mitteilungen: 1053
| Beitrag No.20, vom Themenstarter, eingetragen 2021-10-16
|
Hallo Diophant,
hmm okay, wie würde eine Lösung dann mit der von zippy vorgeschlagenen Variante aussehen?
Viele Grüße,
X3nion
|
Profil
|
Diophant
Senior
Dabei seit: 18.01.2019
Mitteilungen: 10686
Wohnort: Rosenfeld, BW
| Beitrag No.21, eingetragen 2021-10-16
|
\(\begingroup\)\(\newcommand{\ba}{\begin{aligned}}
\newcommand{\ea}{\end{aligned}}
\newcommand{\bc}{\begin{cases}}
\newcommand{\ec}{\end{cases}}
\newcommand{\bpm}{\begin{pmatrix}}
\newcommand{\epm}{\end{pmatrix}}
\newcommand{\bvm}{\begin{vmatrix}}
\newcommand{\evm}{\end{vmatrix}}
\newcommand{\mb}[1]{\mathbb{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\mf}[1]{\mathfrak{#1}}
\newcommand{\ms}[1]{\mathscr{#1}}
\newcommand{\on}{\operatorname}
\newcommand{\ds}{\displaystyle}\)
Hallo X3nion,
Teil a): \(B\) ist endlich. \(W\) besteht aus einer Vereinigung von abzählbaren Auflistungen aus Elementen der Menge \(B\). Da man die Wörter lexikografisch ordnen kann, ist auch diese Vereinigung abzählbar. Also ist \(W\) abzählbar.
Teil b): geht sinngemäß genauso. Nur dass du jetzt mit \(W\) eine abzählbare Menge als Grundmenge hast. Aber nach a) ist die Menge der Wörter abzählbar und die Sätze bestehen aus endlich vielen Wörtern, also ist auch hier die Vereinigung wieder abzählbar.
Sinngemäß so, vielleicht kann man es noch einfacher/zielführender formulieren.
PS: schön, mal wieder von dir zu lesen!
Gruß, Diophant\(\endgroup\)
|
Profil
|
zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 4638
| Beitrag No.22, eingetragen 2021-10-16
|
\quoteon(2021-10-16 19:18 - X3nion in Beitrag No. 20)
wie würde eine Lösung dann mit der von zippy vorgeschlagenen Variante aussehen?
\quoteoff
Bei a) steht die Lösung quasi schon in der Aufgabenstellung:$$
W = \bigcup_{n\in\mathbb N}B^n \;,\quad
B^n = \bigl\{(b_1,b_2,...,b_n) : b_i \in B\bigr\} \;.
$$Da $B$ endlich ist, sind auch die Mengen $B^n$ endlich, und wir haben es mit einer abzählbaren Vereinigung von endlichen Mengen zu tun.
Bei b) geht es um die Menge$$
\bigcup_{n\in\mathbb N}W^n \;.
$$Da $W$ nach a) abzählbar ist, sind auch die $W^n$ abzählbar, und wir haben es mit einer abzählbaren Vereinigung von abzählbaren Mengen zu tun.
In beiden Fällen sind die Voraussetzungen des Satzes ("höchstens abzählbare Vereinigungen höchstens abzählbarer Mengen") erfüllt.
|
Profil
|
X3nion
Aktiv
Dabei seit: 17.04.2014
Mitteilungen: 1053
| Beitrag No.23, vom Themenstarter, eingetragen 2021-10-16
|
Hallo zusammen
kann man denn nicht einfach sagen, dass ein Satz einfach ein ultralanges Wort ist, ggf. getrennt durch ein Leerzeichen "|" und das wurde schon in a) bewiesen?
Viele Grüße,
X3nion
\quoteon
PS: schön, mal wieder von dir zu lesen!
\quoteoff
P.S. @Diophant Ja dito :) ich bin wieder etwas aktiver hier auf dem Matheplaneten.
|
Profil
|
zippy
Senior
Dabei seit: 24.10.2018
Mitteilungen: 4638
| Beitrag No.24, eingetragen 2021-10-17
|
\quoteon(2021-10-16 23:31 - X3nion in Beitrag No. 23)
kann man denn nicht einfach sagen, dass ein Satz einfach ein ultralanges Wort ist, ggf. getrennt durch ein Leerzeichen "|"
\quoteoff
Das kann man sagen. Und das ist gerade die Aussage "ein Wort über $\widetilde B$ ist ein Satz über $W$".
\quoteon(2021-10-16 23:31 - X3nion in Beitrag No. 23)
und das wurde schon in a) bewiesen?
\quoteoff
In a) ging es um ein Alphabet mit 26 Buchstaben (a bis z). Jetzt benötigt man diese Aussage für ein Alphabet mit 27 Buchstaben (a bis z und $|$). Daher ist es wesentlich, dass der Beweis zu a) für beliebige $n$ funktioniert und nicht nur für $n=26$.
|
Profil
|
Kezer
Senior
Dabei seit: 04.10.2013
Mitteilungen: 1860
| Beitrag No.25, eingetragen 2021-10-17
|
Der Grund wieso ich nicht den Zusammenhang "Abzählbare Vereinigung abzählbarer Mengen ist abzählbar" genannt habe, ist, dass diese Aussage das abzählbare Auswahlaxiom benutzt.
Eine explizite Bijektion über Basissystem-Wechsel benötigt das aber, glaube ich, nicht. Da ich aber nicht standfest über solche Beziehungen in der Mengenlehre bin, hatte ich das nicht erwähnt.
|
Profil
|
X3nion
Aktiv
Dabei seit: 17.04.2014
Mitteilungen: 1053
| Beitrag No.26, vom Themenstarter, eingetragen 2021-10-18
|
Hallo zusammen,
vielen Dank euch nochmal für eure Hilfe, ihr habt mir wirklich sehr weitergeholfen! :)
Viele Grüße,
X3nion
|
Profil
|
X3nion hat die Antworten auf ihre/seine Frage gesehen.
X3nion hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
