Axioma da escolha

Ilustração do axioma da escolha, com cada conjunto S_Eu... representado como um jarro e seus elementos representados como mármores. Cada elemento x_Eu... é representado como um mármore à direita. As cores são usadas para sugerir uma associação funcional de mármores depois de adotar o axioma de escolha. A existência de tal função de escolha é em geral independente de ZF para coleções de cardinalidade infinita.

(S)_Eu...) é uma família indexada infinita de conjuntos indexados sobre os números reais R; isto é, há um conjunto S_Eu... para cada número real Eu..., com uma pequena amostra mostrada acima. Cada conjunto contém pelo menos um, e possivelmente infinitamente muitos elementos. O axioma da escolha nos permite selecionar arbitrariamente um único elemento de cada conjunto, formando uma família correspondente de elementos (x_Eu...) também indexado sobre os números reais, com x_Eu... extraído de S_Eu.... Em geral, as coleções podem ser indexadas sobre qualquer conjunto Eu..., (chamado conjunto de índices que elementos são usados como índices para elementos em um conjunto) não apenas R.

Em matemática, o axioma da escolhaou ACÇÃO, é um axioma da teoria dos conjuntos equivalente à afirmação de que um produto cartesiano de uma coleção de conjuntos não vazios é não vazio. Informalmente colocado, o axioma da escolha diz que dada qualquer coleção de conjuntos, cada um contendo pelo menos um elemento, é possível construir um novo conjunto por escolher arbitrariamente um elemento de cada conjunto, mesmo se a coleção é infinita. Formalmente, afirma que para cada família indexada (SEu...)Eu...∈ ∈ Eu...(S_{i}) I. de conjuntos vazios, existe um conjunto indexado (xEu...)Eu...∈ ∈ Eu...(x_{i}) I. tal que xEu...∈ ∈ SEu...{\displaystyle x_{i}\in}in S_{i}} para todos Eu...∈ ∈ Eu...- Sim.. O axioma da escolha foi formulado em 1904 por Ernst Zermelo para formalizar sua prova do teorema bem ordenado.

Em muitos casos, um conjunto resultante da escolha arbitrária de elementos pode ser feito sem invocar o axioma da escolha; este é, em particular, o caso se o número de conjuntos a partir dos quais escolher os elementos for finito, ou se uma regra canônica sobre como escolher os elementos estiver disponível – alguma propriedade distintiva que por acaso vale para exatamente um elemento em cada conjunto . Um exemplo ilustrativo são os conjuntos escolhidos dos números naturais. A partir desses conjuntos, pode-se sempre selecionar o menor número, por ex. dados os conjuntos {{4, 5, 6}, {10, 12}, {1, 400, 617, 8000}}, o conjunto contendo cada menor elemento é {4, 10, 1}. Nesse caso, "selecione o menor número" é uma função de escolha. Mesmo que infinitos conjuntos sejam coletados dos números naturais, sempre será possível escolher o menor elemento de cada conjunto para produzir um conjunto. Ou seja, a função de escolha fornece o conjunto de elementos escolhidos. No entanto, nenhuma função de escolha definida é conhecida para a coleção de todos os subconjuntos não vazios dos números reais (se houver reais não construíveis). Nesse caso, o axioma da escolha deve ser invocado.

Bertrand Russell cunhou uma analogia: para qualquer coleção (mesmo infinita) de pares de sapatos, pode-se escolher o sapato esquerdo de cada par para obter uma coleção apropriada (ou seja, conjunto) de sapatos; isso torna possível definir uma função de escolha diretamente. Para uma coleção infinita de pares de meias (supostamente sem características distintivas), não há uma maneira óbvia de criar uma função que forme um conjunto de selecionar uma meia de cada par, sem invocar o axioma de escolha.

Embora originalmente controverso, o axioma da escolha agora é usado sem reservas pela maioria dos matemáticos e está incluído na forma padrão da teoria axiomática dos conjuntos, a teoria dos conjuntos de Zermelo-Fraenkel com o axioma da escolha (ZFC). Uma motivação para esse uso é que vários resultados matemáticos geralmente aceitos, como o teorema de Tychonoff, requerem o axioma da escolha para suas provas. Os teóricos dos conjuntos contemporâneos também estudam axiomas que não são compatíveis com o axioma da escolha, como o axioma da determinação. O axioma da escolha é evitado em algumas variedades de matemática construtiva, embora existam variedades de matemática construtiva nas quais o axioma da escolha é adotado.

Declaração

Uma função de escolha (também chamada de seletor ou seleção) é uma função f, definida em uma coleção X de conjuntos não vazios, tal que para cada conjunto A em X, f(A) é um elemento de A. Com este conceito, o axioma pode ser declarado:

Formalmente, isso pode ser expresso da seguinte forma:

