Matroids Matheplanet Forum Index
Moderiert von mire2 StrgAltEntf
Logik, Mengen & Beweistechnik » Mengenlehre » Überabzählbarkeit der Menge {f: IN -> {0,1}}
Autor
Kein bestimmter Bereich J Überabzählbarkeit der Menge {f: IN -> {0,1}}
Heiner42
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 17.05.2021
Mitteilungen: 9
  Themenstart: 2021-05-17

Hallo! Zum Hintergrund: ich bin kein Mathematiker, meine letzte Analysis Vorlesung liegt Jahrzehnte zurück und ich beschäftige mir aus Spaß mit Mächtigkeiten von Mengen. Ich bitte also wenn möglich um eine "leichte" Antwort. Mein Problem: Sei $f:\IN \rightarrow\{0,1\}$ eine Funktion, die die natürlichen Zahlen auf die Ziffern 0 und 1 abbildet, also eine (abzählbar) unendliche Folge von Nullen und Einsen. Die Menge {f} aller dieser Funktionen ist mächtiger als die der natürlichen Zahlen, wie sich mit dem zweiten Cantorschen Diagonalargument zeigen lässt. Damit sollte es keine injektive Funtktion von {f} nach $\IN$ geben. Was aber ist $F(f) := \sum_{k=0}^\infty f(k)2^k$? - Ich vermute, F ist eine Funktion. - Ich vermute, dass gilt: F(f1) = F(f2) => f1 = f2, d.h. F ist injektiv. - Ich vermute, dass F für jedes f eine natürliche Zahl ergibt, F also in die natürlichen Zahlen abbildet. Wären alle drei Vermutungen richtig, dann wäre F eine injektive Funktion $\{f\}\rightarrow\IN$. Welche dieser Vermutungen ist also falsch und warum? Gruß Heiner


   Profil
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3291
Wohnort: Berlin
  Beitrag No.1, eingetragen 2021-05-17

Hallo und Willkommen auf dem Matheplaneten! Damit $F(f)$ wohldefiniert ist, muss $\sum_{k=0}^\infty f(k)2^k$ konvergieren. Das ist aber nur der Fall, wenn $f$ eine abbrechende Folge ist, d.h. wenn es ein $k_0\in\IN$ gibt mit $f(k)=0$ für alle $k\geq k_0$. [Verschoben aus Forum 'Logik, Mengen & Beweistechnik' in Forum 'Mengenlehre' von ligning]


   Profil
sonnenschein96
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 26.04.2020
Mitteilungen: 515
  Beitrag No.2, eingetragen 2021-05-17

