Axioma da escolha

O axioma da escolha diz que se você tiver uma coleção de cestas, cada qual contendo pelo menos um objeto, então é possível afirmar a existência de um conjunto, o conjunto de escolha, que contém exatamente um objeto de cada cesta—mesmo que haja um número infinito de cestas e não haja nenhuma regra que estabeleça qual objeto de cada cesta deve ser escolhido para formar parte desse conjunto. Por exemplo, você não precisa do axioma da escolha para escolher um sapato de cada par, dentre um número infinito de pares de sapatos. É possível estabelecer uma regra como: pegar sempre o pé direito para formar um outro conjunto. Por outro lado, para escolher uma meia de cada par, dentre um número infinito de pares, é necessário utilizar o axioma da escolha. Sendo as meias de cada par iguais, não é possível estabelecer uma regra. O axioma da escolha afirma que o conjunto de escolha existe e contém uma meia de cada par.

Seja X {\displaystyle X} um conjunto cujos elementos são conjuntos não-vazios. Uma função f {\displaystyle f} de domínio X {\displaystyle X} tal que f ( x ) ∈ x ∀ x ∈ X {\displaystyle f(x)\in x\ \forall x\in X} é denominada uma função de escolha. O axioma da escolha é o enunciado: para todo conjunto X {\displaystyle X} de conjuntos não vazios, existe uma função de escolha. Em termos formais, ∀ C , ∅ ∉ C ⟹ ( ∃ Φ ∈ F ( C , ∪ C ) : ( ∀ A ∈ C , Φ ( A ) ∈ A ) ) {\displaystyle \forall C,\emptyset \notin C\implies \left(\exists \Phi \in {\mathcal {F}}(C,\cup C):\left(\forall A\in C,\Phi (A)\in A\right)\right)} Assim, a negação do axioma da escolha diz que existe um conjunto de conjuntos não-vazios que não possui função de escolha. Cada função de escolha numa coleção X de conjuntos não vazios é um elemento do Produto Cartesiano dos conjuntos em X. Essa não é a situação mais geral de um produto Cartesiano de uma família de conjuntos, onde o mesmo conjunto pode ocorrer mais de uma vez como um fator; entretanto, pode-se focar em elementos de um certo produto que escolhe o mesmo elemento toda vez que um dado conjunto aparece como fator, e tais elementos correspondem a um elemento do produto Cartesiano de todos os conjuntos distintos na família. O axioma da escolha garante a existência de tais elementos; sendo assim equivalente a:

Até o final do século XIX, o Axioma da Escolha foi sempre usado implicitamente, embora ainda não formalmente definido. Por exemplo, depois de estabelecido que o conjunto X {\displaystyle X} contém apenas conjuntos não-vazios, um matemático poderia dizer "faça F ( s ) {\displaystyle F(s)} ser um dos membros de s {\displaystyle s} para todo s s {\displaystyle s} em X {\displaystyle X} " para definir a função F {\displaystyle F} . Em geral, é impossível provar que F {\displaystyle F} existe sem o Axioma da Escolha, mas isso parece ter passado despercebido até para Zermelo. Nem toda situação requer o Axioma da Escolha. Para conjuntos finitos X {\displaystyle X} , o Axioma da Escolha segue dos outros axiomas da teoria dos conjuntos. Nesse caso é equivalente a dizer que se tivermos várias caixas (um número finito), cada uma contendo pelo menos um item, então podemos escolher exatamente um item de cada caixa. Claramente podemos fazer isso: Começamos pela primeira caixa, escolhemos um item; vai para a segunda caixa, escolhemos um item; e assim sucessivamente. O número de caixas é finito, então eventualmente nosso procedimento de escolha irá terminar. O resultado é uma função de escolha explícita: uma função que pega a primeira caixa para o primeiro elemento que escolhemos, a segunda caixa para o segundo elemento que escolhemos, e assim sucessivamente. (Uma prova formal para todos os conjuntos finitos usaria o princípio da indução matemática para provar "para todo número natural k {\displaystyle k} , toda família de k {\displaystyle k} conjuntos não-vazios tem uma função de escolha"). Esse método não pode, entretanto, ser usado para mostrar que toda família contável de conjuntos não-vazios tem uma função de escolha, como é afirmada pelo axioma da escolha contável. Se o método é aplicado a uma sequência infinita ( X i : i ∈ ω ) {\displaystyle (X_{i}:i\in \omega )} de conjuntos não-vazios, uma função é obtida a cada etapa finita, mas não existe uma etapa tal que uma função de escolha seja construída para a família inteira, nenhuma função de escolha "limite" pode ser construída, em geral, na ZF sem o Axioma da Escolha.

A natureza dos conjuntos não-vazios individuais na coleção pode tornar possível evitar o Axioma da Escolha para certas coleções infinitas. Por exemplo, suponha que cada membro da coleção X é um subconjunto não-vazio dos números naturais. Todo tal subconjunto tem um menor elemento, então para especificar nossa função de escolha, podemos simplesmente dizer que ela mapeia cada conjunto para o menor elemento desse conjunto. Isso nos dá uma escolha definida de um elemento de cada conjunto, e torna desnecessário aplicar o Axioma da Escolha. A dificuldade aparece quando não existe escolha natural dos elementos de cada conjunto. Se não podemos fazer escolhas explícitas, como podemos saber que nosso conjunto existe? Por exemplo, suponha que X é o conjunto de todos os subconjuntos não-vazios dos números reais. Primeiro poderíamos tentar proceder como se X fosse finito. Se tentarmos escolher um elemento de cada conjunto, então, pelo fato de X ser infinito, nosso procedimento de escolha nunca vai acabar, e consequentemente, nunca estaremos aptos a produzir uma função de escolha para todo X. Depois, poderíamos tentar especificar o menor elemento de cada conjunto. Mas, alguns subconjuntos dos número reais não possuem menor elemento. Por exemplo, o intervalo aberto (0,1) não possui um menor elemento: se x pertence a (0,1), então x/2 também pertence, e x/2 é sempre estritamente menor que x. Logo esta tentativa também falha.