Gerenciamento de contas Gerenciamento de contas XNão.∅ ∅ ∉ ∉ X? ? Detalhe Detalhe f:: X→ → ⋃ ⋃ XGerenciamento de contas Gerenciamento de contas A∈ ∈ X(f(A)∈ ∈ A)].{\displaystyle \forall X\left[\varnothing \notin X\implies \exists f\colon X\rightarrow \bigcup X\quad \forall A\in X\,(f(A)\in A)\right]\,.}

Assim, a negação do axioma da escolha afirma que existe uma coleção de conjuntos vazios que não têm função de escolha. (p→ → q⟺ ⟺ ? ? Não.p∧ ∧ (? ? q)]{\displaystyle p\rightarrow q\Longleftrightarrow \lnot [p\land (\lnot q)]}Então... ? ? (p→ → q)⟺ ⟺ p∧ ∧ (? ? q){\displaystyle \lnot (p\rightarrow q)\Longleftrightarrow p\land (\lnot q)} Onde? ? ? - Sim. é negação.)

Cada função de escolha em uma coleção X de conjuntos não vazios é um elemento do produto cartesiano dos conjuntos em X. Esta não é a situação mais geral de um produto cartesiano de uma família de conjuntos, onde um determinado conjunto pode ocorrer mais de uma vez como fator; entretanto, pode-se focar em elementos de tal produto que selecionam o mesmo elemento toda vez que um determinado conjunto aparece como fator, e tais elementos correspondem a um elemento do produto cartesiano de todos os conjuntos distintos da família . O axioma da escolha afirma a existência de tais elementos; é, portanto, equivalente a:

Dada qualquer família de conjuntos vazios, seu produto cartesiano é um conjunto vazio.

Nomenclatura ZF, AC e ZFC

Neste artigo e em outras discussões sobre o Axioma da Escolha, as seguintes abreviações são comuns:

• AC – O Axioma da Escolha.
• ZF – Zermelo–Fraenkel define a teoria omitindo o Axiom da escolha.
• ZFC – Teoria dos conjuntos Zermelo-Fraenkel, estendida para incluir o Axioma da Escolha.

Variantes

Existem muitas outras declarações equivalentes do axioma da escolha. Estes são equivalentes no sentido de que, na presença de outros axiomas básicos da teoria dos conjuntos, eles implicam o axioma da escolha e são por ele implícitos.

Uma variação evita o uso de funções de escolha, na verdade, substituindo cada função de escolha por seu intervalo.

Dado qualquer conjunto X de conjuntos não vazios, existe pelo menos um conjunto C que contém exatamente um elemento em comum com cada um dos conjuntos em X.

Isso garante para qualquer partição de um conjunto X a existência de um subconjunto C de X contendo exatamente um elemento de cada parte do partição.

Outro axioma equivalente considera apenas coleções X que são essencialmente conjuntos de potência de outros conjuntos:

Para qualquer conjunto A, o conjunto de potência de A (com o conjunto vazio removido) tem uma função de escolha.

Os autores que usam esta formulação frequentemente falam da função de escolha em A, mas esta é uma noção ligeiramente diferente de função de escolha. Seu domínio é o conjunto de potência de A (com o conjunto vazio removido) e, portanto, faz sentido para qualquer conjunto A, enquanto com a definição usada em outras partes deste artigo, o O domínio de uma função de escolha em uma coleção de conjuntos é essa coleção e, portanto, só faz sentido para conjuntos de conjuntos. Com essa noção alternativa de função de escolha, o axioma da escolha pode ser expresso de forma compacta como

Cada conjunto tem uma função de escolha.

que é equivalente a

Para qualquer conjunto A há uma função f tal que para qualquer subconjunto não vazio B de A, f(B) mente em B.

A negação do axioma pode assim ser expressa como:

Há um conjunto A tal que para todas as funções f (no conjunto de subconjuntos não vazios de A), há uma B tal que f(B) não se encontra B.

Restrição a conjuntos finitos

A declaração usual do axioma da escolha não especifica se a coleção de conjuntos não vazios é finita ou infinita e, portanto, implica que toda coleção finita de conjuntos não vazios tem uma função de escolha. No entanto, esse caso particular é um teorema da teoria dos conjuntos de Zermelo–Fraenkel sem o axioma da escolha (ZF); é facilmente provado pelo princípio da indução finita. No caso ainda mais simples de uma coleção de um conjunto, uma função de escolha corresponde apenas a um elemento, então esta instância do axioma da escolha diz que todo conjunto não vazio tem um elemento; isso vale trivialmente. O axioma da escolha pode ser visto como afirmando a generalização desta propriedade, já evidente para coleções finitas, para coleções arbitrárias.

Uso

Até o final do século 19, o axioma da escolha era frequentemente usado implicitamente, embora ainda não tivesse sido formalmente declarado. Por exemplo, depois de estabelecer que o conjunto X contém apenas conjuntos não vazios, um matemático poderia ter dito "deixe F(s) ser um dos membros de s para todos os s em X" para definir uma função F. Em geral, é impossível provar que F existe sem o axioma da escolha, mas isso parece ter passado despercebido até Zermelo.

Exemplos

