Matematik

Tællelighed

05. juli 2018 af Stats - Niveau: Universitet/Videregående

Undskyld dette bliver lidt langt... Blok citaterne er hhv. et bevis, opgaven og en løsning af opgaven... Det er selve løsningen jeg ikke kan finde ud af, hvordan han er kommet frem til.

OPGAVEN

2.15: Adapt the proof of Theorem 2.8 to show that $\small \tiny \small \#\{1,2\}^\mathbb{N}\leqslant \#(0,1)\leqslant \#\{0,1\}^\mathbb{N}$ and conclude that $\small \tiny \small \#(0,1)= \#\{0,1\}^\mathbb{N}$

Remark. This is the reason for writing $\small \tiny \small \mathfrak{c}=2^{\aleph_0}$ .
[Hint: Interpret $\small \tiny \small \{0,1\}^\mathbb{N}$ as a base-2 expansions of all numbers in $\small \tiny \small (0,1)$ while $\small \tiny \small \{1,2\}^\mathbb{N}$ are all infinite base-3 expansions lacking the digit 0.]

BEVIS PÅ THEOREM 2.8

Theorem 2.8 The interval $\small (0,1)$ is uncountable; it's cardinality $\small \tiny \small \mathfrak{c}:=\#(0,1)$ is called the continuum.

Proof We can write each $\small \tiny \small x\in(0,1)$ as a decimal fraction, i.e. $\small \tiny \small x=0.y_1y_2y_3...$ with $\small \tiny \small y_i\in\{0,1,...,9\}$ . If $\small x$ has a finite decimal representation, say $\small x=0.y_1y_2y_3...y_n,y_n\neq0$ we replace the last digit $\small y_n$ by $\small y_n-1$ and fill it up with trailing 9's. For example, $\small 0.24=0.23\overline{99}$ ... This yields a unique representation of $\small x$ by infinite decimal expansion.
Assume that $\small (0,1)$ were countable and let $\small \{x_1,x_2,...\}$ be an enumeration (containing no element more than once!). We can write

$\small \begin{matrix} x_1 & = & 0.a_{1,1}a_{1,2}a_{1,3}a_{1,4}...\\ x_2 & = & 0.a_{2,1}a_{2,2}a_{2,3}a_{2,4}...\\ x_3 & = & 0.a_{3,1}a_{3,2}a_{3,3}a_{3,4}...\\ x_4 & = & 0.a_{4,1}a_{4,2}a_{4,3}a_{4,4}...\\ \vdots & \vdots & \end{matrix}$

And construct a new number $\small x:=0.y_1y_2y_3...\in(0,1)$ with digits

$\small y_i\left\{ \begin{matrix} 1 & \textrm{if }a_{i,i}=5\\ 5 & \textrm{if }a_{i,i}\neq 5 \end{matrix}\right .$

By contruction, $\small x\neq x_i$ for any $\small x_i$ from the list above: $\small x$ and $\small x_i$ differ at the ith decimal. But then we have found a number $\small x\in(0,1)$ which is not contained in our supposedly complete enumeration of $\small (0,1)$ and we get a contradiction.

LØSNINGEN

Since we can write each $\small x\in(0,1)$ as an infinite dyadic fraction (o.k. if it is finite fill it up with an inifite tail of zeros!), the prove of Theorem 2.8 shows that $\small \#(0,1)\leqslant \#\{0,1\}^\mathbb{N}$ .

On the other hand, thinking in base-4 expansions, each element of $\small \#\{1,2\}^\mathbb{N}$ can be interpreted as a unique base-4 fraction (having no 0 or 3 in its expansion) of some number in $\small (0,1)$ . Thus, $\small \#\{1,2\}^\mathbb{N}\leqslant \#\mathbb{N}$

But $\small \#\{1,2\}^\mathbb{N}=\#\{0,1\}^\mathbb{N}$ and we can conclude with Theorem 2.7 that $\small \#(0,1)=\#\{0,1\}^\mathbb{N}$

Theorem 2.7 er Cantor-bernsteins: #X ≤ #Y og #Y ≤ X så er #X = #Y

Jeg bliver forvirret over den "dyadic fraction". Nu har jeg været inde og kigge på wikipedia, og da siger de, at sådan en er på formen

$\small \frac{a}{2^b}$

Men så bliver jeg netop forvirret... Vi kan ikke tilskrive hvert x∈(0,1) som en dyadic fraction. En dyadic fraction er netop rationel - mens x kan være irrationel. Her mener jeg også at beviset i Theorem 2.8 overhovedet ikke viser at $\small \small \#(0,1)\leqslant \#\{0,1\}^\mathbb{N}$ .. Nogen der kan forklare den første bid?

Brugbart svar (0)

Svar #1
05. juli 2018 af Drunkmunky

Det der menes med "infinite dyadic fraction" er, at ligesom du med tallene mellem 0 og 1 i decimalsystemet (10-tals systemet) kan skrive

$a=0,a_{1}a_{2}a_{3}a_{4}a_{5}\ldots=\sum\limits_{i=1}^{\infty}a_{i}10^{-i}$

(som jo er et rationelt tal hvis og kun hvis endeligt mange af a_i'erne er lige med 0), så kan du skrive dem i det binære talsystem (2-tal systemet)

$a=0,b_{1}b_{2}b_{3}b_{4}b_{5}\ldots=\sum\limits_{i=1}^{\infty}b_{i}2^{-i}$ ,

hvilket er det de bruger Cantors diagonalargument på for at vise, at $\#(0,1)\leq\#\lbrace 0,1\rbrace^{\mathbb{N}}$ for det er jo klart, at alle b_i'erne er enten 0 eller 1 (ellers kan det ikke være skrevet i det binære talsystem).

Tror også du har skrevet en fejl i løsningen i det opslag:

On the other hand, thinking in base-4 expansions, each element of $\#\lbrace 1,2\rbrace^{\mathbb{N}}$ can be interpreted as a unique base-4 fraction (having no 0 or 3 in its expansion) of some number in $(0,1)$ . Thus, $\#\lbrace1,2\rbrace^{\mathbb{N}}\leq\mathbb{N}$

Man burde jo konkludere, at $\#\lbrace1,2\rbrace^{\mathbb{N}}\leq(0,1)$ for argumentet viser jo, at man kan se alle elementerne i $\lbrace1,2\rbrace^{\mathbb{N}}$ som et element i (0,1) (i.e. vi har en injektion fra den ene mængde fra den anden).

Skriv et svar til: Tællelighed

Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk? Klik her for at oprette en bruger.