Conjunto contável

Na matemática, um conjunto contável é um conjunto de mesma cardinalidade (número de elementos) de um subconjunto qualquer do conjunto dos números naturais. Um conjunto é dito incontável quando ele não é contável. O termo foi criado por Georg Cantor. Os elementos de um conjunto contável podem ser contados um por vez—mesmo que a contagem nunca termine, cada elemento do conjunto será eventualmente associado com um número natural.

Alguns autores usam conjunto contável para representar um conjunto com a mesma cardinalidade do conjunto dos números naturais.^[1] A diferença entre as duas definições é que, considerando a primeira definição, conjuntos finitos também são considerados contáveis. A segunda definição, no entanto, estabelece que conjuntos infinitos não são contáveis. Para resolver essa ambiguidade, o termo máximo contável é usado para a primeira definição, e infinito contável para a segunda definição. O termo enumerável também pode ser usado para representar infinito contável,^[2] ou contável, em contraste com o termo não enumerável.^[3]

Definição

Um conjunto S é dito contável se existe uma função injetora f de S para os números naturais $\mathbb {N} =\{0,1,2,3,...\}.$ ^[4]

Se f também for sobrejetora e portanto bijetora (já que f já foi definida como injetora), então S é infinito contável.

Como mencionado acima, esta terminologia não é universal: Alguns autores usam contável para representar o que aqui é chamado infinito contável, sem incluir os conjuntos infinitos.

Para formulações alternativas (equivalentes) da definição em termos de uma função bijetora ou uma função sobrejetora, veja a seção Definição formal e propriedades abaixo.

Introdução

Um conjunto é uma coleção de elementos, e pode ser descrito de várias maneiras. Uma delas é simplesmente listar todos os seus elementos; por exemplo, o conjunto que consiste dos números inteiros 3, 4 e 5 pode ser denotado por $\{3,4,5\}$ . No entanto, esta forma é eficaz apenas para conjuntos pequenos; para grandes conjuntos, ela pode ser demorada e propensa a erros. Ao invés de listar cada elemento, às vezes são usadas reticências (...), quando é fácil determinar os elementos que estão faltando; por exemplo, $\{1,2,3,\dots ,100\}$ possivelmente representa o conjunto dos inteiros de 1 a 100. Mesmo nesse caso, entretanto, ainda é possível listar todos os elementos do conjunto, pois o conjunto é finito; tem um número específico de elementos.

Alguns conjuntos são infinitos; estes conjuntos possuem mais que n elementos para todo inteiro n. Por exemplo, o conjunto dos números naturais, representado por $\{0,1,2,3,4,5,\dots \}$ , possui infinitos elementos, e não podemos usar nenhum número normal para indicar seu tamanho. Mesmo assim, verifica-se que conjuntos infinitos possuem uma noção bem definida de tamanho (ou melhor, cardinalidade, que é o termo técnico para o número de elementos de um conjunto), e nem todos conjuntos infinitos têm a mesma cardinalidade.

Para entender o que isso significa, primeiro examinamos o que isso não significa. Por exemplo, Existem um número infinito de números inteiros ímpares e pares, e portanto, infinitos números inteiros em geral. Contudo, verifica-se que o número de inteiros ímpares, que é o mesmo número de inteiros pares, é também o mesmo número de inteiros (ímpares e pares). Isto é, para cada inteiro, existe um inteiro ímpar distinto: ... −2 → −3, −1 → −1, 0 → 1, 1 → 3, 2 → 5, ...; ou de forma mais geral, n → 2n + 1. Em outras palavras, existe uma correspondência um a um (ou bijeção) entre os inteiros e os inteiros ímpares, que é uma função que faz o mapeamento entre os dois conjuntos tal que cada elemento de cada conjunto corresponde a um único elemento do outro conjunto.

Porém, nem todos os conjuntos infinitos têm a mesma cardinalidade. Por exemplo, Georg Cantor (quem introduziu esse campo da matemática) demonstrou que não existe uma correspondência um a um entre os números reais e os números naturais (inteiros não negativos), e portanto que a cardinalidade do conjunto dos números reais é maior que a cardinalidade dos números naturais.