Hallo Heiner, falls Du die Abbildung \[F\colon\{f\,|\,f\colon\mathbb{N}\to\{0,1\}\}\to\mathbb{N}\cup\{\infty\},\,f\mapsto\sum_{k=0}^\infty f(k)2^k\] meinst, diese bildet nicht in die natürlichen Zahlen ab. Jedes \(f\), das unendlich viele Einsstellen hat, wird auf \(\infty\) abgebildet, womit diese Abbildung nicht mehr injektiv ist. [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
Riemannifold
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.05.2021
Mitteilungen: 18
  Beitrag No.3, eingetragen 2021-05-17

Ich bin nicht sicher, aber ich glaube, die Funktion $F$, wie du sie definiert hast, bildet nicht immer nach $\mathbb{N}$ ab. Beispiel: Sei $f:\mathbb{N}\to\left\lbrace 0,1\right\rbrace$ definiert durch $f(n) = 1$ für alle $n$. Dann ist, wenn ich $F$ richtig verstehe, $$F(f) = \sum_{k=0}^\infty 1\cdot 2^k = 1 + 2 + 4 + 8 + \cdots$$ und da die Summe auf der rechten Seite divergiert, bildet $F$ also nicht jedes $f$ nach $\mathbb{N}$ ab. Ich hoffe, das hilft dir weiter. [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
Heiner42
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 17.05.2021
Mitteilungen: 9
  Beitrag No.4, vom Themenstarter, eingetragen 2021-05-17

Vielen Dank ligning, sonnenschein96 und Riemannifold. Die Nicht-Konvergenz hatte ich nicht berücksichtigt. Allerdings kann ich das Problem vielleicht umgehen, indem ich in die Menge der Ordinalzahlen abbilde. Sei also G(f) := sum(f(k) \omega^k,k=0,\inf ). G bildet nun {f} in eine Teilmenge der Ordinalzahlen ab. Das Supremum der Wertemenge von G ist meiner Meinung nach: lim(k->\inf,\omega^k) = \omega^\omega Damit ist G eine injektive Funktion von {f} nach {0...\omega^\omega }. {f} hat die Mächtigkeit von \IR, {0...\omega^\omega } ist aber abzählbar. Wo liege ich diesmal falsch? Gruß und viele Grüße Heiner


   Profil
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 7087
Wohnort: Milchstraße
  Beitrag No.5, eingetragen 2021-05-17

Hallo Heiner42, die Addition von Ordinalzahlen ist ja nicht kommutativ. Bspw. ist \(1+\omega=\omega\neq\omega+1\). Damit deine Funktion G injektiv ist, müsste also \(G(1,0,0,0,...)=1\), \(G(0,1,0,0,...)=\omega\), \(G(1,1,0,0,...)=\omega+1\). Was ist nun \(G(1,1,1,1,...)\)?


   Profil
Heiner42
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 17.05.2021
Mitteilungen: 9
  Beitrag No.6, vom Themenstarter, eingetragen 2021-05-17

Hallo StrgAltEntf, ich kenne mich mit Ordinalzahlarithmetik leider nicht wirklich aus. Ich hatte den "Satz der Cantorsche Normalform zur Basis \omega ": "Jede Ordinalzahl \gamma lässt sich in eindeutiger Weise schreiben als \gamma = \omega ^\alpha_1 n_1 + ... + \omega ^\alpha_k n_k, usw..." in der Art interpretiert, dass jedes Polynom von \omega eindeutig ist in dem Sinne, dass unterschiedliche Polynome immer unterschiedliche Ordinalzahlen ergeben. Aber hier mag ich mich irren. Viele Grüße Heiner


   Profil
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 3011
  Beitrag No.7, eingetragen 2021-05-17

\(\begingroup\)\(\renewcommand{\Re}{\operatorname{Re}} \renewcommand{\Im}{\operatorname{Im}} \newcommand{\End}{\operatorname{End}} \newcommand{\id}{\operatorname{id}} \newcommand{\GL}{\operatorname{GL}} \newcommand{\im}{\operatorname{im}} \newcommand{\sgn}{\operatorname{sgn}} \newcommand{\d}{{\rm d}} \newcommand{\rg}{\operatorname{rg}} \newcommand{\spur}{\operatorname{spur}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\opn}{\operatorname}\) Hallo, wenn man deine Definition von $G$ aus No.4 interpretiert als $$G(f):= \sup_{n\geq 0} f(n)\omega^n+f(n-1)\omega^{n-1}+\ldots + f(0) = \bigcup_{n\geq 0}f(n)\omega^n+f(n-1)\omega^{n-1}+\ldots + f(0),$$ dann ist $G$ nicht injektiv, denn $G(0,1,1,1,\ldots) = G(1,1,1,\ldots)=\omega^\omega$ (allgemeiner: $G(f)=\omega^\omega$ für jedes $f$, dass unendlich oft den Wert $1$ annimmt).\(\endgroup\)


   Profil
Heiner42
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 17.05.2021
Mitteilungen: 9
  Beitrag No.8, vom Themenstarter, eingetragen 2021-05-18

Hallo! Danke für den Hinweis. So betrachtet ist G doch nicht injektiv. Vielen Dank auch nochmals den anderen Teilnehmern! Viele Grüße Heiner


   Profil
Heiner42 hat die Antworten auf ihre/seine Frage gesehen.
Heiner42 hat selbst das Ok-Häkchen gesetzt.
Heiner42 wird per Mail über neue Antworten informiert.

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]