Forum:  Mengenlehre
Thema: Überabzählbarkeit der Menge {f: IN -> {0,1}}
Themen-Übersicht
Heiner42
Junior
Dabei seit: 17.05.2021
Mitteilungen: 9
Themenstart: 2021-05-17 18:04

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


ligning
Senior
Dabei seit: 07.12.2014
Mitteilungen: 3263
Wohnort: Berlin
Beitrag No.1, eingetragen 2021-05-17 18:19

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]


sonnenschein96
Senior
Dabei seit: 26.04.2020
Mitteilungen: 507
Beitrag No.2, eingetragen 2021-05-17 18:20

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


Riemannifold
Junior
Dabei seit: 01.05.2021
Mitteilungen: 18
Beitrag No.3, eingetragen 2021-05-17 18:23

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


Heiner42
Junior
Dabei seit: 17.05.2021
Mitteilungen: 9
Beitrag No.4, vom Themenstarter, eingetragen 2021-05-17 21:17

fed-Code einblenden


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6992
Wohnort: Milchstraße
Beitrag No.5, eingetragen 2021-05-17 22:29

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,...)\)?


Heiner42
Junior
Dabei seit: 17.05.2021
Mitteilungen: 9
Beitrag No.6, vom Themenstarter, eingetragen 2021-05-17 22:54

fed-Code einblenden


Nuramon
Senior
Dabei seit: 23.01.2008
Mitteilungen: 2977
Beitrag No.7, eingetragen 2021-05-17 23:42
\(\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\)

Heiner42
Junior
Dabei seit: 17.05.2021
Mitteilungen: 9
Beitrag No.8, vom Themenstarter, eingetragen 2021-05-18 23:17

Hallo!

Danke für den Hinweis. So betrachtet ist G doch nicht injektiv.

Vielen Dank auch nochmals den anderen Teilnehmern!


Viele Grüße

Heiner




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=253956=1718
Druckdatum: 2021-07-25 20:44