A natureza dos conjuntos individuais não vazios na coleção pode tornar possível evitar o axioma da escolha mesmo para certas coleções infinitas. Por exemplo, suponha que cada membro da coleção X seja um subconjunto não vazio dos números naturais. Cada um desses subconjuntos tem um menor elemento, portanto, para especificar nossa função de escolha, podemos simplesmente dizer que 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 adicionar o axioma da escolha aos nossos axiomas da teoria dos conjuntos.

A dificuldade aparece quando não há escolha natural dos elementos de cada conjunto. Se não podemos fazer escolhas explícitas, como sabemos que nossa seleção forma um conjunto legítimo (conforme definido pelos outros axiomas ZF da teoria dos conjuntos)? Por exemplo, suponha que X é o conjunto de todos os subconjuntos não vazios dos números reais. Primeiro podemos tentar proceder como se X fosse finito. Se tentarmos escolher um elemento de cada conjunto, então, como X é infinito, nosso procedimento de escolha nunca chegará ao fim e, consequentemente, nunca seremos capazes de produzir uma função de escolha para todo de X. Em seguida, podemos tentar especificar o menor elemento de cada conjunto. Mas alguns subconjuntos dos números reais não têm elementos mínimos. Por exemplo, o intervalo aberto (0,1) não tem um elemento mínimo: se x está em (0,1), então x/2 também está, e x/2 é sempre estritamente menor que x. Portanto, esta tentativa também falha.

Além disso, considere por exemplo o círculo unitário S, e a ação em S por um grupo G consistindo de todas as rotações racionais. Ou seja, são rotações por ângulos que são múltiplos racionais de π. Aqui G é contável enquanto S é incontável. Portanto, S se divide em inúmeras órbitas sob G. Usando o axioma da escolha, poderíamos escolher um único ponto de cada órbita, obtendo um subconjunto incontável X de S com a propriedade de que todas as suas translações por G são disjuntas de X. O conjunto desses traduz particiona o círculo em uma coleção contável de conjuntos disjuntos, que são todos congruentes aos pares. Como X não é mensurável para qualquer medida finita aditiva invariante de rotação em S, encontrar um algoritmo para formar um conjunto a partir da seleção de um ponto em cada órbita requer que se adicione o axioma da escolha aos nossos axiomas da teoria dos conjuntos. Veja conjunto não mensurável para mais detalhes.

A razão pela qual podemos escolher menos elementos de subconjuntos dos números naturais é o fato de que os números naturais são bem ordenados: todo subconjunto não vazio dos números naturais tem um único elemento mínimo sob a ordem natural. Pode-se dizer: "Embora a ordem usual dos números reais não funcione, pode ser possível encontrar uma ordem diferente dos números reais que seja uma boa ordem. Então, nossa função de escolha pode escolher o menor elemento de cada conjunto sob nossa ordem incomum." O problema passa então a ser o de construir uma boa ordenação, que acaba por exigir o axioma da escolha para sua existência; todo conjunto pode ser bem ordenado se e somente se o axioma da escolha for válido.

Crítica e aceitação

Uma prova que requer o axioma da escolha pode estabelecer a existência de um objeto sem definir explicitamente 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 de teoria dos conjuntos com o axioma da escolha em que nenhuma boa ordenação dos reais é definível. Da mesma forma, embora um subconjunto dos números reais que não é mensurável por Lebesgue possa ser provado usando o axioma da escolha, é consistente que tal conjunto não seja definível.

O axioma da escolha prova a existência desses intangíveis (objetos que existem provados, mas que não podem ser explicitamente construídos), que podem entrar em conflito com alguns princípios filosóficos. Como não há uma boa ordenação canônica de todos os conjuntos, uma construção que depende de uma boa ordenação pode não produzir um resultado canônico, mesmo se um resultado canônico for desejado (como costuma acontecer na teoria das categorias). Isso tem sido usado como um argumento contra o uso do axioma da escolha.

Outro argumento contra o axioma da escolha é que ele implica a existência de objetos que podem parecer contra-intuitivos. Um exemplo é o paradoxo de Banach-Tarski, que diz que é possível decompor a bola unitária sólida tridimensional em um número finito de peças e, usando apenas rotações e translações, remontar as peças em duas bolas sólidas, cada uma com o mesmo volume da original. . As peças dessa decomposição, construídas pelo axioma da escolha, são conjuntos não mensuráveis.

Apesar desses fatos aparentemente paradoxais, a maioria dos matemáticos aceita o axioma da escolha como um princípio válido para provar novos resultados em matemática. O debate é interessante o suficiente, no entanto, que é considerado digno de nota quando um teorema em ZFC (ZF mais AC) é logicamente equivalente (com apenas os axiomas ZF) ao axioma de escolha, e os matemáticos procuram resultados que exigem o axioma de escolha como falsa, embora esse tipo de dedução seja menos comum do que o tipo que exige que o axioma da escolha seja verdadeiro.

