Quais teoremas interessantes no TCS dependem do axioma da escolha? (Ou, alternativamente, o axioma da determinação?)

67

Os matemáticos às vezes se preocupam com o axioma da escolha (CA) e o axioma da determinação (DA).

Axiom of Choice : Dado qualquer coleção de conjuntos não vazios, existe uma função f que, dado um conjunto S em C , retorna um membro da S .CfSCS

Axioma da Determinação : Seja um conjunto de cadeias de bits infinitamente longas. Alice e Bob jogam um jogo em que Alice escolhe um 1º bit b 1 , Bob escolhe um segundo bit b 2 e assim por diante, até que uma seqüência infinita x = b 1 b 2 seja construída. Alice ganha o jogo se x S , Bob ganha o jogo se x S . O pressuposto é que, para todo S , existe uma estratégia vencedora para um dos jogadores. (Por exemplo, se S consistir apenas na sequência all-ones, Bob poderá vencer em muitos movimentos finitos.)Sb1b2x=b1b2xSxS SS

Sabe-se que esses dois axiomas são inconsistentes entre si. (Pense nisso, ou vá aqui .)

Outros matemáticos prestam pouca ou nenhuma atenção ao uso desses axiomas em uma prova. Eles parecem ser quase irrelevantes para a ciência da computação teórica, pois acreditamos que trabalhamos principalmente com objetos finitos. No entanto, como o TCS define problemas de decisão computacional como seqüências de bits infinitas, e medimos (por exemplo) a complexidade do tempo de um algoritmo como uma função assintótica sobre os naturais, sempre existe a possibilidade de que o uso de um desses axiomas possa surgir em algumas provas.

Qual é o exemplo mais impressionante no TCS que você sabe onde um desses axiomas é necessário ? (Você conhece algum exemplo?)

Apenas para prenunciar um pouco, observe que um argumento de diagonalização (acima do conjunto de todas as máquinas de Turing, por exemplo) não é uma aplicação do Axioma da Escolha. Embora a linguagem que uma máquina de Turing defina seja uma sequência de bits infinita, cada máquina de Turing tem uma descrição finita; portanto, não precisamos realmente de uma função de escolha para muitos conjuntos infinitos aqui.

(Coloquei muitas tags porque não tenho ideia de onde virão os exemplos.)

Ryan Williams
fonte
CW? ou não ? não tenho certeza.
Suresh Venkat
Eu não tenho certeza quer ... esta é uma questão onde eu sou muito inseguro sobre a "complexidade" da resposta ...
Ryan Williams
5
Outros matemáticos prestam pouca ou nenhuma atenção ao uso desses axiomas em uma prova. Os matemáticos realmente usam os dois axiomas descuidados? Se você acidentalmente assumir os dois axiomas, poderá provar qualquer coisa!
Warren Schudy
11
Conjectura de Harvey Friedman . Não sei se isso também se aplica à ciência da computação teórica.
Kaveh
11
Não conheço nenhum resultado na ciência da computação teórica que não possa ser provado em ZF, mas pode ser provado em alguma extensão interessante de ZF. Dito isso, meu palpite é que mesmo esses resultados provavelmente não exigirão o axioma completo da escolha (CA) e que eles exigem apenas uma versão mais fraca do CA, como o axioma da escolha dependente (CD) ou o axioma ainda mais fraco da contagem escolha (AC_ω). Como um aparte, DC (e, portanto, AC_ω) é consistente com o axioma da determinação .
Tsuyoshi Ito

Respostas:

47

Qualquer declaração aritmética comprovável no ZFC é comprovável no ZF e, portanto, não "precisa" do axioma da escolha. Por uma afirmação "aritmética", quero dizer uma afirmação na linguagem aritmética de primeira ordem, o que significa que pode ser afirmada usando apenas quantificadores sobre números naturais ("para todos os números naturais x" ou "existe um número natural x"), sem quantificar sobre conjuntos de números naturais. À primeira vista, pode parecer muito restritivo proibir a quantificação sobre conjuntos de números inteiros; no entanto, conjuntos finitos de números inteiros podem ser "codificados" usando um único número inteiro; portanto, não há problema em quantificar sobre conjuntos finitos de números inteiros.

PNP

