A cardinalidade de um conjunto é uma medida que indica a quantidade de elementos presentes nesse conjunto. Em outras palavras, é o “tamanho” do conjunto.
Definição 15.1 Sejam \(A\) e \(B\) dois conjuntos. Dizemos que \(A\) e \(B\) têm a mesma cardinalidade se existe uma função bijetora \(f: A \to B\). Neste caso, escrevemos \(|A| = |B|\).
Exemplo 15.1
Sejam os conjuntos \(A = \{1, 2, 3\}\) e \(B = \{4, 5, 6\}\). Podemos definir uma função bijetora \(f: A \to B\) tal que:
\(f(1) = 4\)
\(f(2) = 5\)
\(f(3) = 6\).
Ou seja, cada elemento de \(A\) é mapeado para um elemento único de \(B\), e vice-versa. Portanto, os conjuntos \(A\) e \(B\) têm a mesma cardinalidade: \(|A| = |B|\).
Ora, se \(C=\{4,5\}\), então não existe função bijetora entre \(A\) e \(C\), pois \(A\) tem mais elementos que \(C\). Portanto, \(|A| \neq |C|\).
15.2 Conjuntos finitos e infinitos
Definição 15.2 Se um conjunto \(A\) tem a mesma cardinaldidade do conjunto \(\{1, 2, \ldots, n\}\) para algum número natural \(n\), dizemos que \(A\) é um conjunto finito e escrevemos \(|A| = n\). Caso contrário, dizemos que \(A\) é um conjunto infinito.
Exemplo 15.2 OS conjuntos \(A\), \(B\) e \(C\) do exemplo anterior são conjuntos finitos, com cardinalidades \(|A| = 3\), \(|B| = 3\) e \(|C| = 2\). O conjuinto dos números naturais \(\mathbb{N} = \{0, 1, 2, 3, \ldots\}\) é um conjunto infinito, pois não existe um número natural \(n\) tal que \(\mathbb{N}\) tenha a mesma cardinalidade de \(\{1, 2, \ldots, n\}\).
15.3 Conjuntos infinitos enumeráveis e não enumeráveis
Os conjuntos infinitos têm muitas propriedades interessantes e inesperados. Por exemplo, se \(A\) é um conjunto infinito, então é possível que a cardinalidade de \(A\) seja igual à cardinalidade de um subconjunto próprio de \(A\). Por exemplo, o conjunto dos números pares \(\{0, 2, 4, 6, \ldots\}\) é um subconjunto próprio do conjunto dos números naturais \(\mathbb{N}\), mas ambos os conjuntos têm a mesma cardinalidade, ou seja, \(|\mathbb{N}| = |\{0, 2, 4, 6, \ldots\}|\). Isso vale porque, por exemplo, a função \(f: \mathbb{N} \to \{0, 2, 4, 6, \ldots\}\) dada por \(f(n) = 2n\) é uma bijeção entre esses dois conjuntos.
Estes tipos de fenômenos são ilustrados pelo paradoxo do Hotel de Hilbert, que pode ser assistido nos vídeos a seguir:
Definição 15.3 Um conjunto infinito \(A\) é dito enumerável se ele tem a mesma cardinalidade do conjunto dos números naturais \(\mathbb{N}\). Caso contrário, dizemos que \(A\) é um conjunto não enumerável.
Para um conjunto ser enumerável significa que é possível listar todos os seus elementos em uma sequência infinita; ou seja, os elementos do conjunto podem ser listados, como primeiro, segundo, terceiro, e assim por diante.
Exemplo 15.3
O conjunto dos números inteiros \(\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}\) é um conjunto infinito enumerável. Podemos definir uma função bijetora \(f: \mathbb{N} \to \mathbb{Z}\) da seguinte forma:
\(f(0) = 0\)
\(f(1) = 1\)
\(f(2) = -1\)
\(f(3) = 2\)
\(f(4) = -2\)
e assim por diante. Portanto, \(|\mathbb{Z}| = |\mathbb{N}|\).
O conjunto dos números racionais \(\mathbb{Q}\) também é um conjunto infinito enumerável. Podemos listar todos os números racionais em uma sequência, na maneira seguinte. Escreva os números racionais na forma de frações \(\frac{p}{q}\), onde \(p\) e \(q\) são inteiros e \(q \neq 0\). Organize essas frações em uma grade infinita, onde a linha representa o numerador \(p\) e a coluna representa o denominador \(q\).
Em seguida, percorra essa grade em uma diagonal, ignorando as frações que não estão na forma mais simples (ou seja, aquelas que podem ser simplificadas). Ou seja, listamos os números racionais na seguinte ordem: \[
1/1,\ -1/1,\ 2/1,\ 1/2,\ -2/1,\ 3/1,\ -1/2,\ \cancel{2/2},\ -3/1,\ 4/1, \ldots
\] Dessa forma, podemos listar todos os números racionais sequencialmente, Portanto, \(|\mathbb{Q}| = |\mathbb{N}|\).
Exemplo 15.4 O conjunto dos números reais \(\mathbb{R}\) é um conjunto infinito não enumerável. Isso pode ser demonstrado usando o argumento da diagonalização de Cantor. Vamos usar o argumento que o o intervalo \((0,1)\) é não enumerável, o que implica que \(\mathbb{R}\) também é não enumerável. Suponha, para fins de contradição, que exista uma maneira de enumerar os números reais no intervalo \((0,1)\). Isso significa que podemos listar todos os números reais nesse intervalo como uma sequência infinita: \[
a_1=0,b_{11}b_{12}b_{13}b_{14}\ldots \\
a_2=0,b_{21}b_{22}b_{23}b_{24}\ldots \\
a_3=0,b_{31}b_{32}b_{33}b_{34}\ldots \\
a_4=0,b_{41}b_{42}b_{43}b_{44}\ldots \\
\vdots
\] Para garantir a unicidade, assumimos que nenhum número termina com uma sequência infinita de 9s, enquanto nas expansões finitas, assumimos que a sequência de dígitos tem uma sequência infinita de 0s.
Agora, vamos construir um novo número real \(c\) no intervalo \((0,1)\) que difere de cada número \(a_n\) na \(n\)-ésima casa decimal. Definimos o número \[
c=0,c_1c_2c_3c_4\ldots
\] na seguinte forma. Escolhemos o dígito \(c_1\) diferente de \(b_{11}\) e diferente de 9. Similarmente, escolhemos o dígito \(c_2\) diferente de \(b_{22}\) e diferente de 9, e assim por diante. Dessa forma, garantimos que o número \(c\) difere de cada número \(a_n\) na \(n\)-ésima casa decimal; ou seja o número \(c\) não aparece na noss lista, mas também não possui uma sequência infinita de 9s. Isso contradiz nossa suposição inicial de que todos os números reais no intervalo \((0,1)\) foram enumerados. Portanto, concluímos que o conjunto dos números reais \(\mathbb{R}\) é não enumerável.
Lema 15.1 Os seguintes conjuntos tem a mesma cardinalidade dos números reais \(\mathbb{R}\):
O intervalo aberto \((0,1)\).
O intervalo semiaberto \([0,1)\).
O intervalo fechado \([0,1]\).
Um intervalo qualquer \((a,b)\), \([a,b]\), ou \([a,b)\)onde \(a < b\) e \(a,b \in \mathbb{R}\).
\((0,+\infty)\) e \([0, +\infty)\), \((-\infty,0)\) e \((-\infty,0]\).
Comprovação. A demonstração pode ser feita construindo funções bijetoras entre estes conjuntos.
Por exemplo, para mostrar que o intervalo aberto \((0,1)\) tem a mesma cardinalidade que o intervalo semiaberto \([0,1)\), podemos definir a função bijetora \(f: (0,1) \to [0,1)\) da seguinte forma: \[
f(x) =
\begin{cases}
0, & \text{se } x=1/2 \\
1/2^{k+1}, & \text{se } x = 1/2^k \text{ para algum } k \in \mathbb{N} \\
x, & \text{caso contrário}
\end{cases}
\] Essa função mapeia o ponto \(1/2\) para \(0\), os pontos da forma \(1/2^k\) para \(1/2^{k+1}\), e mantém todos os outros pontos inalterados. É possível verificar que essa função é bijetora, garantindo que cada elemento de \((0,1)\) é mapeado para um elemento único de \([0,1)\), e vice-versa.
Entre, os intervalos \((0,1)\) e \((a,b)\), podemos definir a função bijetora \(g: (0,1) \to (a,b)\) dada por: \[
g(x) = a + (b-a)x.
\] Essa função mapeia o intervalo \((0,1)\) para o intervalo \((a,b)\) de forma bijetora.
Entre os intervalos \((0,1)\) e \(\R\) podemos definir a função bijetora \(h: (0,1) \to \R\) dada por: \[
h(x) = \tan\left(\pi x - \frac{\pi}{2}\right).
\] Essa função mapeia o intervalo \((0,1)\) para todo o conjunto dos números reais de forma bijetora.
Entre os intervalos \(\R\) e \((0,+\infty)\) podemos definir a função bijetora \(k: \R \to (0,+\infty)\) dada por: \[
k(x) = e^x.
\]
Usando essas ideias, podemos construir funções bijetoras entre todos os conjuntos mencionados, demonstrando que eles têm a mesma cardinalidade dos números reais \(\mathbb{R}\).
15.4 A cardinalidade do conjunto das partes
O leitor pode se perguntar se existe uma cardinalidade maior que a do conjunto dos números reais. A resposta é sim, e de fato existem cardinalidades infinitas cada vez maiores. Uma maneira de construir conjuntos com cardinalidades maiores é considerar o conjunto das partes de um conjunto dado.
Lembra que o conjunto das partes \(\mathcal P(A)\) de um conjunto \(A\) é o conjunto formado por todos os subconjuntos de \(A\). Por exemplo, se \(A = \{1, 2\}\), então o conjunto das partes de \(A\) é dado por: \[
\mathcal P(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}.
\]
Teorema 15.1 Sendo \(A\) um conjunto qualquer (possívelmente infinito), não existe uma função sobrejetora de \(A\) para \(\mathcal P(A)\). Em particular, a cardinalidade de \(\mathcal P(A)\) é estritamente maior que a cardinalidade de \(A\).
Comprovação. Suponha, para fins de contradição, que exista uma função sobrejetora \(f: A \to \mathcal P(A)\). Isso significa que para cada subconjunto \(B\) de \(A\), existe um elemento \(a \in A\) tal que \(f(a) = B\). Agora, vamos construir um subconjunto especial de \(A\), chamado de conjunto diagonal \(D\), definido da seguinte forma: \[
D = \{a \in A \mid a \notin f(a)\}.
\] Ou seja, o conjunto \(D\) contém todos os elementos de \(A\) que não pertencem ao subconjunto que lhes é associado pela função \(f\). Agora, como \(f\) é sobrejetora, deve existir um elemento \(d \in A\) tal que \(f(d) = D\). Agora, vamos analisar se o elemento \(d\) pertence ao conjunto \(D\) ou não.
Se \(d \in D\), então, pela definição de \(D\), temos que \(d \notin f(d)\). Mas como \(f(d) = D\), isso implica que \(d \notin D\), o que é uma contradição.
Se \(d \notin D\), então, novamente pela definição de \(D\), temos que \(d \in f(d)\). Mas como \(f(d) = D\), isso implica que \(d \in D\), o que também é uma contradição.
Logo, em ambos os casos, chegamos a uma contradição. Portanto, nossa suposição inicial de que existe uma função sobrejetora de \(A\) para \(\mathcal P(A)\) é falsa. Isso implica que a cardinalidade de \(\mathcal P(A)\) é estritamente maior que a cardinalidade de \(A\).