Conjunto contável - Countable set

Em matemática , um conjunto contável é um conjunto com a mesma cardinalidade ( número de elementos) que algum subconjunto do conjunto de números naturais . Um conjunto contável é um conjunto finito ou um conjunto infinito contável . Sejam finitos ou infinitos, os elementos de um conjunto contável podem sempre ser contados um de cada vez e - embora a contagem possa nunca terminar - cada elemento do conjunto está associado a um número natural único.

Georg Cantor introduziu o conceito de conjuntos contáveis, contrastando conjuntos que são contáveis ​​com aqueles que são incontáveis . Hoje, os conjuntos contáveis ​​formam a base de um ramo da matemática chamado matemática discreta .

Uma nota sobre a terminologia

Embora os termos "contável" e "contável infinito", conforme definidos aqui, sejam bastante comuns, a terminologia não é universal. Um estilo alternativo usa contável para significar o que aqui é chamado de infinito contável e, no máximo, contável para significar o que é aqui chamado de contável. Para evitar ambigüidades, pode-se limitar-se aos termos "no máximo contável" e "infinito contável", embora no que diz respeito à concisão este seja o pior dos dois mundos. O leitor é aconselhado a verificar a definição em uso ao encontrar o termo "contável" na literatura.

Os termos enumerável e denumerável também podem ser usados, por exemplo, referindo-se a contável e contável infinito respectivamente, mas como as definições variam, o leitor é mais uma vez aconselhado a verificar a definição em uso.

Definição

A definição mais concisa é em termos de cardinalidade . Um conjunto S é contável se sua cardinalidade | S | é menor do que ou igual a ( alef-nulo ), a cardinalidade do conjunto de números naturais N . Um conjunto S é contávelmente infinito se | S | = . Um conjunto é incontável se não for contável, ou seja, sua cardinalidade é maior que ; o leitor é encaminhado ao conjunto incontável para uma discussão mais aprofundada.

Equivalentemente, um conjunto S é contável se :

Da mesma forma, um conjunto S é contavelmente infinito se :

  • existe uma injetivo e sobrejetivo (e, por conseguinte, bijective mapeamento) entre S e N . Em outras palavras, é um conjunto contavelmente infinito se tem um-para-um correspondência com o conjunto número natural, N .
  • Os elementos de S podem ser organizados em uma sequência infinita , onde é distinto de for e todos os elementos de S são listados.

História

Em 1874, em seu primeiro artigo sobre a teoria dos conjuntos , Cantor provou que o conjunto de números reais é incontável, mostrando que nem todos os conjuntos infinitos são contáveis. Em 1878, ele usou correspondências um a um para definir e comparar cardinalidades. Em 1883, ele estendeu os números naturais com seus ordinais infinitos e usou conjuntos de ordinais para produzir uma infinidade de conjuntos com cardinalidades infinitas diferentes.

Introdução

Um conjunto é uma coleção de elementos e pode ser descrito de várias maneiras. Uma maneira é simplesmente listar todos os seus elementos; por exemplo, o conjunto que consiste nos inteiros 3, 4 e 5 pode ser denotado {3, 4, 5}, denominado forma de lista. No entanto, isso só é eficaz para conjuntos pequenos; para conjuntos maiores, isso seria demorado e sujeito a erros. Em vez de listar cada elemento, às vezes uma reticência ("...") é usada para representar muitos elementos entre o elemento inicial e o elemento final em um conjunto, se o escritor acreditar que o leitor pode facilmente adivinhar o que ... representa ; por exemplo, {1, 2, 3, ..., 100} presumivelmente denota o conjunto de inteiros de 1 a 100. Mesmo neste caso, no entanto, ainda é possível listar todos os elementos, porque o número de elementos no conjunto é finito.

Alguns conjuntos são infinitos ; esses conjuntos têm mais de n elementos, onde n é qualquer número inteiro que pode ser especificado. (Não importa quão grande seja o número inteiro especificado n , como n = 9 × 10 32 , conjuntos infinitos têm mais de n elementos.) Por exemplo, o conjunto de números naturais, denotável por {0, 1, 2, 3, 4 , 5, ...}, tem infinitamente muitos elementos e não podemos usar nenhum número natural para dar seu tamanho. No entanto, verifica-se que os conjuntos infinitos têm uma noção bem definida de tamanho (ou mais apropriadamente, cardinalidade , o termo técnico para o número de elementos em um conjunto), e nem todos os conjuntos infinitos têm a mesma cardinalidade.

Mapeamento bijetivo de inteiro para números pares

Para entender o que isso significa, primeiro examinamos o que não significa. Por exemplo, há infinitamente muitos inteiros ímpares, infinitamente muitos inteiros pares e (portanto) infinitamente muitos inteiros no geral. No entanto, verifica-se que o número de inteiros pares, que é igual ao número de inteiros ímpares, também é igual ao número de inteiros gerais. Isso ocorre porque podemos organizar as coisas de forma que, para cada inteiro, haja um inteiro par distinto:

ou, de forma mais geral, (veja a imagem). O que fizemos aqui foi organizar os inteiros e pares inteiros em uma correspondência um-para-um (ou bijeção ), que é uma função que mapeia entre dois conjuntos de modo que cada elemento de cada conjunto corresponda a um único elemento no outro definir.

No entanto, nem todos os conjuntos infinitos têm a mesma cardinalidade. Por exemplo, Georg Cantor (que introduziu este conceito) demonstrou que os números reais não podem ser colocados em correspondência um a um com os números naturais (inteiros não negativos) e, portanto, que o conjunto de números reais tem uma cardinalidade maior do que o conjunto de números naturais.

Visão geral formal

Por definição, um conjunto S é contável se existe uma função injetiva f  : SN de S para os números naturais N = {0, 1, 2, 3, ...}. Significa simplesmente que cada elemento em S tem a correspondência de um elemento diferente em N .

Pode parecer natural dividir os conjuntos em classes diferentes: coloque todos os conjuntos contendo um elemento juntos; todos os conjuntos contendo dois elementos juntos; ...; finalmente, reúna todos os conjuntos infinitos e considere-os como tendo o mesmo tamanho. Essa visão não é sustentável, entretanto, sob a definição natural de tamanho.

Para elaborar isso, precisamos do conceito de bijeção . Embora uma "bijeção" possa parecer um conceito mais avançado do que um número, o desenvolvimento usual da matemática em termos de teoria dos conjuntos define funções antes dos números, visto que são baseadas em conjuntos muito mais simples. É aqui que entra o conceito de bijeção: definir a correspondência

a ↔ 1, b ↔ 2, c ↔ 3

Uma vez que cada elemento de { a , b , c } é pareado com precisamente um elemento de {1, 2, 3} e vice-versa, isso define uma bijeção.

Agora generalizamos essa situação; nós definir que dois conjuntos são do mesmo tamanho, se e somente se existe uma bijeção entre eles. Para todos os conjuntos finitos, isso nos dá a definição usual de "o mesmo tamanho".

Quanto ao caso de conjuntos infinitos, considere os conjuntos A = {1, 2, 3, ...}, o conjunto de inteiros positivos , e B = {2, 4, 6, ...}, o conjunto de pares inteiros positivos. Afirmamos que, em nossa definição, esses conjuntos têm o mesmo tamanho e que, portanto, B é contavelmente infinito. Lembre-se de que, para provar isso, precisamos exibir uma bijeção entre eles. Isso pode ser alcançado usando a atribuição n ↔ 2 n , de modo que

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

Como no exemplo anterior, cada elemento de A foi emparelhado com precisamente um elemento de B e vice-versa. Portanto, eles têm o mesmo tamanho. Este é um exemplo de um conjunto do mesmo tamanho que um de seus subconjuntos apropriados , o que é impossível para conjuntos finitos.

Da mesma forma, o conjunto de todos os pares ordenados de números naturais (o produto cartesiano de dois conjuntos de números naturais, N × N ) é contavelmente infinito, como pode ser visto seguindo um caminho como o da imagem:

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

O mapeamento resultante procede da seguinte maneira:

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

Este mapeamento cobre todos esses pares ordenados.

Esta forma de mapeamento triangular generaliza recursivamente para n - tuplas de números naturais, ou seja, ( a 1 , a 2 , a 3 , ..., a n ) onde a i e n são números naturais, mapeando repetidamente os primeiros dois elementos de um n- duplo para um número natural. Por exemplo, (0, 2, 3) pode ser escrito como ((0, 2), 3). Então (0, 2) mapeia para 5 então ((0, 2), 3) mapeia para (5, 3), então (5, 3) mapeia para 39. Como uma 2-tupla diferente, isso é um par como ( a , b ) mapeia para um número natural diferente, uma diferença entre duas n-tuplas por um único elemento é suficiente para garantir que as n-tuplas sejam mapeadas para diferentes números naturais. Assim, uma injeção do conjunto de n -tuples no conjunto de números naturais N é provada. Para o conjunto de n-tuplas feitas pelo produto cartesiano de muitos conjuntos finitos diferentes, cada elemento em cada tupla tem correspondência com um número natural, então cada tupla pode ser escrita em números naturais, então a mesma lógica é aplicada para provar o teorema .

Teorema: O produto cartesiano de um número finito de conjuntos contáveis ​​é contável.

O conjunto de todos os inteiros Z e o conjunto de todos os números racionais Q podem intuitivamente parece muito maior do que N . Mas as aparências podem enganar. Se um par é tratado como o numerador e denominador de uma fracção vulgar (uma fracção sob a forma de uma / b , onde um e b ≠ 0 são números inteiros), em seguida, para cada fracção positiva, podemos chegar a um número natural distinta correspondendo para isso. Essa representação também inclui os números naturais, uma vez que todo número natural também é uma fração N / 1. Portanto, podemos concluir que existem exatamente tantos números racionais positivos quanto inteiros positivos. Isso também é verdadeiro para todos os números racionais, como pode ser visto a seguir.