Um conjunto é contável se: (1) é finito, ou (2) tem a mesma cardinalidade (tamanho) do conjunto dos números naturais. Em outras palavras, um conjunto é contável se tem a mesma cardinalidade de um subconjunto qualquer do conjunto dos números naturais. Caso contrário, é incontável.

Definição formal e propriedades

Por definição um conjunto S é contável se existe uma função injetora

f:S\to \mathbb {N}

de S para o conjunto dos números naturais $\mathbb {N} =\{0,1,2,3,...\}.$

Deve ser natural dividir os conjuntos em diferentes classes: coloque todos os conjuntos de um elemento juntos; todos os conjuntos de dois elementos juntos; ...; finalmente, coloque todos os conjuntos infinitos e considere-os tendo o mesmo tamanho. No entanto, esta abordagem não é convincente sob a definição natural de tamanho.

Para isto precisamos do conceito de bijeção. Embora uma "bijeção" pareça ser um conceito mais avançado que um número, a matemática tradicional em termos de teoria dos conjuntos define funções antes de números, já que eles são baseados em conjuntos muito mais simples. Daí surge o conceito de bijeção: Dada a correspondência

a ↔ 1, b ↔ 2, c ↔ 3

Já que cada elemento de { a, b, c } está emparelhado com precisamente um elemento de { 1, 2, 3 }, e vice-versa, temos uma bijeção.

Agora generalize essa situação e defina dois conjuntos de mesmo tamanho se (e somente se) existe uma bijeção entre eles. Para todo conjunto finito, isso nos dá a definição usual de "o mesmo tamanho". O que podemos concluir sobre o tamanho de conjuntos infinitos?

Considere os conjuntos A = { 1, 2, 3, ... }, o conjunto dos inteiros positivos e B = { 2, 4, 6, ... }, o conjunto dos inteiros positivos pares. Afirmamos que, sob nossa definição, esses conjuntos têm o mesmo tamanho, e que portanto B é infinito contável. Para provar isso precisamos exibir uma bijeção entre eles. Mas isto é fácil, usando n ↔ 2n, então

1 ↔ 2, 2 ↔ 4, 3 ↔ 6, 4 ↔ 8, ....

Como no exemplo anterior, cada elemento de A está emparelhado com precisamente um elemento de B, e vice-versa. Portanto eles têm o mesmo tamanho. Este é um exemplo de um conjunto que tem o mesmo tamanho de seu subconjunto próprio, uma situação que é impossível para conjuntos finitos.

Do mesmo modo, o conjunto de todos os pares ordenados dos números naturais é infinito contável, como demonstrado na figura:

A função de emparelhamento de Cantor atribui um número natural para cada par de números naturais

O mapeamento resultante seria:

0 ↔ (0,0), 1 ↔ (1,0), 2 ↔ (0,1), 3 ↔ (2,0), 4 ↔ (1,1), 5 ↔ (0,2), 6 ↔ (3,0) ....

É claro que este mapeamento cobrirá todos os pares ordenados.

É interessante observar que se você tratar cada par como sendo o numerador e denominador de uma fração simples, então para cada fração positiva, podemos definir um número distinto correspondente a ela. Essa representação também inclui os números naturais, já que todo número natural também é uma fração N/1. Então podemos concluir que existem exatamente tantos números racionais positivos quanto inteiros positivos. Isso também se aplica para números racionais, como pode ser visto abaixo (para lidar com números negativos, é necessária uma representação mais complexa).

Teorema: O produto cartesiano de uma quantidade ﬁnita de conjuntos contáveis é contável.

Esta forma de mapeamento triangular é generalizada recursivamente para vetores de uma quantidade infinita de números naturais, mapeando repetidamente os primeiros dois elementos para um número natural. Por exemplo, (0,2,3) é mapeado para (5,3) que é mapeado para 39.

Algumas vezes é necessário mais de um mapeamento, quando você mapeia o conjunto que você deseja provar que é infinito contável, em outro conjunto. Por exemplo, os números racionais positivos podem facilmente ser mapeados para os pares de números naturais (ou um subconjunto desses), pois p/q mapeia para (p, q).

O que acontece com os subconjuntos infinitos de conjuntos infinito contáveis? Eles têm menos elementos que N?

