Htykuut

I was studying about countability or non-contability of sets when I saw the Cantor's diagonal argument to prove that the set of real numbers are not-countable. My question is that in the proof it is always possible to find a new real number that was not in the listed before, but it is kinda obvious, since the set of real number is infinity, we can always find a new real different from the previous one, like with integers for example. If we try to find a bijection f between integers and naturals, given that we know the value of $f$ in ${1,2,ldots,n}$ the value of $f(n+1)$ will be different than any number in ${f(1),f(2),ldots,f(n)}$, since $f$ is bijective then $f$ is injective.

We say that two sets are equinumerous if there exists a bijection between them. That is, sets $A$ and $B$ admit a function $$f colon A rightarrow B$$ such that every element of $B$ is mapped to by exactly one element of $A$ (we say $f$ is both injective and surjective). So, if you give you an element $a in A$, I can give you a unique element of $b in B$ that is "associated" with $a$ via $f$; that is exactly the case when $f(a) = b$. This correspondence goes both ways: Given $b$, I can find $a$ by applying the inverse of $f$ (the existence of inverses is essential to bijections).

An infinite set $A$ is countable if it is equinumerous with the natural numbers which are denoted by $mathbb{N}$. We can show that $A$ is countable by exhibiting a bijection between $A$ and $mathbb{N}$. The integers are countable for example, via the bijection $$ f colon mathbb{N} rightarrow mathbb{Z} \ f(0) = 0, ; f(1) = -1, ; f(2) = 1, ; f(3) = -2, ; f(4) = 2, ; f(5) = -3, ldots$$ Similarly, the rationals $mathbb{Q}$ are countable.

A defining characteristic of countable sets is that we can list their elements. This is by virtue of being in a bijection with the natural numbers; via the bijective function, we can associate any natural number with a unique element, just as we can in a list. Consider, for example, the bijection between $mathbb{N}$ and $mathbb{Z}$ as a list (LHS is element of the naturals, RHS an element of the integers in a bijective correspondence):

$$begin{array}{c|c}
mathbb{N} & mathbb{Z} \ hline
0 & 0 \
1 & -1 \
2 & 1 \
3 & -2 \
4 & 2 \
5 & -3
end{array}$$

and so on.

Cantor's argument says that there is no way of listing all reals in such a list indexed by the natural numbers. While we know that the reals are infinite (the naturals are infinite, and each natural number is also a real number), this proves that there are more reals than there are naturals.

You are right in the sense that whenever we consider ${ f(0), ldots, f(n-1) }$, where $f$ is a bijection from infinite $A$ to infinite $B$, then $f(n)$ will be different from each $f(i)$ for $i < n$. But that's not enough. For a bijection $f$ from $mathbb{N}$ to $mathbb{R}$, we would need for any real number $r$ a unique $m$ in $mathbb{N}$ such that $f(m) = r$. In your analogy, fix any real number $r$. Then considering any natural number $m$, if $r notin { f(0), ldots, f(m) }$, there must exist some integer $n > m$ such that $r in { f(0), ldots, f(n) }$. Cantor's diagonal argument shows that given any infinite list ${ f(0), f(1), ldots }$, there is always a real $r'$ that is not in that list.

Cantor's diagonal proof has nothing to do with finding real numbers which had not been “listed before”. We start with a list of real numbers and then we find a new real number which is nowhere on that list.

Cantor's diagonal proof gets misrepresented in many ways. These misrepresentations cause much confusion about it. One of them seems to be what you are asking about. (Another is that used the set of real numbers. In fact, it intentionally did not use that set. It can, with an additional step, so I will continue as if it did.)

What the significant part of the proof shows, directly and not "by contradiction," is what you called "obvious":

• If you have a function whose domain is the natural numbers and whose co-domain is the real numbers between 0 and 1,


• Then that function is not a surjection.

The only thing that can be called a proof by contradiction, is what Cantor deduced from it: A bijection cannot exist. If you assume one does, it both is (by definition), and is not (by the proof), a surjection.