Teorema: Z (o conjunto de todos os inteiros) e Q (o conjunto de todos os números racionais) são contáveis.

De maneira semelhante, o conjunto de números algébricos é contável.

Às vezes, mais de um mapeamento é útil: um conjunto A a ser mostrado como contável é mapeado um a um (injeção) para outro conjunto B, então A é provado como contável se B for mapeado um a um ao conjunto de números naturais. Por exemplo, o conjunto de números racionais positivos pode ser facilmente mapeado um para um ao conjunto de pares de números naturais (2-tuplas) porque p / q mapeia para ( p , q ). Uma vez que o conjunto de pares de números naturais é mapeado um a um (na verdade, correspondência ou bijeção um a um) para o conjunto de números naturais como mostrado acima, o conjunto de números racionais positivos é provado como contável.

Teorema: Qualquer união finita de conjuntos contáveis ​​é contável.

Com a previdência de saber que existem incontáveis ​​conjuntos, podemos nos perguntar se este último resultado pode ou não ser levado mais longe. A resposta é "sim" e "não", podemos estendê-la, mas precisamos assumir um novo axioma para fazê-lo.

Teorema: (assumindo o axioma da escolha contável ) A união de muitos conjuntos contáveis ​​é contável.

Por exemplo, dados conjuntos contáveis a , b , c , ...

Enumeração para número contável de conjuntos contáveis

Usando uma variante da enumeração triangular que vimos acima:

  • a 0 mapeia a 0
  • um 1 mapeia para 1
  • b 0 mapeia para 2
  • a 2 mapeia a 3
  • b 1 mapeia para 4
  • c 0 mapeia para 5
  • a 3 mapeia a 6
  • b 2 mapeia para 7
  • c 1 mapeia para 8
  • d 0 mapeia para 9
  • a 4 mapeia a 10
  • ...

Isso só funciona se os conjuntos a , b , c , ... forem separados . Caso contrário, a união é ainda menor e, portanto, também pode ser contada por um teorema anterior.

Precisamos do axioma da escolha contável para indexar todos os conjuntos a , b , c , ... simultaneamente.

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

Esse conjunto é a união das sequências de comprimento 1, das sequências de comprimento 2 e das sequências de comprimento 3, cada uma das quais é um conjunto contável (produto cartesiano finito). Portanto, estamos falando sobre 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.

Os elementos de qualquer subconjunto finito podem ser ordenados em uma sequência finita. Existem apenas muitas sequências finitas contáveis, portanto, também existem apenas muitos subconjuntos finitos contáveis.

Teorema: Sejam S e T conjuntos.

  1. Se a função f  : ST é injetiva e T é contável, então S é contável.
  2. Se a função g  : ST é sobrejetora e S é contável, então T é contável.

Estas decorrem das definições de conjunto contável como funções injetivas / sobrejetivas.

O teorema de Cantor afirma que se A é um conjunto e P ( A ) é seu conjunto de potência , ou seja, o conjunto de todos os subconjuntos de A , então não há função sobrejetiva de A a P ( A ). Uma prova é fornecida no artigo teorema de Cantor . Como consequência imediata disso e do Teorema Básico acima, temos:

Proposição: O conjunto P ( N ) não é contável; ou seja, é incontável .

Para uma elaboração desse resultado, consulte o argumento diagonal de Cantor .

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

O modelo mínimo da teoria dos conjuntos é contável

Se houver um conjunto que é um modelo padrão (consulte o modelo interno ) da teoria de conjuntos ZFC, então há um modelo padrão mínimo ( consulte Universo construtível ). O teorema de Löwenheim – Skolem pode ser usado para mostrar que este modelo mínimo é contável. O fato de que a noção de "incontabilidade" faz sentido mesmo neste modelo e, em particular, que este modelo M contém elementos que são:

  • subconjuntos de M , portanto contáveis,
  • mas incontável do ponto de vista de M ,

foi visto como paradoxal nos primeiros dias da teoria dos conjuntos, consulte o paradoxo de Skolem para mais informações.

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

Pedidos totais

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

  • Ordens de poço (ver também o número ordinal ):
    • A ordem usual dos números naturais (0, 1, 2, 3, 4, 5, ...)
    • Os inteiros na ordem (0, 1, 2, 3, ...; −1, −2, −3, ...)
  • Outros ( pedidos não bem):
    • A ordem usual dos inteiros (..., −3, −2, −1, 0, 1, 2, 3, ...)
    • A ordem usual dos números racionais (não pode ser escrita explicitamente como uma lista ordenada!)

Em ambos os exemplos de ordens de poço aqui, qualquer subconjunto tem um elemento mínimo ; e em ambos os exemplos de ordens de não poço, alguns subconjuntos não têm um elemento mínimo . Esta é a definição chave que determina se um pedido total também é um pedido de poço.

Veja também

Notas

Citações

Referências