Axioma da escolha - Axiom of choice

Ilustração do axioma de escolha, com cada S _i e x _i representados como uma jarra e uma bola de gude colorida, respectivamente

(S _i ) é uma família infinita de conjuntos indexados sobre os números reais R ; ou seja, há um conjunto S _i para cada número real i , com uma pequena amostra mostrada acima. Cada conjunto contém pelo menos um, e possivelmente infinitos, elementos. O axioma da escolha permite selecionar arbitrariamente um único elemento de cada conjunto, formando uma família correspondente de elementos ( x _i ) também indexados sobre os números reais, com x _i extraído de S _i . Em geral, os conjuntos podem ser indexada sobre qualquer conjunto I , (chamado conjunto de índices que elementos são usados como índices para elementos de um conjunto) não apenas R .

Em matemática , o axioma da escolha , ou AC , é 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 . Colocado informalmente, o axioma da escolha diz que dada qualquer coleção de caixas, cada uma contendo pelo menos um objeto, é possível fazer uma seleção de exatamente um objeto de cada caixa, mesmo que a coleção seja infinita . Formalmente, ele afirma que para cada família indexada de conjuntos não vazios existe uma família indexada de elementos para cada . O axioma da escolha foi formulado em 1904 por Ernst Zermelo a fim de formalizar sua prova do teorema da boa ordenação . ${\ displaystyle (S_ {i}) _ {i \ in I}}$${\ displaystyle (x_ {i}) _ {i \ in I}}$${\ displaystyle x_ {i} \ in S_ {i}}$${\ displaystyle i \ in I}$