Teorema: Todo subconjunto de um conjunto contável é contável. Em particular, todo subconjunto infinito de um conjunto infinito contável é infinito contável.

Por exemplo, o conjunto dos números primos é contável, mapeando o n-ésimo número primo para n:

2 mapeia para 1
3 mapeia para 2
5 mapeia para 3
7 mapeia para 4
11 mapeia para 5
13 mapeia para 6
17 mapeia para 7
19 mapeia para 8
23 mapeia para 9
etc.

O que acontece com conjuntos "maiores que" N? Um exemplo óbvio seria Q, o conjunto de todos os números racionais, que intuitivamente pode parecer muito maior que N. Mas as aparências enganam:

Teorema: Q (o conjunto de todos os números racionais) é contável.

Q pode ser definido como o conjunto de todas as frações a/b onde a e b são inteiros e b > 0. Isto pode ser mapeado no subconjunto de triplas ordenadas de números naturais (a, b, c) tal que a ≥ 0, b > 0, a e b são primos entre si, e c ∈ {0, 1} tal que c = 0 se a/b ≥ 0 e c = 1 caso contrário.

0 mapeia para (0,1,0)
1 mapeia para (1,1,0)
−1 mapeia para (1,1,1)
1/2 mapeia para (1,2,0)
−1/2 mapeia para (1,2,1)
2 mapeia para (2,1,0)
−2 mapeia para (2,1,1)
1/3 mapeia para (1,3,0)
−1/3 mapeia para (1,3,1)
3 mapeia para (3,1,0)
−3 mapeia para (3,1,1)

1/4 mapeia para (1,4,0)
−1/4 mapeia para (1,4,1)
2/3 mapeia para (2,3,0)
−2/3 mapeia para (2,3,1)
3/2 mapeia para (3,2,0)
−3/2 mapeia para (3,2,1)
4 mapeia para (4,1,0)
−4 mapeia para (4,1,1)
...

De um modo similar, o conjunto dos números algébricos é contável, e também o conjunto dos números definíveis.

Teorema: (assumindo o axioma da escolha) A união de um sistema ﬁnito de conjuntos contáveis é contável.

Por exemplo, dados conjuntos contáveis A, B, C ...

Usando uma variante da enumeração triangular vista anteriormente:

a₀ mapeia para 0

a₁ mapeia para 1
b₀ mapeia para 2

a₂ mapeia para 3
b₁ mapeia para 4
c₀ mapeia para 5

a₃ mapeia para 6
b₂ mapeia para 7
c₁ mapeia para 8
d₀ mapeia para 9

a₄ mapeia para 10
...

Note que isto só funciona se os conjuntos A, B, C,... são disjuntos. Se não, então a união é até mesmo menor e é também portanto contável pelo teorema anterior.

Note também que o axioma da escolha é necessário para indexar todos os conjuntos A, B, C, ...

Teorema: O conjunto de todas as sequências de tamanho finito dos números naturais é contável.

Este conjunto é a união das sequências de tamanho 1, as sequências de tamanho 2, as sequências de tamanho 3, cada uma delas é um conjunto contável (produto cartesiano finito). Então nós estamos falando de uma união contável de conjuntos contáveis, que é contável pelo teorema anterior.

Teorema: O conjunto de todos os subconjuntos finitos dos números naturais é contável.

Se você tem um subconjunto finito, você pode ordenar os elementos em uma sequência finita. Existe apenas um sistema finito de sequências finitas, como também existe apenas um sistema finito de subconjuntos finitos.

O teorema seguinte fornece formulações equivalentes em termos de função bijetora ou sobrejetora. Uma prova deste resultado pode ser encontrada no texto de Lang.^[2]

Teorema: Seja S um conjunto. As seguintes declarações são equivalentes:

S é contável, ou seja, existe uma função injetora
$f\colon S\to \mathbb {N}$ .
Ou S é vazio, ou existe uma função sobrejetora
$g\colon \mathbb {N} \to S$ .
Ou S é finito ou existe uma bijeção
$h\colon \mathbb {N} \to S$ .

