I've been reading about Cantor's diagonal argument all day, it's pretty confusing, but I think I get it now and I want to make sure asking you guys to confirm it. So, this is my understanding:
Two sets, $A$ and $B$ have the same size if and only if there exists a one-to-one function that maps $A$ onto $B$.
A set $A$ is countably infinite if and only if there exists a one-to-one function that maps $A$ onto $ℕ$.
Now, if we want to show that the set $ℝ$ does not have the same cardinality as $ℕ$ and that "it's larger", from the above definition, we have to prove that there does not exists a one-to-one function that maps $ℕ$ onto $ℝ$ (or equivalently that $ℝ$ is not countably infinite).
We proceed by contradiction:
We suppose there exists a one-to-one function that maps $ℕ$ onto $ℝ$.
All these are real numbers $f(1), f(2), f(3), …, f(n), …$
we arrange these numbers in this way:
\begin{matrix}
f(1)=\:.\pmb{a_{11}}a_{12}a_{13}a_{14}…\\
f(2)=\:.a_{21}\pmb{a_{22}}a_{23}a_{24}…\\
f(3)=\:.a_{31}a_{32}\pmb{a_{33}}a_{34}…\\
…\\
f(n)=\:.a_{n1}a_{n2}a_{n3}a_{n4}…\\
…
\end{matrix}
where all the $a_{ij}$s represent random numbers from $0$ to $9$ (note the period at the beginning, it means that there should be another number there, like a normal decimal).
Now if we find a number that is not in that list it means 2 things (which is actually the same thing):
1 – The function is not bijective (since at the beginning we supposed that there exists a one-to-one function that maps $ℕ$ onto $ℝ$ every element of $ℝ$ should have an element of $ℕ$ mapped to it, and we found an element of $ℝ$ that doesn't have one, since it's not in the list).
2 – That the set $ℝ$ is not countable, both because we can't "list them" (that list should represent every real number, but we missed one) and because that function is not bijective.
To find this number that is not in the list we choose a number that should be in that list, let's say number $y$, which since it has to to be real number it has the form of a decimal: $y=\:.y_1y_2y_3y_4…$ where again all the $y_i$s are numbers between $0$ and $9$, now to make different from all the other numbers, the trick is:
Let the first digit $y_1$ be different from the first digit of the first number of that list, namely $a_{11}$, the second digit $y_2$ be different from the second digit of the second number of that list, namely $a_{22}$, $y_3$ different from $a_{33}$ and so on, so we will have a number that has at least 1 different digit from all those numbers and therefore it's none of those numbers, but at the same time since it's a decimal it should be in that list so we have a contradiction and we proved the 2 points, so in the end, even though $ℕ$ and $ℝ$ are both infinite they dont have the same number of elements, $ℝ$ has more since some elements "stay free" even after we paired every element of $ℕ$ with some element of $ℝ$.
Is this correct? I tried to explain it in the best way i can, i really hope it makes sense.. and please don't close the question, i know that there are a lot of questions about Cantor's diagonal argument but i can't be 100% sure i understand it if i don't write it down and someone confirms it. Thank you so much!
Best Answer
The argument works as follows:
you tell me your would-be bijection by listing the numbers in the order induced by that bijection;
I am able to exhibit a number which is not in your list: I take for the first decimal a digit different from the first decimal of the first number; then a digit different from the second decimal of the second number, and so on.
By the construction principle, that real differs from all reals the list by at least one decimal, hence your bijection is incomplete.
As this "works" with any bijection, no bijection can exist.
Illustration:
$$0.\color{green}584669954\cdots\to0.6$$ $$0.3\color{green}62587745\cdots\to0.67$$ $$0.88\color{green}7459552\cdots\to0.678$$ $$0.336\color{green}528454\cdots\to0.6786$$ $$0.9549\color{green}24584\cdots\to0.67863$$ $$\cdots$$