Conjunto contável

Um conjunto S é dito contável se existe uma função injetora f de S para os números naturais N = { 0 , 1 , 2 , 3 , . . . } . {\displaystyle \mathbb {N} =\{0,1,2,3,...\}.} 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.

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 } {\displaystyle \{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 , … , 100 } {\displaystyle \{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 , … } {\displaystyle \{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.

Por definição um conjunto S é contável se existe uma função injetora de S para o conjunto dos números naturais N = { 0 , 1 , 2 , 3 , . . . } . {\displaystyle \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 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.

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 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.

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