I don't fully understand the concept behind...
(1) The Cantor Pairing Function and
(2) Cantor's Diagonalization Method.
I understand that (1) and (2) involve proving if a set is countable or not.
For example, let's consider the set of all real numbers, $\mathbb{R}$, which is known to be uncountable. We can prove this set is uncountable using Cantor's Diagonlization method.
To keep things simple, let's look at the set of real numbers between 0 and 1. We can prove that this subset is uncountable by using contradiction. Thus, we initially assume the subset is countable, like so:
$y_1$ = $0 \: . \: x_{11} \: x_{12} \: x_{13} \: . . .$
$y_2$ = $0 \: . \: x_{21} \: x_{22} \: x_{23} \: . . .$
$y_3$ = $0 \: . \: x_{31} \: x_{32} \: x_{33} \: . . .$
.
.
.
$y_k$ = $0 \: . \: x_{k1} \: x_{k2} \: x_{k3} \: . . .$
where each $x_{ij}$ is a decimal place.
Now we can consider $y' = 0. x_{11} \: x_{22} \: x_{33} . . .$, for $y' \in [0,1]$. This particular $y'$ is the diagonal... We can now immediately see that $y'$ is not in the subset, which proves that the set of real numbers between 0 and 1 is not countable.
So now I have 2 questions...
(1) How does Cantor's diagonalization method prove that this subset is uncountable? I understand that $y'$ is not in the subset, but how does this prove we can't count everything? Is this because we can create permutations of $y'$ that are also not in the subset? For example, let $y''$ and $y'''$ be permutations of $y'$:
$y'' = 0. \: x_{22} \: x_{33} \: x_{44} . . . \: x_{kk} . . . \: x_{11}$
$y''' = 0. \: x_{33} \: x_{44} \: x_{55} . . . \: x_{kk} . . . \: x_{11} \: x_{22}$
etc..
(2) Can I use Cantor's pairing function to prove the set is countable or not? If I can, how would I use it? If I can't, why can't I use it?
As a side note, I saw this question earlier about Cantor's pairing function: Prove that the union of countably many countable sets is countable.
It only confused me further. I don't understand how this method creates a one-to-one mapping to $\mathbb{N}$
No comments:
Post a Comment