É possível provar muitos teoremas usando nem o axioma da escolha nem sua negação; tais declarações serão verdadeiras em qualquer modelo de ZF, independentemente da verdade ou falsidade do axioma da escolha naquele modelo específico. A restrição a ZF torna qualquer afirmação que se baseie no axioma da escolha ou em sua negação indemonstrável. Por exemplo, o paradoxo de Banach-Tarski não pode ser provado nem refutado apenas a partir de ZF: é impossível construir a decomposição necessária da bola unitária em ZF, mas também impossível provar que tal decomposição não existe. Da mesma forma, todas as declarações listadas abaixo que exigem escolha ou alguma versão mais fraca delas para sua prova não são demonstráveis em ZF, mas como cada uma é demonstrável em ZF mais o axioma da escolha, existem modelos de ZF nos quais cada afirmação é verdadeira. Afirmações como o paradoxo de Banach-Tarski podem ser reformuladas como declarações condicionais, por exemplo, "Se AC vale, então a decomposição no paradoxo de Banach-Tarski existe." Tais declarações condicionais são demonstráveis em ZF quando as declarações originais são demonstráveis a partir de ZF e do axioma da escolha.

Na matemática construtiva

Como discutido acima, no ZFC, o axioma da escolha é capaz de fornecer "provas não construtivas" em que a existência de um objeto é provada, embora nenhum exemplo explícito seja construído. O ZFC, no entanto, ainda é formalizado na lógica clássica. O axioma da escolha também foi exaustivamente estudado no contexto da matemática construtiva, onde a lógica não clássica é empregada. O status do axioma da escolha varia entre diferentes variedades de matemática construtiva.

Na teoria dos tipos de Martin-Löf e na aritmética de Heyting de ordem superior, a declaração apropriada do axioma da escolha é (dependendo da abordagem) incluída como um axioma ou demonstrável como um teorema. Errett Bishop argumentou que o axioma da escolha era construtivamente aceitável, dizendo

Uma função de escolha existe em matemática construtiva, porque uma escolha é implícita pelo próprio significado da existência.

Na teoria construtiva dos conjuntos, no entanto, o teorema de Diaconescu mostra que o axioma da escolha implica a lei do meio excluído (ao contrário da teoria do tipo Martin-Löf, onde não). Assim, o axioma da escolha geralmente não está disponível na teoria dos conjuntos construtivos. A causa dessa diferença é que o axioma da escolha na teoria dos tipos não possui as propriedades de extensionalidade que o axioma da escolha na teoria construtiva dos conjuntos possui.

Alguns resultados na teoria construtiva dos conjuntos usam o axioma da escolha contável ou o axioma da escolha dependente, que não implicam na lei do meio excluído na teoria construtiva dos conjuntos. Embora o axioma da escolha contável em particular seja comumente usado na matemática construtiva, seu uso também tem sido questionado.

Independência

Em 1938, Kurt Gödel mostrou que a negação do axioma da escolha não é um teorema de ZF construindo um modelo interno (o universo construtível) que satisfaz ZFC e, assim, mostrando que ZFC é consistente se o próprio ZF for consistente. Em 1963, Paul Cohen empregou a técnica de forçamento, desenvolvida para esse fim, para mostrar que, supondo que ZF seja consistente, o próprio axioma da escolha não é um teorema de ZF. Ele fez isso construindo um modelo muito mais complexo que satisfaz ZF¬C (ZF com a negação de AC adicionada como axioma) e assim mostrando que ZF¬C é consistente.

Juntos, esses resultados estabelecem que o axioma da escolha é logicamente independente de ZF. A suposição de que ZF é consistente é inofensiva porque adicionar outro axioma a um sistema já inconsistente não pode piorar a situação. Por causa da independência, a decisão de usar o axioma da escolha (ou sua negação) em uma prova não pode ser feita apelando para outros axiomas da teoria dos conjuntos. A decisão deve ser tomada por outros motivos.

Um argumento dado a favor do uso do axioma da escolha é que é conveniente usá-lo porque permite provar algumas proposições simplificadoras que de outra forma não poderiam ser provadas. Muitos teoremas que podem ser provados usando escolha são de um caráter geral elegante: as cardinalidades de quaisquer dois conjuntos são comparáveis, todo anel não trivial com unidade tem um ideal maximal, todo espaço vetorial tem uma base, todo grafo conectado tem uma árvore geradora e todo produto de espaços compactos é compacto, entre muitos outros. Sem o axioma da escolha, esses teoremas podem não valer para objetos matemáticos de grande cardinalidade.

A prova do resultado da independência também mostra que uma ampla classe de declarações matemáticas, incluindo todas as declarações que podem ser formuladas na linguagem da aritmética de Peano, são demonstráveis em ZF se e somente se forem demonstráveis em ZFC. As declarações nesta classe incluem a declaração de que P = NP, a hipótese de Riemann e muitos outros problemas matemáticos não resolvidos. Quando se tenta resolver problemas desta classe, não faz diferença se ZF ou ZFC é empregado se a única questão é a existência de uma prova. É possível, no entanto, que haja uma prova mais curta de um teorema de ZFC do que de ZF.

