Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Mengenlehre » Abzählbarkeit und Überabzählbarkeit
Autor
Universität/Hochschule J Abzählbarkeit und Überabzählbarkeit
X3nion
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 8039
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 Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 1554
  Beitrag No.2, eingetragen 2021-10-16

Tipp: Dezimalsystem vs. Basis 26.


   Profil
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1157
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 Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 8039
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 Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 8039
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 Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 8039
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 Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1157
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 Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 8039
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 Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  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 Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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 Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  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 Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 8039
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 Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 18.01.2019
Mitteilungen: 8039
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 Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  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 Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2948
  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 Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 1554
  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 Letzter Besuch: im letzten Quartal
Dabei seit: 17.04.2014
Mitteilungen: 1051
  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.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 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]