Em muitos casos, essa seleção pode ser feita sem invocar o axioma da escolha; este é o caso em particular se o número de conjuntos for finito, ou se uma regra de seleção 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 a partir dos números naturais. De tais conjuntos, pode-se sempre selecionar o menor número, por exemplo, 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 infinitamente muitos conjuntos tenham sido 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 é conhecida para a coleção de todos os subconjuntos não vazios dos números reais (se houver reais não construtí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 seleção apropriada; isso torna possível definir diretamente uma função de escolha. Para uma coleção infinita de pares de meias (supostamente sem características distintivas), não há maneira óbvia de fazer uma função que selecione uma meia de cada par, sem invocar o axioma da 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 dos conjuntos axiomática, a teoria dos conjuntos de Zermelo-Fraenkel com o axioma da escolha ( ZFC ). Uma motivação para esse uso é que uma série de resultados matemáticos geralmente aceitos, como o teorema de Tychonoff , requerem o axioma de escolha para suas demonstrações. 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 em que o axioma da escolha é adotado.

Demonstração

Uma função de escolha (também chamado selector ou selecção) é uma função de f , definido de uma colecção de X dos conjuntos não vazios, tais que, para cada conjunto Um em X , f ( A ) é um elemento de um . Com este conceito, o axioma pode ser afirmado:

Formalmente, isso pode ser expresso da seguinte forma:

${\ displaystyle \ forall X \ left [\ varnothing \ notin X \ implica \ existe f \ dois pontos 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 não vazios que não tem função de escolha. ( então, onde está a negação.) ${\ displaystyle p \ rightarrow q \ Longleftrightarrow \ lnot [p \ land (\ lnot q)]}$${\ displaystyle \ lnot (p \ rightarrow q) \ Longleftrightarrow p \ land (\ lnot q)}$${\ displaystyle \ lnot}$

Cada função de escolha em um conjunto 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 um fator; entretanto, pode-se focar nos 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 não vazios, seu produto cartesiano é um conjunto não 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 - Teoria dos conjuntos Zermelo – Fraenkel omitindo o Axioma da Escolha.
• ZFC - teoria dos conjuntos de Zermelo-Fraenkel, estendida para incluir o Axioma da Escolha.

Variantes

Existem muitas outras afirmações equivalentes do axioma da escolha. Eles 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 implicados por ele.

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 de X de pares disjuntos conjuntos não vazios, existe, pelo menos, um conjunto C que contém exactamente 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 da partição.

Outro axioma equivalente considera apenas coleções X que são essencialmente conjuntos de poderes 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 essa formulação freqüentemente 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 outro lugar neste artigo, o domínio de uma função de escolha em uma coleção de conjuntos é essa coleção, e assim só faz sentido para conjuntos de conjuntos. Com esta noção alternativa de função de escolha, o axioma de escolha pode ser afirmado 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 não-vazia subconjunto B de A , f ( B ) situa-se em B .

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

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

Restrição a conjuntos finitos

O enunciado 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 por indução matemática . No caso ainda mais simples de uma coleção de um conjunto, uma função de escolha corresponde apenas a um elemento, portanto, esta instância do axioma de escolha diz que todo conjunto não vazio tem um elemento; isso é trivial. O axioma da escolha pode ser visto como a afirmação da generalização dessa 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 freqüentemente usado implicitamente, embora ainda não tivesse sido formalmente declarado. Por exemplo, após ter verificado que o conjunto X contém apenas os conjuntos não vazios, um matemático poderia ter dito "deixar F (s) é um dos membros do s para todos 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 .

Nem toda situação requer o axioma da escolha. Para conjuntos finitos X , o axioma de escolha segue dos outros axiomas da teoria dos conjuntos. Nesse caso, é equivalente a dizer que se tivermos várias (um número finito de) caixas, cada uma contendo pelo menos um item, podemos escolher exatamente um item de cada caixa. É claro que podemos fazer isso: começamos na primeira caixa, escolhemos um item; vá para a segunda caixa, escolha um item; e assim por diante. O número de caixas é finito, então, eventualmente, nosso procedimento de escolha chega ao fim. O resultado é uma função de escolha explícita: uma função que leva a primeira caixa ao primeiro elemento que escolhemos, a segunda caixa ao segundo elemento que escolhemos e assim por diante. (Uma prova formal para todos os conjuntos finitos usaria o princípio da indução matemática para provar "para cada número natural k , cada família de k conjuntos não vazios tem uma função de escolha.") Este método não pode, no entanto, ser usado para mostrar que todos os contáveis família de conjuntos não vazios tem uma função de escolha, como afirma o axioma da escolha contável . Se o método for aplicado a uma sequência infinita ( X _i  : i ∈ω) de conjuntos não vazios, uma função é obtida em cada estágio finito, mas não há estágio em que uma função de escolha para toda a família seja construída, e não " A limitação da "função de escolha pode ser construída, em geral, em ZF sem o axioma de escolha.

Exemplos

A natureza dos conjuntos não vazios individuais 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 subconjunto tem um menor elemento, portanto, para especificar nossa função de escolha, podemos simplesmente dizer que ele mapeia cada conjunto para o menor elemento desse conjunto. Isso nos dá uma escolha definitiva de um elemento de cada conjunto e torna desnecessário aplicar o axioma da escolha.

A dificuldade surge quando não há escolha natural de elementos de cada conjunto. Se não podemos fazer escolhas explícitas, como sabemos que nosso conjunto existe? Por exemplo, suponha que X seja o conjunto de todos os subconjuntos não vazios dos números reais . Primeiro, podemos tentar proceder como se X fosse finito. Se tentamos escolher um elemento de cada conjunto, então, porque X é infinita, nosso procedimento de escolha nunca vai chegar a um fim, e, consequentemente, nunca seremos capazes de produzir uma função de escolha para todos os X . Em seguida, podemos tentar especificar o mínimo de elemento de cada conjunto. Mas alguns subconjuntos dos números reais não têm menos elementos. 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, essa 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 que consiste em todas as rotações racionais. A saber, essas são rotações por ângulos que são múltiplos racionais de  π . Aqui, G é contável enquanto S é incontável. Daí S divide em uncountably muitas órbitas sob  G . Usando o axioma da escolha, poderíamos escolher um único ponto de cada órbita, obtendo-se um subconjunto incontável X de S com a propriedade de que todos os seus traduz por L são disjuntos de  X . O conjunto daqueles traduz as partições do círculo em uma coleção contável de conjuntos disjuntos, que são todos congruentes em pares. Uma vez que X não é mensurável para qualquer medida finita aditiva contável e invariante à rotação em S , encontrar um algoritmo para selecionar um ponto em cada órbita requer o axioma de escolha. Veja conjunto não mensurável para mais detalhes.

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

Crítica e aceitação

Uma prova que exige 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 há uma boa ordenação dos números reais, existem modelos da teoria dos conjuntos com o axioma da escolha em que nenhuma ordenação dos reais é definível. Da mesma forma, embora um subconjunto dos números reais que não seja mensurável de Lebesgue possa ser provado que existe usando o axioma da escolha, é consistente que nenhum tal conjunto seja definível.

O axioma da escolha prova a existência desses intangíveis (objetos cuja existência foi comprovada, mas que não podem ser explicitamente construídos), que podem entrar em conflito com alguns princípios filosóficos. Como não há 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 ser o caso 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 de unidade sólida tridimensional em muitas peças finitas e, usando apenas rotações e translações, remontar as peças em duas bolas sólidas, cada uma com o mesmo volume do original . As peças nesta decomposição, construídas usando o 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, para ser considerado digno de nota quando um teorema em ZFC (ZF mais AC) é logicamente equivalente (apenas com os axiomas de ZF) ao axioma de escolha, e os matemáticos procuram resultados que requerem o axioma de a escolha seja 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 afirmações serão verdadeiras em qualquer modelo de ZF, independentemente da verdade ou falsidade do axioma de escolha nesse modelo particular. A restrição a ZF torna improvável qualquer afirmação que se baseie no axioma da escolha ou em sua negação. Por exemplo, o paradoxo de Banach – Tarski não pode ser provado nem desmentido apenas por ZF: é impossível construir a decomposição necessária da bola unitária em ZF, mas também impossível provar que não existe tal decomposição. Da mesma forma, todas as afirmações listadas abaixo que requerem escolha ou alguma versão mais fraca delas para sua prova são improváveis ​​em ZF, mas uma vez que cada uma é demonstrável em ZF mais o axioma da escolha, existem modelos de ZF em que cada afirmação é verdadeira. Declarações como o paradoxo de Banach-Tarski podem ser reformuladas como declarações condicionais, por exemplo, "Se a AC se mantém, então a decomposição no paradoxo de Banach-Tarski existe." Essas declarações condicionais são prováveis ​​em ZF quando as declarações originais são prováveis ​​de ZF e do axioma de escolha.

Em matemática construtiva

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

Na teoria de tipo de Martin-Löf e na aritmética de Heyting de ordem superior , a declaração apropriada do axioma de 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 na matemática construtiva, porque uma escolha está implícita no próprio significado da existência.

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

Alguns resultados na teoria dos conjuntos construtivos usam o axioma da escolha contável ou o axioma da escolha dependente , o que não implica a lei do meio excluído na teoria dos conjuntos construtivos. 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 de escolha não é um teorema de ZF, construindo um modelo interno (o universo construtível ) que satisfaça ZFC e, assim, mostrando que ZFC é consistente se o próprio ZF for consistente. Em 1963, Paul Cohen empregou a técnica do forçamento , desenvolvida para esse fim, para mostrar que, supondo que ZF seja consistente, o axioma da escolha em si 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 de 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-se 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 demonstrados usando a escolha são de um caráter geral elegante: todo ideal em um anel está contido em um ideal máximo , todo espaço vetorial tem uma base e todo produto de espaços compactos é compacto. 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 afirmações matemáticas, incluindo todas as afirmações que podem ser formuladas na linguagem da aritmética de Peano , são prováveis ​​em ZF se e somente se são prováveis ​​em ZFC. As afirmações nesta aula incluem a afirmação de que P = NP , a hipótese de Riemann e muitos outros problemas matemáticos não resolvidos. Quando alguém tenta resolver problemas nesta classe, não faz diferença se ZF ou ZFC é empregado se a única questão for a existência de uma prova. É possível, entretanto, 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 afirmaçã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, cada um, o axioma da escolha e, portanto, são estritamente mais fortes do que ele. Em teorias de classe 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 adequadas. O axioma da escolha global segue 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 cada conjunto pertence a algum universo de Grothendieck , é mais forte do que o axioma de escolha.

Equivalentes

Existem declarações importantes que, assumindo os axiomas de ZF, mas nem AC nem ¬AC, são equivalentes ao axioma de escolha. Os mais importantes entre eles são o lema de Zorn e o teorema da boa ordenação . Na verdade, Zermelo inicialmente introduziu o axioma da escolha a fim de formalizar sua prova do teorema da boa ordenação.

• Teoria de conjuntos
  • Teorema da boa ordenação : cada conjunto pode ser bem ordenado. Conseqüentemente, todo cardinal possui um ordinal inicial .
  • Teorema de Tarski sobre a escolha : Para cada conjunto infinito A , há um mapa bijective entre os conjuntos A e A × A .
  • Tricotomia : se dois conjuntos são fornecidos, eles têm a mesma cardinalidade ou um tem uma cardinalidade menor que o outro.
  • Dados dois conjuntos não vazios, um se entrega ao outro.
  • O produto cartesiano de qualquer família de conjuntos não vazios é não vazio.
  • Teorema de König : coloquialmente, 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 sem algum aspecto do axioma de escolha.)
  • Toda função sobrejetiva tem um inverso correto .
• Teoria da ordem
  • Lema de Zorn : Cada conjunto parcialmente ordenado não vazio em que cada cadeia ( isto é , subconjunto totalmente ordenado) tem um limite superior contém pelo menos um elemento máximo.
  • Princípio máximo de Hausdorff : Em qualquer conjunto parcialmente ordenado, todo subconjunto totalmente ordenado está contido em um subconjunto máximo totalmente ordenado. O princípio restrito "Cada conjunto parcialmente ordenado tem um subconjunto máximo totalmente ordenado" também é equivalente a AC sobre ZF.
  • Lema de Tukey : Cada coleção não vazia de caracteres finitos possui um elemento máximo com relação à inclusão.
  • Princípio anticadeia : todo conjunto parcialmente ordenado possui uma anticadeia máxima .
• Álgebra abstrata
  • Todo espaço vetorial tem uma base .
  • Teorema de Krull : Todo anel unital, exceto o anel trivial, contém um ideal máximo .
  • Para cada conjunto não vazio S, há uma operação binária definida em S que fornece uma estrutura de grupo . (Um cancellative binário operação é suficiente, ver a estrutura e o grupo axioma de escolha ).
  • Cada conjunto é um objeto projetivo na categoria Conjunto de conjuntos.
• Análise funcional
  • A bola unitária fechada do dual de um espaço vetorial normatizado sobre os reais tem um ponto extremo .
• Topologia de conjunto de pontos
  • Tychonoff é teorema : Cada produto de compactos espaços topológicos é 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 é incluído em um conjunto que é máxima entre os subconjuntos consistentes de S . O caso especial em que S é o conjunto de todas as sentenças de primeira ordem em uma determinada assinatura é mais fraco, equivalente ao teorema ideal primário booleano ; consulte a seção "Formas mais fracas" abaixo.
• Teoria dos grafos
  • Cada gráfico conectado possui uma árvore de abrangência .

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 do que o axioma de escolha, dependendo da força dos fundamentos técnicos. Por exemplo, se alguém define categorias em termos de conjuntos, isto é, como conjuntos de objetos e morfismos (geralmente chamados de uma pequena categoria ), ou mesmo localmente pequenas categorias, cujos hom-objetos são conjuntos, então não há categoria de todos os conjuntos e, portanto, é difícil para uma formulação da teoria das categorias ser aplicada 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 da teoria da categoria idêntica pode ser mais forte do que a formulação padrão, à la teoria das classes, mencionada acima.

Exemplos de afirmações teóricas de categorias que requerem escolha incluem:

• Cada pequena categoria tem um esqueleto .
• Se duas categorias pequenas forem fracamente equivalentes, elas serão equivalentes .
• Cada functor contínuo em uma categoria completa pequena que satisfaça a condição de conjunto de solução apropriada tem um adjunto à esquerda (o teorema do functor adjunto de Freyd).

Formas mais fracas

Existem várias afirmaçõ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 (CD). 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 em 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 são contestáveis ​​do axioma completo de 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 Tarski de 1930 : cada filtro é um subconjunto de algum ultrafiltro .

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

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

• Teoria de conjuntos
  • O lema do ultrafiltro (com ZF) pode ser usado para provar o Axioma de escolha para conjuntos finitos: Dados e uma coleção de conjuntos finitos não vazios , seu produto não é vazio.${\ displaystyle I \ neq \ varnothing}$${\ displaystyle \ left (X_ {i} \ right) _ {i \ in I}}$${\ displaystyle \ prod _ {i \ in I} X_ {i}}$
  • Qualquer união de muitos conjuntos contáveis é em si contável (porque é necessário escolher uma ordem particular para cada um dos muitos conjuntos contáveis).
  • Se o conjunto A é infinito , então existe uma injeção dos números naturais N em A (ver Dedekind infinito ).
  • Oito definições de um conjunto finito são equivalentes.
  • Todo jogo infinito no qual é um subconjunto do Borel do espaço de Baire é determinado .${\ displaystyle G_ {S}}$${\ displaystyle S}$
• Teoria da medida
  • O teorema de Vitali sobre a existência de conjuntos não mensuráveis que afirma que existe um subconjunto dos números reais que não é mensurável de Lebesgue .
  • O paradoxo de Hausdorff .
  • O paradoxo de Banach – Tarski .
• Álgebra
  • Todo campo tem um fechamento algébrico .
  • Cada extensão de campo tem uma base de transcendência .
  • O teorema de representação de Stone para álgebras booleanas precisa do teorema ideal primo booleano .
  • O teorema de Nielsen-Schreier , de que todo subgrupo de um grupo livre é livre.
  • Os grupos aditivos de R e C são isomórficos.
• Análise funcional
  • O teorema de Hahn-Banach em análise funcional , permitindo a extensão de funcionais lineares
  • O teorema de que todo espaço de Hilbert tem uma base ortonormal.
  • O teorema de Banach-Alaoglu sobre compacidade de conjuntos de funcionais.
  • O teorema da categoria de Baire sobre espaços métricos completos e suas consequências, como o teorema do mapeamento aberto e o teorema do gráfico fechado .
  • Em cada espaço vetorial topológico de dimensão infinita, há um mapa linear descontínuo .
• Topologia geral
  • Um espaço uniforme é compacto se e somente se for completo e totalmente delimitado.
  • Cada espaço Tychonoff tem uma compactificação Stone – Čech .
• Lógica matemática
  • Teorema da completude de Gödel para lógica de primeira ordem: todo conjunto consistente de sentenças de primeira ordem tem uma conclusão. Ou seja, todo conjunto consistente de sentenças de primeira ordem pode ser estendido a um conjunto consistente máximo.

Possivelmente implicações equivalentes de AC

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

• Teoria de conjuntos
  • Princípio de partição: se houver uma surjection de um a B , há uma injecção de B para A . Equivalentemente, cada partição P de um conjunto S é menor ou igual a S em tamanho.
  • Converse o teorema de Schröder-Bernstein : se dois conjuntos têm sobreposições um ao outro, eles são equinumeros.
  • Princípio de partição fraco: Uma partição de um conjunto S não pode ser maior do que o estritamente S . Se o WPP for válido, isso já implica a existência de um conjunto não mensurável. Cada uma das três afirmações anteriores está implícita na anterior, mas não se sabe se alguma dessas implicações pode ser revertida.
  • Não há sequência decrescente infinita de cardeais. A equivalência foi conjecturada por Schoenflies em 1905.
• Álgebra abstrata
  • Hahn incorporação teorema : Cada grupo ordenado abeliano G ORDER-incorporações como um subgrupo do grupo de aditivos dotado com uma ordem léxicografica , onde Ω é o conjunto de classes de equivalência de Arquimedes de L . Essa equivalência foi conjecturada por Hahn em 1907.${\ displaystyle \ mathbb {R} ^ {\ Omega}}$

Formas mais fortes de negação de AC

Se abreviarmos para BP a afirmação de que todo conjunto de números reais tem a propriedade de Baire , então BP é mais forte do que ¬AC, o 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 CA. Por exemplo, ZF + DC + BP é consistente, se ZF for.

Também é consistente com ZF + DC que cada conjunto de reais é Lebesgue mensurável ; no entanto, este resultado de consistência, devido a Robert M. Solovay , não pode ser provado no próprio ZFC, mas requer uma suposição cardinal grande moderada (a existência de um cardeal inacessível ). O axioma de determinação muito mais forte , ou AD, implica que todo conjunto de reais é Lebesgue mensurável, tem a propriedade de Baire e tem a propriedade de conjunto perfeito (todos os três resultados são refutados pelo próprio AC). ZF + DC + AD é consistente desde que um grande axioma cardinal suficientemente forte seja consistente (a existência de infinitos cardeais 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 da NF, o axioma de escolha pode ser refutado.

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

Existem modelos da teoria dos conjuntos de Zermelo-Fraenkel nos quais o axioma da escolha é falso. Devemos abreviar "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 seguintes afirmações, existe um modelo de ZF em que essa afirmação é verdadeira.

• Em algum modelo, há um conjunto que pode ser particionado estritamente em mais classes de equivalência do que o conjunto original possui elementos, e uma função cujo domínio é estritamente menor que seu intervalo. Na verdade, esse é o caso em todos os modelos conhecidos .
• Há uma função f dos números reais para os números reais tal que f não é contínuo em a , mas f é sequencialmente contínuo em a , ou seja, para qualquer sequência { x _n } convergindo para a , lim _n f ( x _n ) = f (a).
• Em algum modelo, há um conjunto infinito de números reais sem um subconjunto infinito contável.
• Em alguns modelos, os números reais são uma união contável de conjuntos contáveis. Isso não implica que os números reais sejam contáveis: conforme apontado acima, mostrar que uma união contável de conjuntos contáveis ​​é ela própria contável requer o Axioma da escolha contável .
• Em algum modelo, existe um campo sem fechamento algébrico.
• Em todos os modelos de ZF¬C existe um espaço vetorial sem base.
• Em alguns modelos, existe um espaço vetorial com duas bases de cardinalidades diferentes.
• Em alguns modelos, existe uma álgebra booleana completa e gratuita em muitos geradores.
• Em alguns modelos, há um conjunto que não pode ser ordenado linearmente .
• Existe um modelo de ZF¬C no qual cada conjunto em R ⁿ é mensurável . Assim, é possível excluir resultados contra-intuitivos, como o paradoxo de Banach-Tarski, que podem ser provados em ZFC. Além disso, isso é possível enquanto se assume o Axioma da escolha dependente , que é mais fraco do que AC, mas suficiente para desenvolver a maior parte da análise real .
• Em todos os modelos de ZF¬C, a hipótese do contínuo generalizado não é válida.

Para provas, veja Jech (2008) .

Além disso, ao impor condições de definibilidade aos conjuntos (no sentido da teoria descritiva dos conjuntos ), pode-se freqüentemente 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 de escolha afirma que se para cada x do tipo σ existe um y do tipo τ tal que R ( x , y ), então há uma função f de objetos do tipo σ para objetos do tipo τ tais que R ( x , f ( x )) vale para todo x do tipo σ:

${\ displaystyle (\ forall x ^ {\ sigma}) (\ existe y ^ {\ tau}) R (x, y) \ to (\ existe 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 é tipicamente 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.

Citações

O axioma da escolha é obviamente verdadeiro, o princípio da boa ordenação obviamente falso, e quem pode saber sobre o lema de Zorn ?

-  Jerry Bona

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

O Axioma da Escolha é necessário para 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 se pode definir uma função para selecionar a partir de um número infinito de pares de sapatos, afirmando, por exemplo, escolher um sapato esquerdo. 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 que 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 [verdadeiras] bem conhecidas não é um resultado novo, e Lebesgue escreveu que uma implicação entre duas proposições falsas não tem interesse.

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

O axioma tem esse nome não porque os matemáticos o prefiram a outros axiomas.

-  AK Dewdney

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

Notas

Referências

• Halmos, Paul R. (1960). Teoria dos conjuntos ingênua . The University Series in Graduate Mathematics. Princeton, NJ: van Nostrand Company. Zbl  0087.04403 .
• Herrlich, Horst (2006). Axioma de escolha . Notas de aula em matemática. 1876. Berlin: Springer-Verlag . ISBN 978-3-540-30989-5.
• Howard, Paul; Rubin, Jean E. (1998). Consequências do axioma da escolha . Pesquisas e monografias matemáticas. 59 . Providence, Rhode Island: American Mathematical Society . ISBN 9780821809778.
• Jech, Thomas (2008) [1973]. O axioma da escolha . Mineola, Nova York: Dover Publications . ISBN 978-0-486-46624-8.
• Jech, Thomas (1977). "Sobre o Axioma da Escolha". Em John Barwise (ed.). Handbook of Mathematical Logic .
• Lévy, Azriel (1958). "A independência de várias definições de finitude" (PDF) . Fundamenta Mathematicae . 46 : 1-13. doi : 10.4064 / fm-46-1-1-13 .
• Per Martin-Löf, "100 anos do axioma da escolha de Zermelo: Qual era o problema com ele?", Em Logicism, Intuitionism, and Formalism: What Has Become of Them? , Sten Lindström, Erik Palmgren, Krister Segerberg e Viggo Stoltenberg-Hansen, editores (2008). ISBN  1-4020-8925-2
• Mendelson, Elliott (1964). Introdução à lógica matemática . Nova York: Van Nostrand Reinhold.
• Moore, Gregory H. (1982). Axioma de escolha de Zermelo, suas origens, desenvolvimento e influência . Springer . ISBN 978-0-387-90670-6., disponível como uma reimpressão da Dover Publications , 2013, ISBN  0-486-48841-1 .
• Moore, Gregory H (2013) [1982]. Axioma de escolha de Zermelo: suas origens, desenvolvimento e influência . Mineola, Nova York: Dover Publications. ISBN 978-0-486-48841-7.
• Herman Rubin , Jean E. Rubin : Equivalents of the axioma of choice. North Holland, 1963. Reeditado por Elsevier , abril de 1970. ISBN  0-7204-2225-6 .
• Herman Rubin, Jean E. Rubin: Equivalents of the Axiom of Choice II. North Holland / Elsevier, julho de 1985, ISBN  0-444-87708-8 .
• Russell, Bertrand (1993) [1919]. Introdução à filosofia matemática . Nova York: Dover Publications. ISBN 978-0-486-27724-0.
• Suppes, Patrick (1972) [1960]. Teoria dos conjuntos axiomáticos . Mineola, Nova York: Dover. ISBN 978-0-486-61630-8.
• George Tourlakis, Lectures in Logic and Set Theory. Vol. II: Set Theory , Cambridge University Press , 2003. ISBN  0-511-06659-7
• Zermelo, Ernst (1904). "Beweis, dass jede Menge wohlgeordnet werden kann" (reimpressão) . Mathematische Annalen . 59 (4): 514–16. doi : 10.1007 / BF01445300 . S2CID  124189935 .
• Ernst Zermelo , "Untersuchungen über die Grundlagen der Mengenlehre I," Mathematische Annalen 65 : (1908) pp. 261-81. Baixar PDF via digizeitschriften.de

Traduzido em: Jean van Heijenoort , 2002. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 . Nova edição. Harvard University Press . ISBN  0-674-32449-8

• 1904. "Prova de que todo jogo pode ser bem ordenado", 139-41.
• 1908. "Investigations in the foundations of set theory I," 199-215.

links externos

• Artigo Axiom of Choice na Springer Encyclopedia of Mathematics .
• Axiom of Choice e seus equivalentes, entrada no ProvenMath. Inclui declaração formal do Axioma da Escolha, Princípio Máximo de Hausdorff, Lema de Zorn e provas formais de sua equivalência nos mínimos detalhes.
• Consequências do Axioma da Escolha , baseado no livro de Paul Howard e Jean Rubin.
• Artigo "The Axiom of Choice" de John Lane Bell na Stanford Encyclopedia of Philosophy .