Mas espere, você pode dizer, o que dizer de afirmações aritméticas cuja prova requer algo como o lema de Koenig ou o teorema da árvore de Kruskal? Isso não exige uma forma fraca do axioma da escolha? A resposta é que depende exatamente de como você declara o resultado em questão. Por exemplo, se você declarar o teorema menor do gráfico na forma ", dado qualquer conjunto infinito de gráficos não rotulados, devem existir dois deles, de modo que um seja menor do outro" ", então é necessária alguma escolha para avançar seu conjunto infinito de dados, escolhendo vértices, subgráficos etc. [EDIT: cometi um erro aqui. Como Emil Jeřábek explica, o teorema menor do gráfico - ou pelo menos a afirmação mais natural na ausência de CA - é comprovável em ZF. Mas, modulo esse erro, o que digo abaixo ainda está essencialmente correto. ] No entanto, se você escrever uma codificação específica por números naturais da relação menor em gráficos finitos rotulados e frasear o teorema menor do gráfico como uma declaração sobre essa ordem parcial em particular, a declaração se torna aritmética e não requer CA a prova.

A maioria das pessoas sente que a "essência combinatória" do teorema menor do gráfico já é capturada pela versão que corrige uma codificação específica e que a necessidade de chamar o AC para rotular tudo, no caso de você ser apresentado com o conjunto geral. versão teórica do problema, é uma espécie de artefato irrelevante da decisão de usar a teoria dos conjuntos em vez da aritmética como fundamento lógico. Se você se sente da mesma maneira, o teorema menor do gráfico não requer CA. (Veja também este post de Ali Enayat na lista de discussão Fundamentos da Matemática, escrito em resposta a uma pergunta semelhante que eu já tive.)

O exemplo do número cromático do plano é igualmente uma questão de interpretação. Existem várias perguntas que você pode fazer que sejam equivalentes se você assumir a CA, mas que são perguntas distintas se você não assumir a CA. Do ponto de vista do TCS, o cerne combinatório da questão é a colorabilidade de subgráficos finitos do plano e o fato de que você pode (se quiser) usar um argumento de compactação (é aqui que entra a CA) para concluir algo o número cromático de todo o plano é divertido, mas de interesse um tanto tangencial. Então, não acho que esse seja um bom exemplo.

Penso que, em última análise, você pode ter mais sorte perguntando se há alguma pergunta sobre o TCS que exija grandes axiomas cardinais para sua resolução (em vez de CA). O trabalho de Harvey Friedman mostrou que certas declarações finitárias na teoria dos grafos podem exigir grandes axiomas cardinais (ou pelo menos a consistência 1 de tais axiomas). Os exemplos de Friedman até agora são um pouco artificiais, mas eu não ficaria surpreso ao ver exemplos semelhantes surgindo "naturalmente" no TCS durante nossas vidas.

Timothy Chow
fonte
8
Provar a normalização para o cálculo lambda digitado com polimorfismo requer pelo menos aritmética de segunda ordem, e mostrar o mesmo para as teorias de tipo mais generosas pode exigir axiomas cardinais grandes, embora sejam bastante modestos. IIRC, a prova de normalização da Coq precisa de muitos inacessíveis, já que você pode usá-la para codificar argumentos do universo no estilo Grothendieck.
Neel Krishnaswami
3
@ Neel: Bom argumento, embora na IMO esses exemplos "trapaceiem" porque é óbvio que você pode precisar de fortes axiomas lógicos para provar a consistência de um sistema lógico.
Timothy Chow
4
Gosto dessa resposta porque explica por que o uso do axioma de escolha no TCS parece extremamente raro.
Tsuyoshi Ito
11
Π31Π31ZFCZF
11
Esta resposta é apresentada no blog da comunidade.
Aaron Sterling
39

Meu entendimento é que a prova conhecida do teorema de Robertson-Seymour usa o Axioma da Escolha (via teorema da árvore de Kruskal). Isso é consideravelmente interessante do ponto de vista do TCS, pois o teorema de Robertson-Seymour implica que o teste de associação em qualquer família de gráficos menor e fechada pode ser realizado em tempo polinomial. Em outras palavras, o Axiom of Choice pode ser usado indiretamente para provar que os algoritmos de tempo polinomial existem para certos problemas, sem realmente construir esses algoritmos.

