I am trying to prove that the Cantor set is uncountable, but I am very much a novice in working with different bases of numbers. I've never had to do it in any of my classes until now.
Where I'm at is this:
It is trivial that $C \underline{\subset} [0,1]$. Therefore, $|C| \leq |[0,1]|$.
Now, I want to get $|[0,1]| \leq |C|$ to apply Cantor-Bernstein-Schroeder, and I have a few questions. I am mainly looking at this link here https://sciences.csuohio.edu/sites/csuohio.edu.sciences/files/Cantor%20and%20infinite%20sets.pdf number 5 on page 2.
First, I have read that ternary numbers could have multiple binary representations. (Or maybe it's the other way around, I'm extremely new to this stuff). Is this true? If so, how would it be possible to get an injection since an input could produce multiple outputs?
Second, from looking at this link here For any two sets A and B, if $f: A \rightarrow B$ is injective, then if A is countable, B must be countable. it seems like an injection (1-1) from $C$ to $[0,1]$ (in our case) means that "$C$ has at least as many elements as $[0,1]$." So, $|[0,1]| \leq |C|$. The surjection (onto) is the other way around. With that being said, at the first link I sent, why are they giving $f(x)$? Since $f(x)$ is a surjection, doesn't that simply assert that $|C| \leq |[0,1]|$? They already said that fact was found from number 4, so I'm confused as to the importance of listing it?
Third, following on my second question, it looks like $g(y)$ is all that is needed. If $g(y)$ is injective, like they say, then we'd have a 1-1 map from $[0,1] \to C$ meaning "$[0,1]$ has at least as many elements as $C$." So, We would have $|C| \leq [0,1]$. But this goes back to my first question: if there are multiple representations, how do we know this map is indeed 1-1? Can we prove that this map is 1-1? And if so, how?
Note for readers: I know there are plenty of posts about this subject. However, I am still not fully sure how to answer the question from reading them. Due to my very limited knowledge of other bases and never having worked with the countability of sets, I'm having trouble following them. So that is why I posted this, I want some clarification.
Best Answer
Suppose we have two decimal expansions $x = 0.x_1x_2x_3\dots, y = 0.y_1y_2y_3\dots$ for numbers in $0$ and $1$, labelled so that $x \ge y$. Then $$x - y = \sum_{n=1}^\infty(x_n - y_n)10^{-n}$$ where for all $n, x_n - y_n \le 9$. Therefore $$x - y \le 9\sum_{n=1}^\infty 10^{-n} = 1$$ If the first $k$ decimals agree - that is, $x_n = y_n$ for all $n \le k$ - then we can sharpen that estimate $$x - y \le 9\sum_{n=k+1}^\infty 10^{-n} = 10^{-k}$$ But further, to get $10^{-k}, x_n - y_n =9$ for all $n > k$. The only way to accomplish this is for all the $x_n = 9, y_n = 0$. In this case, $x = y + 10^{-k}$. But $y+ 10^{-k}$ is also what you get by increasing $y_k$ by $1$ (unless $y_k = 9$, in which case, you set $y_k = 0$ and increase $y_{k-1}$ by $1$, etc.) So the original expansion $0.x_1x_2x_3\dots$ ending in repeated $9$s, and the terminating expansion from incrementing $y_k$ are two different representations of $x$.
On the other hand, if there are some $n > k$ with $x_n \ne 9$, then $x - y < 10^{-k}$. No matter how $y$ varies from $x$ beyond the first $k$ digits, it cannot be as much as a change by $1$ in the $k^\text{th}$ digit. Thus any alternative expansion for $x$ cannot make up a difference in the $k^\text{th}$ digit by the remaining digits. I.e., it must agree up to digit $k$. Similarly, if $y$ has non-zero digits beyond $y_k$, then no alternative expansion for it can disagree in the first $k$ digits.
Thus real numbers with a terminating decimal epression (i.e., all numbers of the form $\frac n{10^m}$ for $n, m \in \Bbb Z$), also have a second decimal expression agreeing up to but not including the last non-zero digit of the terminating expression. That last digit is $1$ lower, and is followed by repeating $9$. Any non-terminating decimal expression that also does not end in repeating $9$ is unique. The number it represents has no other decimal expansion.
In the the above, if you replace "$10$" with any integer base $b > 1$ and "$9$" with "$b-1$", the argument is still valid. For any base, the terminating expansions have two forms, while all other expansions are unique.
The answer to your question of how is it possible is that you take greater care than this, and pick specifically which output you want. I'll get to that later.
No. The set $\{1\}$ has a injection into $\Bbb R$ (namely the map carrying $1$ to itself), but I can assure you that $\{1\}$ does not have as many elements of $\Bbb R$. The questioner failed to realize they needed to disprove statement (A), not prove it. That is why a similar, if not quite so blatant, counterexample was given in both the comments and both answers.
If you have an injection from $A$ into $B$, then that injection matches up $1-1$ every element of $A$ with an element of $B$. Every element of $A$ is matched, but $B$ can have some elements left over. If you match up the the fingers of your right and left hands, and (perhaps due to some unfortunate incident in your past), one of the hands has an unmatched finger, which hand has more fingers? The one with the left-over finger. So an injection from $A$ to $B$ means $B$ has at least as many elements as $A$, not the other way around.
Conversely, if $A$ has a surjection $g$ onto $B$, intuitively, you can create an "semi-inverse" mapping $h$ from $B$ into $A$ by picking for each element $b \in B$, one of its pre-images in $g^{-1}(b) = \{a \in A : g(a) = b\}$ (there are a lot complications if you want to prove it constructively, but this is the general idea). Since $g(h(b)) = b$, $h$ has to be injective (do you see why?). So if there is a surjection from $A$ to $B$, then $A$ has at least as many elements as $B$.
As I've already noted, the surjectivity of $f$ does not show the same inequality already known, but the opposite inequality. But that is not why they discuss $f$. In your text, they have not (yet) discussed the relationship between surjectivity and comparison of cardinals. Yes, (under the axiom of choice) surjectivity does show the cardinality of the domain is $\ge$ the cardinality of the codomain. But that is not how they defined $\ge$ between cardinals, nor have they discussed it, so it is not something they can use.
So why talk about $f$? You'll have to ask them to be sure. $f$ and $g$ are "semi-inverses" as discussed above. $f$ is surjective, and $g$ picks one of the pre-images of $f$. I think they include $f$ as part of the general background about the Cantor set and function (if you restrict the Cantor function (often called the Cantor-Legesgue function) they define later to just the Cantor set, you get $f$.
So it is by $g$ that they show $|[0,1]| \le |\frak C|$.
By specifically deciding which representation will be used:
$g$ is defined by this procedure
The binary expansion of $y$ is used to define the $b_n$. So that is where there is ambiguity. But there are multiple expansions only when the number has a terminating expansion, so we require that the terminating expansion always be used in that case. That removes the ambiguity. The value of $g$ is defined by a well-defined infinite sum, so there is no ambiguity in it.