O axioma da escolha não é a única afirmação significativa independente de ZF. Por exemplo, a hipótese do contínuo generalizado (GCH) não é apenas independente de ZF, mas também independente de ZFC. No entanto, ZF mais GCH implica AC, tornando GCH uma reivindicação estritamente mais forte do que AC, embora ambos sejam independentes de ZF.

Axiomas mais fortes

O axioma da construtibilidade e a hipótese do contínuo generalizado implicam o axioma da escolha e, portanto, são estritamente mais fortes do que ele. Nas teorias de classes, como a teoria dos conjuntos de Von Neumann-Bernays-Gödel e a teoria dos conjuntos de Morse-Kelley, existe um axioma chamado axioma da escolha global que é mais forte do que o axioma da escolha para conjuntos porque também se aplica a classes próprias. O axioma da escolha global decorre do axioma da limitação de tamanho. O axioma de Tarski, que é usado na teoria dos conjuntos de Tarski-Grothendieck e afirma (no vernáculo) que todo conjunto pertence a algum universo de Grothendieck, é mais forte que o axioma da escolha.

Equivalentes

Existem afirmações importantes que, assumindo os axiomas de ZF, mas nem AC nem ¬AC, são equivalentes ao axioma da escolha. Os mais importantes 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 do teorema da boa ordenação.

• Teoria dos conjuntos
  • O teorema de Tarski sobre a escolha: Para cada conjunto infinito A, há um mapa bijetivo entre os conjuntos A e A×A.
  • Tricotomia: Se dois conjuntos são dados, então ou eles têm a mesma cardinalidade, ou um tem uma cardinalidade menor do que o outro.
  • Dado dois conjuntos não vazios, um tem uma surjeção para o outro.
  • Cada função surjetiva tem um inverso direito.
  • O produto cartesiano de qualquer família de conjuntos vazios não é nada. Em outras palavras, cada família de conjuntos vazios tem uma função de escolha (Ou seja. uma função que mapeia cada um dos conjuntos vazios a um de seus elementos).
  • Teorema de König: Colloquialmente, a soma de uma sequência de cardeais é estritamente menor do que o produto de uma sequência de cardeais maiores. (A razão para o termo "coloquialmente" é que a soma ou produto de uma "sequência" de cardeais não pode ser definida em si mesmo sem algum aspecto do axioma da escolha.)
  • Teorema de ordenação: Cada conjunto pode ser bem ordenado. Consequentemente, cada cardeal tem um ordinal inicial.
  • Cada elemento de um conjunto parcialmente ordenado S é o elemento mínimo de um subconjunto bem ordenado não tendo nenhum limite superior estrito em S.
  • Lemma de Zorn: Cada conjunto não vazio parcialmente ordenado em que cada cadeia (Ou seja., subconjunto totalmente ordenado) tem um limite superior contém pelo menos um elemento máximo.
  • Princípio máximo de Hausdorff: Cada conjunto parcialmente ordenado tem uma cadeia máxima. Equivalentemente, em qualquer conjunto parcialmente ordenado, cada cadeia pode ser estendida a uma cadeia máxima.
  • Lemma de Tukey: Cada coleção não vazia de caráter finito tem um elemento máximo em relação à inclusão.
  • Princípio anti-chain: Cada conjunto parcialmente ordenado tem um antichain maximal. Equivalentemente, em qualquer conjunto parcialmente ordenado, cada antichain pode ser estendido a um antichain maximal.
• Álgebra abstrata
  • Cada espaço vetorial tem uma base (Ou seja., um subconjunto de exploração linearmente independente). Em outras palavras, os espaços vetoriais são equivalentes a módulos gratuitos.
  • O teorema de Krull: Cada anel unital (excepto o anel trivial) contém um ideal máximo. Equivalentemente, em qualquer anel unital não trivial, cada ideal pode ser estendido a um ideal máximo.
  • Para cada conjunto não vazio S há uma operação binária definida em S que lhe dá uma estrutura de grupo. (Uma operação binária cancellativa é suficiente, veja a estrutura do grupo e o axioma da escolha.)
  • Cada grupo abeliano livre é projetivo.
  • O critério de Baer: Cada grupo abeliano divisível é injetável.
  • Cada conjunto é um objeto projectivo na categoria Conjunto de conjuntos.
• Análise funcional
  • A bola de unidade fechada do dual de um espaço vetorial normal sobre os reais tem um ponto extremo.
• Topologia de ponto
  • O produto cartesiano de qualquer família de espaços topológicos conectados está conectado.
  • Teorema de Tychonoff: O produto cartesiano de qualquer família de espaços topológicos compactos é compacto.
  • Na topologia do produto, o fechamento de um produto de subconjuntos é igual ao produto dos fechamentos.
• Lógica matemática
  • Se S é um conjunto de frases de lógica de primeira ordem e B é um subconjunto consistente de S, então B está incluído em um conjunto que é maximal entre subconjuntos consistentes de S. Caso especial em que S é o conjunto de Todos frases de primeira ordem em uma assinatura dada é mais fraca, equivalente ao teorema ideal primo booleano; veja a seção "Formas mais quentes" abaixo.