Porém, isso pode não ser exatamente o que você está procurando, pois não está claro se a CA é realmente necessária aqui.

Janne H. Korhonen
fonte
Este é um bom começo, pois não se sabe como provar o teorema de outra maneira.
Ryan Williams
7
Como mencionado na página da Wikipedia, o artigo de Friedman, Robertson e Seymour sobre a metamatemática do teorema menor do gráfico mostra que o teorema menor do gráfico implica (uma forma de) o teorema da árvore de Kruskal sobre a teoria básica RCA_0, portanto, isso estabelece que o Kruskal o teorema da árvore é necessário para o teorema menor do gráfico em um sentido forte. No entanto, se isso significa que o axioma da escolha é necessário para o teorema menor do gráfico é uma questão um pouco complicada. Depende de maneira sutil de como você escolhe o teorema menor do gráfico. Veja minha resposta para mais detalhes.
Timothy Chow
7
Emil Jeřábek mostrou no MathOverflow como provar o teorema de Robertson-Seymour sem o axioma da escolha. Isso foi surpreendente para mim, porque eu também tinha a impressão de que o Robertson-Seymour para gráficos não rotulados exigia CA, mas isso era evidentemente uma impressão errada.
Timothy Chow
Então a resposta aceita é realmente falsa?
Andrej Bauer
@AndrejBauer: Se você está se referindo à minha resposta, está certo que o que eu disse sobre Robertson-Seymour está errado. Tentei editar minha resposta agora, mas não consegui. Talvez eu não tenha reputação suficiente para editar um post tão antigo.
Timothy Chow
21

Isso está relacionado à resposta dada por Janne Korhonen.

Nos anos 80 e 90, houve uma série de resultados que tentaram caracterizar os sistemas de axiomas (em outras palavras, a teoria aritmética) necessários para provar extensões do Teorema da Árvore de Kruskal (KTT; o KTT original é de 1960). Em particular, Harvey Friedman provou vários resultados seguindo esta linha (veja SG Simpson. Inprovabilidade de certas propriedades combinatórias de árvores finitas . Em LA Harrington et al., Editor da Research on Foundations of Mathematics de Harvey Friedman. Elsevier, North-Holland, 1985) . Esses resultados mostraram que (certas extensões do) KTT devem usar axiomas de compreensão "fortes" (isto é, axiomas dizendo que existem certos conjuntos de alta complexidade lógica). Não sei exatamente sobre a possibilidade de extensões do KTT no ZF (sem o axioma da escolha).

Paralelamente a esse fluxo de resultados, houve uma tentativa de conectá-lo ao TCS ("Teoria B") por meio de sistemas de reescrita . A idéia é construir sistemas de reescrita (pense nisso como uma espécie de programação funcional ou programas de cálculo lambda) para os quais sua terminação depende de certas (extensões) do KTT (a conexão original entre o KTT e a reescrita do sistema foi provada por N Dershowitz (1982)). Isso implica que, para mostrar que certos programas terminam, é necessário axiomas fortes (já que extensões do KTT precisam de tais axiomas). Para esse tipo de resultado, ver, por exemplo, A. Weiermann, A complexidade limita algumas formas finitas do teorema de Kruskal , Journal of Symbolic Computation 18 (1994), 463-488.

Iddo Tzameret
fonte
16

R2

Em Selá e Soifer, "Axioma de escolha e número cromático do plano" , é mostrado que, se todos os subgráficos finitos do plano são quatro cromáticos, então

  • Se você assume o axioma da escolha, o plano é cromático.
  • Se você assume o princípio das escolhas dependentes e que todos os conjuntos são mensuráveis ​​de Lebesgue, o plano é cinco, seis ou sete cromático.
Derrick Stolee
fonte
Isso não é mais orientado para a matemática do que para o TCS?
MS Dousti 5/10/10
Foi por isso que eu disse "tangencialmente" relacionado. Os problemas de coloração são orientados para o TCS, mas não esse específico.
Derrick Stolee
4
α
Excelente. Validação.
Derrick Stolee
5