Uma prova que exige o axioma da escolha pode estabelecer a existência de um objeto sem explicitamente definir o objeto na linguagem da teoria dos conjuntos. Por exemplo, enquanto o Axioma da Escolha implica que existe uma boa ordenação dos números reais, existem modelos da teoria dos conjuntos com o Axioma da Escolha no qual é impossível definir uma boa ordenação dos reais. Semelhantemente, embora um subconjunto dos números reais que não esteja na Medida de Lebesgue pode ser provado que exista usando o Axioma da Escolha, é consistente que tal conjunto não é definível. O Axioma da Escolha produz esses intangíveis (objetos que são provados existir, mas que não podem ser explicitamente construídos), que podem conflitar com alguns princípios filosóficos. Pelo fato de não existir boa ordenação canônica de todos os conjuntos, uma construção que baseia-se em uma boa ordenação pode não produzir um resultado canônico, mesmo que um resultado canônico seja desejado (como é sempre o caso na teoria das categorias). Isso vem sendo usado como um argumento contra o uso do Axioma da Escolha.

Kurt Gödel demonstrou a consistência relativa do Axioma da Escolha com os demais axiomas de ZF, ou seja, C o n ( Z F ) → C o n ( Z F C ) {\displaystyle Con(ZF)\rightarrow Con(ZFC)} , onde C o n ( x ) {\displaystyle Con(x)} significa "x é consistente". A. Fraenkel e, de uma maneira precisa, A. Mostowski, demonstraram a independência do Axioma da Escolha (AE) em Teoria de Conjuntos com átomos (urelementos, alemão:Urelemente), denominada ZFA, na qual não vale o Axioma da Regularidade. Com efeito, usando modelos de permutação demonstraram que, se ZFA é consistente, então ZFA + "existe um conjunto enumerável de pares sem função de escolha" também é consistente. Usando o método de forcing, por ele idealizado, Paul J. Cohen demonstrou a independência relativa aos demais axiomas de ZF (incluindo o Axioma da Regularidade): Se ZF é consistente, então ZF + "existe um conjunto enumerável de pares de conjuntos de números reais sem função de escolha" também é consistente.

O matemático Kurt Gödel definiu um modelo de ZFC denominado o universo construível, abreviado L, no qual valem a hipótese do continuo generalizada e o Axioma de Construtibilidade, V=L. Usando esse modelo mostrou que dentro da teoria ZFC não se pode provar a negação da hipótese do continuo se ZF é consistente. Por sua vez, Paul J. Cohen mostrou que a hipótese do continuo é independente dos axiomas da teoria ZFC, se eles forem consistentes. No entanto, a hipótese do continuo generalizada implica o axioma da escolha na teoria ZF.

Como discutido acima, em ZFC o Axioma da Escolha é capaz de fornecer "provas não construtivas" na qual a existência de um objeto é provada embora nenhum exemplo explícito é construído. ZFC, entretanto, ainda está formalizada na lógica clássica. O Axioma da Escolha também tem sido estudada no contexto da matemática construtiva, onde lógica não-clássica é empregada. O estado do Axioma da Escolha varia entre diferentes variedades de matemática construtiva. Na teoria dos tipos de Martin-Löf e altam ordem aritmética de Heyting, a afirmação apropriada do Axioma da Escolha é (dependendo da abordagem) incluída como uma axioma ou provada como um teorema. Errett Bishop argumentou que o Axioma da Escolha era construtivamente aceitável, dizendo Na teoria dos conjuntos construtiva, entretanto, o teorema de Diaconescu's mostra que o Axioma da Escolha implica a lei do meio excluído (ao contrário como na teoria dos tipos de Martin-Löf, onde isso não acontece). Assim o Axioma da Escolha não está geralmente disponível na teoria dos conjuntos construtiva. Uma causa para essa diferença é que o Axioma da Escolha na teoria dos tipos não tem a propriedade da extensionalidade que o Axioma da Escolha na teoria dos conjuntos construtiva tem.

O axioma da construtibilidade e a hipótese generalizada do contínuo ambas implicam o Axioma da Escolha, mas são estritamente mais fortes do que ele. Na teoria das classes como na teoria dos conjuntos de Von Neumann–Bernays–Gödel e na teoria dos conjuntos de Morse-Kelley, existe um axioma possível chamado de axioma da escolha global que é mais forte do que o Axioma da Escolha para conjuntos porque também se aplica para classes próprias. E o axioma da escolha global segue do axioma do tamanho limitado.

Existem importantes afirmações que, assumindo os axiomas de ZF mas nem AC nem ¬AC, são equivalentes ao Axioma da Escolha. O mais importante entre eles são o Lema de Zorn e o teorema da boa ordenação. De fato, Zermelo inicialmente introduziu o Axioma da Escolha para formalizar sua prova sobre o teorema da boa ordenação.