Muitas propriedades padrões são concluídas facilmente a partir deste teorema. Nós as apresentamos aqui laconicamente. Para uma apresentação mais suave veja as seções abaixo. Observe que $\mathbb {N}$ no teorema pode ser substituído por qualquer conjunto infinito contável. Em particular temos o seguinte corolário.

Corolário: Seja S e T conjuntos.

Se a função
$f\colon S\to T$ é injetora e T é contável então S é contável.
Se a função
$g:S\to T$ é sobrejetora e S é contável então T é contável.

Prova: Para (1) observe que se T é contável existe uma função injetora $h:T\to \mathbb {N} .$ Então se $f:S\to T$ é injetora a composição $h\circ f:S\to \mathbb {N}$ é injetora, então S é contável.

Para (2) observe que se S é contável existe uma função sobrejetora $h:\mathbb {N} \to S.$ Então se $g\colon S\to T$ é sobrejetora a composição $g\circ h:\mathbb {N} \to T$ é sobrejetora, então T é contável.

Proposição: Todo subconjunto de um conjunto contável é contável.

Prova: a restrição de uma função injetora para um subconjunto de seu domínio é também injetora.

Proposição: O produto cartesiano de dois conjuntos contáveis A e B é contável.

Prova: Note que $\mathbb {N} \times \mathbb {N}$ é contável como uma consequência da definição, pois a função $f:\mathbb {N} \times \mathbb {N} \to \mathbb {N}$ dada por $f(m,n)=2^{m}3^{n}$ é injetora. Conclui-se do Teorema Básico e do Corolário que o produto cartesiano de quaisquer dois conjuntos contáveis é contável, pois se A e B são contáveis existem funções sobrejetoras $f:\mathbb {N} \to A$ e $g:\mathbb {N} \to B$ . Então

f\times g:\mathbb {N} \times \mathbb {N} \to A\times B

é uma função sobrejetora do conjunto contável $\mathbb {N} \times \mathbb {N}$ para o conjunto $A\times B$ e o corolário implica $A\times B$ é contável. Este resultado é generalizado para o produto cartesiano de qualquer sistema finito de conjuntos contáveis e a prova é por indução sobre o número de conjuntos do sistema.

Proposição: Os inteiros $\mathbb {Z}$ são contáveis e os números racionais $\mathbb {Q}$ são contáveis.

Prova: Os inteiros $\mathbb {Z}$ são contáveis, pois a função $f\colon \mathbb {Z} \to \mathbb {N}$ dada por $f(n)=2^{n}$ se n não é negativo e $f(n)=3^{|n|}$ se n é negativo, é uma função injetora. Os números racionais $\mathbb {Q}$ são contáveis porque a função $g\colon \mathbb {Z} \times \mathbb {N} \to \mathbb {Q}$ dada por $g(m,n)=m/(n+1)$ é uma função sobrejetora do conjunto contável $\mathbb {Z} \times \mathbb {N}$ para os racionais $\mathbb {Q}$ .

Proposição: Se $A_{n}$ é um conjunto contável para todo $n\in \mathbb {N}$ então $\bigcup _{n\in \mathbb {N} }A_{n}$ é contável.

Prova: Esta é uma consequência do fato de que para todo n existe uma função sobrejetora $g_{n}:\mathbb {N} \to A_{n}$ e portanto a função

G:\mathbb {N} \times \mathbb {N} \to \bigcup _{n\in \mathbb {N} }A_{n}

dada por $G(n,m)=g_{n}(m)$ é sobrejetora. Já que $\mathbb {N} \times \mathbb {N}$ é contável o Corolário implica $\bigcup _{n\in \mathbb {N} }A_{n}$ é contável. Estamos usando o axioma da escolha nesta prova, com o intuito de escolher para todo $n\in \mathbb {N}$ uma função sobrejetora $g_{n}$ do sistema não vazio de funções sobrejetoras de $\mathbb {N}$ para $A_{n}$ .

O Teorema de Cantor afirma que se $A$ e um conjunto e ${\mathcal {P}}(A)$ é seu conjunto das partes, ou seja, o conjunto de todos os subconjuntos de $A$ , então não existe função sobrejetora de $A$ para ${\mathcal {P}}(A)$ . Como uma consequência imediata disto e do Teorema Básico acima, temos:

Proposição: O conjunto ${\mathcal {P}}(\mathbb {N} )$ não é contável; ou seja, é incontável.

Para uma elaboração deste resultado veja Argumento de diagonalização de Cantor.

O conjunto dos números reais é incontável, como também o conjunto de todas as sequências infinitas dos números naturais.

Modelo mínimo da teoria dos conjuntos é contável

Se existe um conjunto que seja um modelo padrão da teoria dos conjuntos ZFC, então existe um modelo padrão mínimo (veja Universo construível). O Teorema de Löwenheim-Skolem pode ser usado para mostrar que esse modelo mínimo é contável. O fato que a noção de "incontabilidade" faz sentido mesmo nesse modelo, e em particular que esse modelo M contém elementos que são

subconjuntos de M, portanto contável,
mas incontável sob o ponto de vista de M,

foi visto como um paradoxo nos primeiros anos da teoria dos conjuntos.

O modelo padrão mínimo inclui todos os números algébricos e todos os números transcendentes efetivamente computáveis, como também muitos outros tipos de números.

Ordenações totais

Conjuntos contáveis podem ser totalmente ordenados de várias maneiras, por exemplo:

Relações bem-ordenadas (veja também Número ordinal)
- A ordem comum dos números naturais
- Os inteiros na ordem 0, 1, 2, 3, ..., -1, -2, -3, ...
Outras:
- A ordem comum dos inteiros
- A ordem comum dos números racionais

Ver também

Notas

↑ Para um exemplo deste uso, veja (Rudin 1976, Chapter 2)
↑ ^a ^b Veja (Lang 1993, §2 of Chapter I).
↑ Veja (Apostol 1969, Chapter 13.19).
↑ Já que existe uma clara bijeção entre $\mathbb {N}$ e $\mathbb {N} ^{*}=\{1,2,3,...\},$ não faz diferença se 0 é considerado um número natural ou não.

Referências

Lang, Serge (1993), Real and Functional Analysis, ISBN 0-387-94001-4, Berlin, New York: Springer-Verlag
Rudin, Walter (1976), Principles of Mathematical Analysis, ISBN 0-07-054235-X, New York: McGraw-Hill

Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.

[Rudin-1] Para um exemplo deste uso, veja (Rudin 1976, Chapter 2)

[Lang-2] Veja (Lang 1993, §2 of Chapter I).

[Apostol-3] Veja (Apostol 1969, Chapter 13.19).

[4] Já que existe uma clara bijeção entre $\mathbb {N}$ e $\mathbb {N} ^{*}=\{1,2,3,...\},$ não faz diferença se 0 é considerado um número natural ou não.

[1]

[2]

[3]

[4]

v d e Teoria dos conjuntos
Axiomas	Axioma da escolha Axioma da escolha numerável Princípio da Escolha Dependente Axioma da extensão Axioma do infinito Axioma do par Axioma da potência Axioma da regularidade Axioma da união Axioma da substituição Axioma da separação Hipótese do continuum Axioma de Martin Propriedade de grande cardinal
Operações	Produto cartesiano Teoremas de De Morgan Interseção Conjunto de partes Complementar Diferença simétrica União
Conceitos	Cardinalidade Número cardinal Classe Universo construível Elemento Família Função bijectiva Número ordinal Indução transfinita Diagrama de Venn
Conjuntos	Argumento de diagonalização de Cantor Conjunto contável Conjunto vazio Conjunto finito Conjunto difuso Conjunto hereditariamente finito Conjunto infinito Conjunto recursivo Subconjunto Conjunto transitivo Conjunto não enumerável Conjunto universo
Teorias	Teoria axiomática dos conjuntos Teorema de Cantor Forçamento Teoria de conjuntos de Morse–Kelley Teoria ingênua dos conjuntos New Foundations Paradoxos Principia mathematica Paradoxo de Russell Problema de Suslin NBG Teoria de conjuntos de Zermelo ZFC Teorias de conjuntos alternativas
Pessoas	Abraham Fraenkel Bertrand Russell Ernst Zermelo Georg Cantor John von Neumann Kurt Gödel Lotfali Askar-Zadeh Paul Bernays Paul Cohen Richard Dedekind Thomas Jech Willard Quine