Parte do trabalho de Olivier Finkel parece estar relacionado à pergunta - embora não necessariamente explicitamente sobre o axioma da própria escolha - e em consonância com a resposta de Timothy Chow. Por exemplo, citando o resumo de Teoremas da Incompletude, Cardeais Grandes e Autômatos sobre Palavras Finitas , TAMC 2017 ,

Tn:=ZFC+``There exist (at least) n inaccessible cardinals''n0
Sylvain
fonte
3

[Esta não é uma resposta direta à sua pergunta, mas pode ser sugestiva e / ou informativa para algumas pessoas.]

A pesquisa P vs. NP de William Gasarch fornece algumas estatísticas sobre "como P vs. NP será resolvido":

  1. 61 pensou P ≠ NP.
  2. 9 pensaram P = NP.
  3. 4 pensaram que é independente . Embora nenhum sistema de axioma em particular tenha sido mencionado, suponho que eles pensem que é independente do ZFC .
  4. 3 apenas afirmaram que NÃO é independente da aritmética recursiva primitiva.
  5. Eu disse que dependeria do modelo.
  6. 22 não ofereceu opinião.

A Wikipedia tem uma visão interessante da independência:

... Essas barreiras também levaram alguns cientistas da computação a sugerir que o problema P versus NP pode ser independente de sistemas de axioma padrão como o ZFC (não pode ser provado ou refutado dentro deles). A interpretação de um resultado de independência pode ser a inexistência de um algoritmo de tempo polinomial para qualquer problema completo de NP e essa prova não pode ser construída no (por exemplo) ZFC, ou a possibilidade de existir algoritmos de tempo polinomial para problemas de NP completo, mas é impossível provar no ZFC que tais algoritmos estão corretos [ 1] No entanto, se for possível demonstrar, usando técnicas do tipo atualmente conhecido como aplicável, que o problema não pode ser resolvido, mesmo com suposições muito mais fracas estendendo os axiomas de Peano (PA) para aritmética inteira, então necessariamente existiria quase algoritmos de tempo polinomial para todos os problemas em NP [ 2 ]. Portanto, se alguém acredita (como a maioria dos teóricos da complexidade) que nem todos os problemas em NP têm algoritmos eficientes, seguiria que provas de independência usando essas técnicas não podem ser possíveis. Além disso, esse resultado implica que provar a independência do PA ou ZFC usando as técnicas atualmente conhecidas não é mais fácil do que provar a existência de algoritmos eficientes para todos os problemas no NP.

MS Dousti
fonte
5
Outro fato interessante (também da Wikipedia) é que, a principal (somente?) Técnica geral para provar independência no ZFC, forçando, não pode provar que P =? NP é independente do ZFC. Este é um corolário do teorema do absolutismo de Shoenfield.
Travis Service
Obrigado Travis. Aqui está o ponteiro: en.wikipedia.org/wiki/Absoluteness . Veja também cs.uwaterloo.ca/~shai/P%20vs%20NP-2.ppt e blog.computationalcomplexity.org/2009/09/… .
MS Dousti 5/10/10
Observe que Bill está participando de outra enquete, que fica aberta por mais um mês: blog.computationalcomplexity.org/2011/06/…
Charles
@ Charles: Obrigado pela atualização. Estou realmente ansioso para conhecer o consenso mais recente da comunidade.
MS Dousti 10/09/11
2

ZF

Gχ(H)HGG

ZF

Stella Biderman
fonte
Belo exemplo. Acho que Timothy Chow abordou esse tipo de exemplo no parágrafo sobre o número cromático do avião.
Sasho Nikolov
@SashoNikolov A colorabilidade dos gráficos é, na minha opinião, claramente um problema do TCS, mesmo quando os gráficos são infinitos. O problema de Hadwiger-Nelson está muito menos obviamente dentro do âmbito do TCS, como comentaram os comentaristas e o OP dessa resposta concordou. Em contraste, eu não acho que há alguém que iria olhar para este teorema e ir “isso não é realmente um problema CS”
Stella Biderman
Não vejo a distinção: Hadwiger-Nelson também trata de colorir um gráfico geométrico infinito. De qualquer forma, eu realmente gostei e votei nos dois exemplos e acho inútil tentar fazer uma distinção muito fina entre o TCS e outras áreas da Matemática.
Sasho Nikolov