• Topologia algébrica
  • Cada grafo conectado tem uma árvore de spanning. Equivalentemente, cada grafo vazio tem uma floresta ascendente.

Teoria da categoria

Existem vários resultados na teoria das categorias que invocam o axioma da escolha para sua prova. Esses resultados podem ser mais fracos, equivalentes ou mais fortes que o axioma da escolha, dependendo da força dos fundamentos técnicos. Por exemplo, se definirmos categorias em termos de conjuntos, ou seja, como conjuntos de objetos e morfismos (geralmente chamados de categoria pequena), ou mesmo categorias localmente pequenas, cujos objetos-hom são conjuntos, então não há categoria de todos os conjuntos , e assim é difícil para uma formulação teórica de categoria aplicar-se a todos os conjuntos. Por outro lado, outras descrições fundamentais da teoria das categorias são consideravelmente mais fortes, e uma declaração de escolha de teoria de categoria idêntica pode ser mais forte do que a formulação padrão, à la class theory, mencionada acima.

Exemplos de declarações teóricas de categoria que requerem escolha incluem:

• Cada categoria pequena tem um esqueleto.
• Se duas categorias pequenas são fracamente equivalentes, então elas são equivalentes.
• Cada funtor contínuo em uma categoria de pequeno-completo que satisfaz a condição de conjunto de solução apropriada tem uma combinação esquerda (o teorema de funtor comum Freyd).

Formas mais fracas

Existem várias declarações mais fracas que não são equivalentes ao axioma da escolha, mas estão intimamente relacionadas. Um exemplo é o axioma da escolha dependente (DC). Um exemplo ainda mais fraco é o axioma da escolha contável (AC_ω ou CC), que afirma que existe uma função de escolha para qualquer conjunto contável de conjuntos não vazios. Esses axiomas são suficientes para muitas provas na análise matemática elementar e são consistentes com alguns princípios, como a mensurabilidade de Lebesgue de todos os conjuntos de reais, que podem ser refutados a partir do axioma completo da escolha.

Dado um parâmetro ordinal α ≥ ω+2 — para cada conjunto S com rank menor que α, S é bem ordenável. Dado um parâmetro ordinal α ≥ 1 — para cada conjunto S com número de Hartogs menor que ω_α, S é bem ordenável. À medida que o parâmetro ordinal é aumentado, eles se aproximam cada vez mais do axioma completo da escolha.

Outros axiomas de escolha mais fracos do que o axioma de escolha incluem o teorema do ideal primo booleano e o axioma da uniformização. O primeiro é equivalente em ZF ao lema do ultrafiltro de 1930 de Tarski: todo filtro é um subconjunto de algum ultrafiltro.

Resultados que requerem AC (ou formas mais fracas), mas mais fracas do que isso

Um dos aspectos mais interessantes do axioma da escolha é o grande número de lugares em matemática que ele aparece. Aqui estão algumas declarações que requerem o axioma da escolha no sentido de que não são demonstráveis de ZF, mas são demonstráveis de ZFC (ZF mais AC). Equivalentemente, essas afirmações são verdadeiras em todos os modelos de ZFC, mas falsas em alguns modelos de ZF.

