Seção 1.2 Números Naturais e Contagem
A primeira habilidade que dominamos no uso dos números naturais é a de contar, ou seja, a de determinar o número de elementos de um conjunto.
Definição 1.2.1.
Contar um conjunto \(X\) significa estabelecer uma correspondência biunívoca entre os elementos de \(X\) e os de um subconjunto de \(\mathbb{N}\) da forma
\begin{equation*}
I_n=\{x\in \mathbb{N}~|~ x\leq n\} = \{1,2,\ldots, n\}.
\end{equation*}
Quando é possível estabelecer tal correspondência biuívoca, dizemos que \(X\) é um conjunto finito e que \(n\) é o número cardinal ou número de elementos de \(X\text{.}\)
A partir da definição anterior podemos demonstrar as propriedades básicas da contagem:
Teorema 1.2.3.
O resultado da contagem (ou seja, o número cardinal de \(X\)) é sempre o mesmo, não importando a contagem que seja feita.
Todo subconjunto \(Y\) de um conjunto finito \(X\) é finito e \(n(Y)\leq n(X)\text{.}\) Tem-se \(n(Y)=n(X)\) somente quando \(Y=X\text{.}\)
Definição 1.2.6.
Dizemos que dois conjuntos \(X\) e \(Y\) têm a mesma cardinalidade quando é possível estabelecer uma correspondência biunívoca entre \(X\) e \(Y\) (isto é, existe uma função bijetiva \(f:X\rightarrow Y\)).
Exemplo 1.2.7.
O conjunto \(\mathbb{N}\) dos números naturais e \(P=\{2n~|~n\in \mathbb{N}\}\) dos números pares têm a mesma cardinalidade. Neste caos, a bijeção já está dada na definição de \(P\text{:}\) a função \(f:\mathbb{N}\rightarrow P\) definida por \(f(n)=2n\) é uma bijeção de \(N\) em \(P\text{.}\)
Exemplo 1.2.9.
Considere o conjunto \(C\) de todas as sequências infinitas em que todos os termos são iguais a \(0\) ou \(1\text{.}\) Um exemplo de elemento de \(C\) é a sequência \((0,1,0,1,\ldots)\text{,}\) que alterna termos \(0\) e \(1\text{.}\) A cardinalidade de \(C\) é pelo menos a mesma de \(\mathbb{N}\text{,}\) já que é possível estabelecer uma correspondência biunívoca entre \(\mathbb{N}\) e o subconjunto \(D\) de \(C\) formado pelas sequências que possuem exatamente um termo igual a \(1\) (podemos associar o natural \(n\) à sequência em que o \(1\) aparece na \(n\)-ésima posição). Isso não impede, em princípio, que possa haver uma bijeção entre \(\mathbb{N}\) e \(C\text{.}\) Cantor, no entanto, mostrou que não há tal bijeção, fazendo com que \(C\) seja "mais infinito" que \(\mathbb{N}\text{.}\)
Seu argumento foi o seguinte. Suponhamos que fosse possível construir uma função \(f:\mathbb{N}\rightarrow C\text{,}\) em que cada sequência de \(C\) aparecesse exatamente uma vez como imagem. Assim, seria possível ordenar as sequências de \(C\text{,}\) por exemplo:
\begin{align*}
f(1)=\amp~ (1,0,0,0,0,0,\ldots)\\
f(2)=\amp~ (1,0,1,0,0,0,\ldots)\\
f(3)=\amp~ (0,0,0,1,1,1,\ldots)\\
\vdots :\amp~ \vdots
\end{align*}
Construa uma sequência \(s\) formada por \(0s\) e \(1s\) do seguinte modo: Se o primeiro termo da sequência \(f(1)\) é \(0\text{,}\) o primeiro termo de \(s\) é \(1\text{;}\) senão, é \(0\text{.}\) Se o \(i\)-ésimo termo da sequência \(f(i)\) é \(0\text{,}\) o \(i\)-ésimo termo de \(s\) é \(1\text{;}\) senão, é \(0\) e assim sucessivamente. A sequência \(s\) assim contruída difere pelo menos na posição \(n\) de cada sequência \(f(n)\text{.}\) Logo, não pertence a imagem de \(f\text{.}\) Mas, nossa suposição era de que todos os elementos de \(C\) aparecessem como imagem!. Temos, assim, uma contradição, que mostra a impossibilidade de construir uma bijeção de \(\mathbb{N}\) em \(C\text{.}\)