• Teoria dos conjuntos
  • O lemma ultrafiltro (com ZF) pode ser usado para provar o Axioma de escolha para conjuntos finitos: Conduzido Eu...≠ ≠ ∅ ∅ Não. I\neq \varnothing } e uma coleção (XEu...)Eu...∈ ∈ Eu...{\displaystyle \left(X_{i}\right)_{i\in I. de não vazio finito conjuntos, seu produto ? ? Eu...∈ ∈ Eu...XEu...{\displaystyle \prod _{i\in I}X_{i}} não está vazio.
  • A união de qualquer família contável de conjuntos contáveis é contável (isto requer escolha contável, mas não o axioma completo da escolha).
  • Se o conjunto A é infinito, então existe uma injeção dos números naturais N para A (ver Dedekind infinito).
  • Oito definições de um conjunto finito são equivalentes.
  • Cada jogo infinito GSNão. G_{S}} em que SNão. S. é determinado um subconjunto Borel do espaço Baire.
• Teoria da medição
  • O teorema de Vitali sobre a existência de conjuntos não mensuráveis que afirma que há um subconjunto dos números reais que não é mensurável de Lebesgue.
  • O paradoxo de Hausdorff.
  • O paradoxo Banach-Tarski.
• Algebra
  • Cada campo tem um fechamento algébrico.
  • Cada extensão de campo tem uma base de transcendência.
  • Cada campo vetorial infinita-dimensional contém um subconjunto linearmente independente infinito (isto requer escolha dependente, mas não o axioma completo da escolha).
  • O teorema de representação de Stone para álgebras booleanas precisa do teorema ideal primo booleano.
  • O teorema de Nielsen-Schreier, que cada subgrupo de um grupo livre é livre.
  • Os grupos aditivos R e C são isomorfos.
• Análise funcional
  • O teorema de Hahn-Banach em análise funcional, permitindo a extensão de funcionais lineares
  • O teorema que cada espaço de Hilbert tem uma base ortonormal.
  • O teorema de Banach-Alaoglu sobre a compactação de conjuntos de funcionais.
  • O teorema da categoria Baire sobre espaços métricos completos, e suas consequências, como o teorema de mapeamento aberto e o teorema do gráfico fechado.
  • Em cada espaço vetorial topológico de dimensão infinita há um mapa linear descontinuo.
• Topologia geral
  • Um espaço uniforme é compacto se e somente se estiver completo e totalmente limitado.
  • Cada espaço Tychonoff tem uma compactação Stone-Čech.
• Lógica matemática
  • O teorema de integridade de Gödel para a lógica de primeira ordem: cada conjunto consistente de sentenças de primeira ordem tem uma conclusão. Ou seja, cada conjunto consistente de sentenças de primeira ordem pode ser estendido para um conjunto consistente máxima.
  • O teorema da compactação: Se Σ Σ Não. Sim. é um conjunto de sentenças de primeira ordem (ou alternativamente, ordem zero), de tal forma que cada subconjunto finito de Σ Σ Não. Sim. tem um modelo, então Σ Σ Não. Sim. tem um modelo.

Possivelmente implicações equivalentes de AC

Existem várias declarações teóricas de conjuntos historicamente importantes implícitas por AC cuja equivalência a AC é aberta. O princípio da partição, que foi formulado antes da própria AC, foi citado por Zermelo como justificativa para acreditar na AC. Em 1906, Russell declarou que PP é equivalente, mas se o princípio da partição implica AC ainda é o problema aberto mais antigo na teoria dos conjuntos, e as equivalências das outras declarações são problemas abertos igualmente difíceis. Em todos os modelos conhecidos de ZF em que a escolha falha, essas instruções também falham, mas não se sabe se elas podem ser mantidas sem escolha.

• Teoria dos conjuntos
  • Princípio de partição: se houver uma surjeção de A para B, há uma injeção de B para A. Equivalentemente, cada partição P de um conjunto S é inferior ou igual a S em tamanho.
  • Converse Schröder–Bernstein teorema: se dois conjuntos têm surjeções um ao outro, eles são equinumerosos.
  • Princípio de partição fraco: se houver uma injeção e uma surjeção de A para B, então A e B são equinumerosos. Equivalentemente, uma partição de um conjunto S não pode ser estritamente maior do que S. Se o WPP deter, isso já implica a existência de um conjunto não seguro. Cada uma das três declarações anteriores é implícita pelo anterior, mas é desconhecido se alguma dessas implicações pode ser revertida.
  • Não há uma sequência decrescente infinita de cardeais. A equivalência foi conjecturada por Schoenflies em 1905.
• Álgebra abstrata
  • Teorema de incorporação de Hahn: Cada grupo abeliano ordenado G order-embeds como um subgrupo do grupo aditivo RΩ Ω {\displaystyle \mathbb {R} ^{\Omega }} dotado de uma ordem lexicográfica, onde Ω é o conjunto de classes de equivalência arqueica de G. Esta equivalência foi conjecturada por Hahn em 1907.

Formas mais fortes da negação de AC

Se abreviarmos por BP a afirmação de que todo conjunto de números reais tem a propriedade de Baire, então BP é mais forte que ¬AC, que afirma a inexistência de qualquer função de escolha em talvez apenas um único conjunto de conjuntos não vazios. Negações fortalecidas podem ser compatíveis com formas enfraquecidas de AC. Por exemplo, ZF + DC + BP é consistente, se ZF for.

Também é consistente com ZF + DC que todo conjunto de reais é mensurável de Lebesgue; no entanto, esse resultado de consistência, devido a Robert M. Solovay, não pode ser provado no próprio ZFC, mas requer uma suposição de cardeal grande e moderado (a existência de um cardeal inacessível). O axioma muito mais forte da determinação, ou AD, implica que todo conjunto de reais é mensurável por Lebesgue, tem a propriedade de Baire e tem a propriedade de conjunto perfeito (todos esses três resultados são refutados pelo próprio AC). ZF + DC + AD é consistente desde que um axioma cardinal grande suficientemente forte seja consistente (a existência de infinitos cardinais de Woodin).

O sistema de teoria axiomática dos conjuntos de Quine, New Foundations (NF), leva o nome do título ("New Foundations for Mathematical Logic") do artigo de 1937 que o introduziu. No sistema axiomático NF, o axioma da escolha pode ser refutado.

Declarações consistentes com a negação de AC

Existem modelos da teoria dos conjuntos de Zermelo-Fraenkel em que o axioma da escolha é falso. Abreviaremos "teoria dos conjuntos de Zermelo-Fraenkel mais a negação do axioma da escolha" por ZF¬C. Para certos modelos de ZF¬C, é possível provar a negação de alguns fatos padrão. Qualquer modelo de ZF¬C também é um modelo de ZF, portanto, para cada uma das afirmações a seguir, existe um modelo de ZF no qual essa afirmação é verdadeira.

• Há um conjunto que pode ser particionado em classes de equivalência estritamente mais do que o conjunto original tem elementos, e uma função cujo domínio é estritamente menor do que o seu alcance. Na verdade, este é o caso em tudo conhecido modelos.
• Há uma função f dos números reais para os números reais tal que f não é contínuo em um, mas f é sequencialmente contínuo em um, ou seja, para qualquer sequência {x_nConvergir para um, lim_n f(x_n)=f(a).
• Há um conjunto infinito de números reais sem um subconjunto contavelmente infinito.
• Os números reais são uma união contável de conjuntos contáveis. Isso não implica que os números reais são contáveis: Como apontado acima, para mostrar que uma união contável de conjuntos contáveis é em si contável requer o Axioma de escolha contável.
• Há um campo sem fechamento algébrico.
• Em todos os modelos de ZF¬ C há um espaço vetorial sem base.
• Há um espaço vetorial com duas bases de diferentes cardinalidades.
• Há uma álgebra booleana completa livre em muitos geradores.
• Há um conjunto que não pode ser ordenada linearmente.
• Existe um modelo de ZF¬C em que cada conjunto em Rⁿ é mensurável. Assim, é possível excluir resultados contra-intuitivos como o paradoxo Banach-Tarski que são prováveis no ZFC. Além disso, isso é possível ao mesmo tempo que assume o Axioma da escolha dependente, que é mais fraco do que AC, mas suficiente para desenvolver a maioria da análise real.
• Em todos os modelos de ZF¬C, a hipótese de continuidade generalizada não possui.

Para provas, consulte Jech (2008).

Além disso, ao impor condições de definibilidade em conjuntos (no sentido da teoria descritiva dos conjuntos), pode-se frequentemente provar versões restritas do axioma da escolha a partir de axiomas incompatíveis com a escolha geral. Isso aparece, por exemplo, no lema de codificação de Moschovakis.

Axioma da escolha na teoria dos tipos

Na teoria dos tipos, um tipo diferente de declaração é conhecido como axioma da escolha. Esta forma começa com dois tipos, σ e τ, e uma relação R entre objetos do tipo σ e objetos do tipo τ. O axioma da escolha afirma que se para cada x do tipo σ existe um y do tipo τ tal que R(x,y), então existe uma função f de objetos do tipo σ para objetos do tipo τ tal que R(x,f(x)) vale para todo x do tipo σ:

(Gerenciamento de contas Gerenciamento de contas xσ σ )(Detalhe Detalhe Sim.? ? )R(x,Sim.)→ → (Detalhe Detalhe fσ σ → → ? ? )(Gerenciamento de contas Gerenciamento de contas xσ σ )R(x,f(x)).(\forall x^{\sigma })(\exists y^{\tau })R(x,y)\to (\exists f^{\sigma \to \tau })(\forall x^{\sigma })R(x,f(x)). ?

Ao contrário da teoria dos conjuntos, o axioma da escolha na teoria dos tipos é normalmente declarado como um esquema de axioma, no qual R varia em todas as fórmulas ou em todas as fórmulas de uma forma lógica particular.

Cotações

O axioma da escolha é obviamente verdade, o princípio bem ordenado obviamente falso, e quem pode dizer sobre o lema de Zorn?

—Jerry Bona

Isso é uma piada: embora os três sejam todos matematicamente equivalentes, muitos matemáticos acham que o axioma da escolha é intuitivo, o princípio da boa ordenação é contra-intuitivo e o lema de Zorn é muito complexo para qualquer intuição .

O Axioma da Escolha é necessário selecionar um conjunto de um número infinito de pares de meias, mas não um número infinito de pares de sapatos.

—Bertrand Russell

A observação aqui é que pode-se definir uma função para selecionar um número infinito de pares de sapatos, por exemplo, escolhendo o sapato esquerdo de cada par. Sem o axioma da escolha, não se pode afirmar que tal função existe para pares de meias, porque as meias esquerda e direita são (presumivelmente) indistinguíveis.

Tarski tentou publicar seu teorema [a equivalência entre AC e "todo conjunto infinito A tem a mesma cardinalidade como A × A", veja acima] em Comptes Rendus, mas Fréchet e Lebesgue se recusaram a apresentá-lo. Fréchet escreveu que uma implicação entre duas proposições bem conhecidas não é um novo resultado, e Lebesgue escreveu que uma implicação entre duas proposições falsas não é de nenhum interesse.

O matemático polonês-americano Jan Mycielski relata esta anedota em um artigo de 2006 no Notices of the AMS.

O axioma recebe seu nome não porque os matemáticos preferem a outros axiomas.

—A. K. Dewdney

Esta citação vem do famoso Dia da Mentira. Day na coluna recriações de computador da Scientific American, abril de 1989.