Matemática Construtiva

Índice:

Matemática Construtiva
Matemática Construtiva

Vídeo: Matemática Construtiva

Vídeo: Matemática Construtiva
Vídeo: Aula de Matematica Construtiva 2024, Março
Anonim

Navegação de entrada

  • Conteúdo da Entrada
  • Bibliografia
  • Ferramentas Acadêmicas
  • Pré-visualização do Friends PDF
  • Informações sobre autor e citação
  • De volta ao topo

Matemática Construtiva

Publicado pela primeira vez em 1997-11-18; revisão substantiva qua 30 maio 2018

A matemática construtiva se distingue de sua contraparte tradicional, a matemática clássica, pela estrita interpretação da frase "existe" como "podemos construir". Para trabalhar de maneira construtiva, precisamos reinterpretar não apenas o quantificador existencial, mas todos os conectivos e quantificadores lógicos como instruções sobre como construir uma prova da afirmação envolvendo essas expressões lógicas.

Neste artigo, apresentamos a matemática construtiva moderna com base na interpretação BHK dos conectivos e quantificadores lógicos. Discutimos quatro grandes variedades de matemática construtiva, com ênfase particular nas duas variedades associadas a Errett Bishop e Per Martin-Löf, que podem ser consideradas como sistemas construtivos mínimos. Em seguida, delineamos o progresso na matemática reversa construtiva (informal), um programa de pesquisa que procura identificar princípios, como o teorema dos fãs de Brouwer, que, somados às variedades construtivas mínimas, facilitam as provas de importantes teoremas analíticos. Após uma breve discussão sobre álgebra construtiva, economia e finanças, a entrada termina com dois apêndices: um sobre certos princípios lógicos que se mantêm na matemática clássica, intuicionista e recursiva e que, acrescentada a Bishop 's matemática construtiva, facilita a prova de certos teoremas úteis de análise; e uma discutindo abordagens para um desenvolvimento construtivo da topologia geral.

  • 1. Introdução
  • 2. A interpretação construtiva da lógica
  • 3. Variedades de Matemática Construtiva

    • 3.1 Matemática Intuicionista
    • 3.2 Matemática Construtiva Recursiva
    • 3.3 Matemática Construtiva do Bispo
    • 3.4 Teoria construtiva dos tipos de Martin-Löf
  • 4. O axioma da escolha
  • 5. Matemática Reversa Construtiva

    5.1 Teoremas de fãs no CRM

  • 6. Topologia Construtiva
  • 7. Economia e Finanças Matemáticas Construtivas
  • 8. Observações finais
  • Bibliografia

    • Referências
    • Literatura relacionada
  • Ferramentas Acadêmicas
  • Outros recursos da Internet
  • Entradas Relacionadas

1. Introdução

Antes de os matemáticos afirmarem algo (que não seja um axioma), eles deveriam ter provado ser verdade. O que, então, os matemáticos querem dizer quando afirmam uma disjunção (P / vee Q), onde (P) e (Q) são afirmações sintaticamente corretas em alguma linguagem matemática (formal ou informal)? Uma interpretação natural - embora, como veremos, não a única - dessa disjunção é que não apenas (pelo menos) uma das afirmações (P, Q) é válida, mas também podemos decidir qual delas é válida. Assim, da mesma forma que os matemáticos afirmarão (P) somente quando tiverem decidido que (P) se mantém comprovado, eles podem afirmar (P / vee Q) somente quando eles puderem produzir uma prova de (P).) ou então produza um de (Q).

Com essa interpretação, no entanto, encontramos um problema sério no caso especial em que (Q) é a negação, (neg P), de (P). Afirmar (neg P) é mostrar que (P) implica uma contradição (como (0 = 1)). Mas, freqüentemente, os matemáticos não têm uma prova de (P) nem uma de (neg P). Para ver isso, precisamos refletir apenas sobre a seguinte conjectura de Goldbach (GC):

Todo inteiro inteiro (gt 2) pode ser escrito como uma soma de dois números primos, que permanece nem provado nem refutado, apesar dos melhores esforços de muitos dos principais matemáticos desde que foi levantado pela primeira vez em uma carta de Goldbach a Euler em 1742. Somos forçados a concluir que, sob a interpretação muito natural da decidibilidade de P (vee Q), apenas um otimista teimoso pode manter uma crença na lei do meio excluído (LEM):

Para toda declaração (P), (P) ou (neg P) é válida.

A lógica clássica contorna isso ao ampliar a interpretação da disjunção: ela interpreta (P / vee Q) como (neg (neg P / wedge / neg Q)) ou, em outras palavras, “é contraditório que (P) e (Q) são falsos”. Por sua vez, isso leva à interpretação idealista da existência, na qual (existe xP (x)) significa (neg / forall x / neg P (x)) (“é contraditório que (P (x)) seja falso para cada (x)”). É nessas interpretações de disjunção e existência que os matemáticos construíram o grande e aparentemente inexpugnável edifício da matemática clássica que serve de base para as ciências físicas, sociais e (cada vez mais) biológicas. No entanto, as interpretações mais amplas têm um custo: por exemplo, quando passamos de nossa interpretação inicial natural de (P / vee Q) para o uso irrestrito da idealista,(neg (neg P / wedge / neg Q)), a matemática resultante geralmente não pode ser interpretada dentro de modelos computacionais, como a teoria da função recursiva.

Este ponto é ilustrado por um exemplo bem usado, a proposição:

Existem números irracionais (a, b) tais que (a ^ b) é racional.

Uma boa prova clássica é a seguinte. Qualquer (sqrt {2} ^ { sqrt {2}}) é racional; nesse caso, tomamos (a = b = / sqrt {2}); ou então (sqrt {2} ^ { sqrt {2}}) é irracional; nesse caso, tomamos (a = / sqrt {2} ^ { sqrt {2}}) e (b = / sqrt {2}) (ver Dummett 1977 [2000], 6). Mas, como está, essa prova não nos permite identificar qual das duas opções do par ((a, b)) tem a propriedade necessária. Para determinar a escolha correta de ((a, b)), precisaríamos decidir se (sqrt {2} ^ { sqrt {2}}) é racional ou irracional, o que é precisamente o Empregue nossa interpretação inicial de disjunção com (P), a afirmação “(sqrt {2} ^ { sqrt {2}}) é racional”.

Aqui está outra ilustração da diferença entre interpretações. Considere a seguinte declaração simples sobre o conjunto (bR) de números reais:

(tag {*} forall x / in / bR (x = 0 / vee x / ne 0),)

onde, por razões que divulgamos em breve, (x / ne 0) significa que podemos encontrar um número racional (r) com (0 / lt r / lt / abs {x}). Uma interpretação computacional natural de (*) é que temos um procedimento que, aplicado a qualquer número real (x), nos diz que (x = 0) ou nos diz que (x / ne 0) (Por exemplo, esse procedimento pode gerar 0 se (x = 0) e 1 se (x / ne 0).) No entanto, como o computador pode manipular números reais apenas por meio de aproximações racionais finitas, ter o problema de subfluxo, no qual um número positivo suficientemente pequeno pode ser interpretado como 0 pelo computador; portanto, não pode haver um procedimento de decisão que justifique a declaração (*). Em outras palavras, não podemos esperar (*) manter nossa interpretação computacional natural do quantificador (forall) e do conectivo (vee).

Vamos examinar isso de outro ângulo. Seja (G (n)) agir como uma abreviação para a afirmação “(2n + 2) é uma soma de dois números primos”, onde (n) varia sobre os números inteiros positivos e define uma sequência binária infinita (ba = (a_1, a_2, / ldots)) da seguinte maneira:

[a_n = / begin {cases} 0 & / text {if} G (n) text {contém para todos} k / le n \\ 1 & / text {if} neg G (n) text {contém por alguns} k / le n \\ / end {cases})

Não há dúvida de que (ba) é uma sequência computacionalmente bem definida, no sentido de que temos um algoritmo para calcular (a_n) para cada (n): verifique os números pares (4, 6,8, / ldots, 2n + 2) para determinar se cada um deles é uma soma de dois números primos; nesse caso, defina (a_n = 0) e, no caso contrário, defina (a_n = 1). Agora considere o número real cujo (n) th dígito binário é (a_n):

(begin {align *} x & = (0 / cdot a_1 a_2 / cdots) _ {2} & = 2 ^ {- 1} a_1 + 2 ^ {- 2} a_2 + / cdots \& = / sum_ {n = 1} ^ { infty} 2 ^ {- n} a_n. / end {align *})

Se (*) é válido sob nossa interpretação computacional, podemos decidir entre as duas alternativas a seguir:

  • (2 ^ {- 1} a_1 + 2 ^ {- 2} a_2 + / cdots = 0), o que implica que (a_n = 0) para cada (n);
  • podemos encontrar um número inteiro positivo (N) tal que (2 ^ {- 1} a_1 + 2 ^ {- 2} a_2 + / cdots / gt 2 ^ {- N}).

No último caso, testando (a_1, / ldots, a_N), podemos encontrar (n / le N) de modo que (a_n = 1). Assim, a interpretação computacional de (*) nos permite decidir se existe (n) tal que (a_n = 1); em outras palavras, nos permite decidir o status da conjectura de Goldbach. Um exemplo desse tipo, mostrando que uma prova construtiva de algum resultado clássico (P) nos permitiria resolver a conjectura de Goldbach (e, por argumentos semelhantes, muitos outros problemas até então abertos, como a hipótese de Riemann), é chamada um exemplo brouweriano para, ou mesmo um contraexemplo brouweriano, da declaração (P) (embora não seja um contraexemplo no sentido normal dessa palavra).

O uso da conjectura de Goldbach aqui é puramente dramático. Pois, o argumento do parágrafo anterior pode ser modificado para mostrar que, sob nossa interpretação computacional, (*) implica o princípio limitado da onisciência (LPO):

Para cada sequência binária ((a_1, a_2, / ldots)) (a_n = 0) para todos (n) ou existe (n) tal que (a_n = 1), que é geralmente considerado como um princípio essencialmente não construtivo por várias razões. Primeiro, sua interpretação recursiva, Existe um algoritmo recursivo que, aplicado a qualquer sequência binária definida recursivamente ((a_1, a_2, / ldots)), gera 0 se (a_n = 0) para todos (n) e gera 1 se (a_n = 1) para alguns (n), é comprovadamente falso dentro da teoria da função recursiva, mesmo com a lógica clássica (ver Bridges & Richman [1987], capítulo 3); portanto, se queremos permitir uma interpretação recursiva de toda a nossa matemática, não podemos usar o LPO. Em segundo lugar, existe uma teoria do modelo (modelos de Kripke) na qual pode ser demonstrado que o LPO não é construtivamente derivável (Bridges & Richman [1987], capítulo 7).

2. A interpretação construtiva da lógica

Agora, deve estar claro que um desenvolvimento computacional completo da matemática desaprova as interpretações idealistas da disjunção e da existência das quais depende a maioria da matemática clássica. Para trabalhar construtivamente, precisamos retornar das interpretações clássicas para as interpretativas naturais:

(vee) (ou): para provar (P / vee Q), precisamos ter uma prova de (P) ou uma prova de (Q).
(wedge) (e): para provar (P / cunha Q), precisamos ter uma prova de (P) e uma prova de (Q).
(Rightarrow) (implica): uma prova de (P / rightarrow Q) é um algoritmo que converte qualquer prova de (P) em uma prova de (Q).
(neg) (não): para provar (neg P), devemos mostrar que (P) implica (0 = 1).
(existe) (existe): para provar (existe xP (x)) precisamos construir um objeto (x) e provar que (P (x)) é válido.
(forall) (para cada um / todos): uma prova de (forall x / no SP (x)) é um algoritmo que, aplicado a qualquer objeto (x) e aos dados que provam que (x / in S), comprova que (P (x)) mantém.

Essas interpretações da BHK (o nome reflete sua origem no trabalho de Brouwer, Heyting e Kolmogorov) podem ser mais precisas usando a noção de realização de Kleene; ver (Dummett [1977/2000], 222-234; Beeson [1985], capítulo VII).

Que tipo de coisas estamos procurando se levamos a sério o desenvolvimento da matemática de tal maneira que, quando um teorema afirma a existência de um objeto (x) com uma propriedade (P), a prova do teorema incorpora algoritmos para construir (x) e demonstrar, por quaisquer cálculos necessários, que (x) possui a propriedade (P). Aqui estão alguns exemplos de teoremas, cada um seguido por uma descrição informal dos requisitos para sua prova construtiva.

  1. Para cada número real (x), (x = 0) ou (x / ne 0). Requisito de prova: um algoritmo que, aplicado a um determinado número real (x), decide se (x = 0) ou (x / ne 0). Observe que, para tomar essa decisão, o algoritmo pode usar não apenas os dados que descrevem (x), mas também os dados que mostram que (x) é realmente um número real.
  2. Cada subconjunto não vazio (S) de (bR) que é delimitado acima tem um limite mínimo mínimo.

    Requisito de prova: um algoritmo que, aplicado a um conjunto (S) de números reais, um membro (s) de (S) e um limite superior para (S),

    1. calcula um objeto (b) e mostra que (b) é um número real;
    2. mostra que (x / le b) para cada (x / em S); e
    3. dado um número real (b '\ lt b), calcula um elemento (x) de (S) tal que (x / gt b').
  3. Se (f) é um mapeamento contínuo com valor real no intervalo fechado ([0,1]), de modo que (f (0) cdot f (1) lt 0), existe (x) tal que (0 / lt x / lt 1) e (f (x) = 0).

    Requisito de prova: um algoritmo que, aplicado à função (f), um módulo de continuidade para (f) e os valores (f (0)) e (f (1)),

    1. calcula um objeto (x) e mostra que (x) é um número real entre 0 e 1; e
    2. mostra que (f (x) = 0).
  4. Se (f) é um mapeamento contínuo com valor real no intervalo fechado ([0,1]), de modo que (f (0) cdot f (1) lt 0), então para cada (varepsilon / gt 0) existe (x) tal que (0 / lt x / lt 1) e (abs {f (x)} lt / varepsilon).

    Requisito de prova: um algoritmo que, aplicado à função (f), um módulo de continuidade para (f), os valores (f (0)) e (f (1)) e um número positivo (varepsilon),

    1. calcula um objeto (x) e mostra que (x) é um número real entre 0 e 1; e
    2. mostra que (abs {f (x)} lt / varepsilon).

Já temos motivos para duvidar que (A) tenha uma prova construtiva. Se os requisitos de prova para (B) puderem ser cumpridos, então, dada qualquer afirmação matemática (P), podemos aplicar nossa prova de (B) para calcular uma aproximação racional (z) ao supremo (sigma) do conjunto

[S = {0 } cup {x / in / bR: P / cunha x = 1 })

com erro (lt / bfrac {1} {4}). Podemos então determinar se (z / gt / bfrac {1} {4}), nesse caso (sigma / gt 0) ou (z / lt / bfrac {3} {4}), quando (sigma / lt 1). No primeiro caso, existe (x / em S) com (x / gt 0), portanto devemos ter (x = 1) e, portanto, (P). No caso (sigma / lt 1), temos (neg P). Assim (B) implica a lei do meio excluído.

No entanto, na teoria construtiva de Bishop dos números reais, baseada em seqüências de Cauchy com uma taxa de convergência pré-atribuída, podemos provar o seguinte princípio construtivo de limite mínimo superior:

Seja (S) um subconjunto não vazio de (bR) que é delimitado acima. Então (S) possui um limite mínimo mínimo se, e somente se, estiver na ordem superior, no sentido de que, para todos os números reais (alpha, / beta), com (alpha / lt / beta), (beta) é um limite superior para (S) ou existe (x / in S) com (x / gt / alpha) (Bishop & Bridges [1985], p. 37, Proposição (4.3)).

De passagem, mencionamos um desenvolvimento alternativo da teoria construtiva de (bR) baseada na aritmética de intervalos; veja o capítulo 2 de Bridges & Vîță [2006].

Cada uma das declarações (C) e (D), classicamente equivalentes, é uma versão do Teorema do Valor Intermediário. Nessas instruções, um módulo de continuidade para (f) é um conjunto (Omega) de pares ordenados ((varepsilon, / delta)) de números reais positivos com as duas propriedades a seguir:

  • para cada (varepsilon / gt 0) existe (delta / gt 0) tal que ((varepsilon, / delta) no / Omega)
  • para cada ((varepsilon, / delta) in / Omega) e para todos (x, y / em [0,1]) com (abs {x - y} lt / delta), temos (abs {f (x) - f (y)} lt / varepsilon).

A declaração (C) envolve outro princípio essencialmente não construtivo, o princípio menos onisciente da onisciência (LLPO):

Para cada sequência binária ((a_1, a_2, / ldots)) com no máximo um termo igual a 1, (a_n = 0) para todos os pares (n) ou então (a_n = 0) para todos os ímpares (n).

A afirmação (D), uma forma fraca de (C), pode ser provada de forma construtiva, usando um argumento de intervalo padrão de um tipo padrão. O seguinte teorema do valor intermediário construtivo mais forte, que é suficiente para fins mais práticos, é comprovado usando um argumento de intervalo aproximado para metade:

Seja (f) um mapeamento contínuo com valor real no intervalo fechado ([0,1]) de modo que (f (0) cdot f (1) lt 0). Suponha também que (f) seja localmente diferente de zero, no sentido de que para cada (x / in [0,1]) e cada (r / gt 0), exista (y) tal que (abs {x - y} lt r) e (f (y) ne 0). Então existe (x) tal que (0 / lt x / lt 1) e (f (x) = 0).

A situação do teorema do valor intermediário é típica de muitos na análise construtiva, onde encontramos um teorema clássico com várias versões construtivas, algumas ou todas que podem ser equivalentes sob a lógica clássica.

Existe um princípio de onisciência cujo status construtivo é menos claro que o de LPO e LLPO - ou seja, o princípio de Markov (MP):

Para cada sequência binária ((a_n)), se for contraditório que todos os termos (a_n) sejam iguais a 0, existe um termo igual a 1.

Esse princípio é equivalente a várias proposições clássicas simples, incluindo as seguintes:

  • Para cada número real (x), se é contraditório que (x) é igual a 0, então (x / ne 0) (no sentido que mencionamos anteriormente).
  • Para cada número real (x), se é contraditório que (x) é igual a 0, então existe (y / in / bR) tal que (xy = 1).
  • Para cada mapeamento contínuo individual (f: [0,1] rightarrow / bR), se (x / ne y), então (f (x) ne f (y)).

O princípio de Markov representa uma pesquisa ilimitada: se você tem uma prova de que todos os termos (a_n) sendo 0 levam a uma contradição, testando os termos (a_1, a_2, a_3, / ldots), por sua vez, garantia de encontrar um termo igual a 1; mas essa garantia não se estende à garantia de que você encontrará o termo desejado antes do fim do universo. A maioria dos praticantes de matemática construtiva vê o princípio de Markov com pelo menos suspeita, se não com total descrença. Tais visões são reforçadas pela observação de que existe um modelo de Kripke mostrando que o MP não é derivado construtivamente (Bridges & Richman [1987], 137–138).

3. Variedades de Matemática Construtiva

O desejo de manter a possibilidade de uma interpretação computacional é uma motivação para usar as reinterpretações construtivas dos conectivos e quantificadores lógicos que fornecemos acima; mas não é exatamente a motivação dos pioneiros do construtivismo na matemática. Nesta seção, examinamos algumas das diferentes abordagens do construtivismo em matemática nos últimos 130 anos.

3.1 Matemática Intuicionista

No final do século XIX, certos indivíduos - principalmente Kronecker e Poincaré - expressaram dúvidas ou até desaprovação dos métodos idealistas e não construtivos usados por alguns de seus contemporâneos; mas é nos escritos polêmicos de LEJ Brouwer (1881-1966), começando com sua tese de doutorado em Amsterdã, Brouwer [1907], e continuando nos próximos quarenta e sete anos, que os fundamentos de uma abordagem sistemática e precisa da matemática construtiva foram colocados. Na filosofia de Brouwer, conhecida como intuicionismo, a matemática é uma criação livre da mente humana, e um objeto existe se, e somente se, puder ser construído (mentalmente). Se alguém adota essa posição filosófica, então é inexoravelmente atraído pela interpretação construtiva anterior dos conectivos e quantificadores lógicos:pois como uma prova da impossibilidade da inexistência de um certo objeto (x) descreve uma construção mental de (x)?

Brouwer não era o expositor mais claro de suas idéias, como mostra a seguinte citação:

A matemática surge quando o sujeito do duplo, resultante da passagem do tempo, é abstraído de todas as ocorrências especiais. A forma vazia restante [a relação de (n) com (n + 1)] do conteúdo comum de todas essas duas coisas torna-se a intuição original da matemática e repetida ilimitadamente cria novos assuntos matemáticos. (citado em Kline [1972], 1199–2000)

Uma versão moderna da visão de Brouwer foi dada por Errett Bishop (Bishop [1967], p. 2):

A principal preocupação da matemática é o número, e isso significa os números inteiros positivos. Sentimos o número da maneira como Kant se sentia sobre o espaço. Os números inteiros positivos e sua aritmética são pressupostos pela própria natureza da nossa inteligência e, somos tentados a acreditar, pela própria natureza da inteligência em geral. O desenvolvimento dos números inteiros positivos a partir do conceito primitivo da unidade, do conceito de adjacência de uma unidade e do processo de indução matemática traz convicção completa. Nas palavras de Kronecker, os números inteiros positivos foram criados por Deus.

Por mais obscuros que os escritos de Brouwer pudessem ser, uma coisa sempre estava clara: para ele, a matemática tinha precedência sobre a lógica. Pode-se dizer, como Hermann Weyl fez na passagem seguinte, que Brouwer viu a matemática clássica como defeituosa precisamente no uso da lógica clássica sem referência à matemática subjacente:

De acordo com a visão de [Brouwer] e a leitura da história, a lógica clássica foi abstraída da matemática de conjuntos finitos e seus subconjuntos. (…) Esquecido dessa origem limitada, depois confundiu essa lógica com algo acima e antes de toda matemática, e finalmente a aplicou, sem justificativa, à matemática de conjuntos infinitos. Este é o outono e o pecado original da teoria dos conjuntos, pelos quais é justamente punido pelas antinomias. Não é que essas contradições tenham sido surpreendentes, mas elas tenham aparecido em um estágio tão tardio do jogo. (Weyl, 1946)

Em particular, esse mau uso da lógica levou a provas de existência não construtivas que, nas palavras de Weyl, "informam ao mundo que um tesouro existe sem revelar sua localização".

Para descrever a lógica usada pelo matemático intuicionista, foi necessário primeiro analisar os processos matemáticos da mente, a partir dos quais a lógica poderia ser extraída. Em 1930, o aluno mais famoso de Brouwer, Arend Heyting, publicou um conjunto de axiomas formais que caracterizam tão claramente a lógica usada pelos intuicionistas que se tornaram universalmente conhecidos como axiomas da lógica intuicionista (Heyting [1930]). Esses axiomas capturaram a interpretação informal da BHK dos conectivos e quantificadores que fornecemos anteriormente.

A matemática intuicionista diverge de outros tipos de matemática construtiva na interpretação do termo “sequência”. Normalmente, uma sequência na matemática construtiva é dada por uma regra que determina, com antecedência, como construir cada um de seus termos; pode-se dizer que essa sequência é semelhante à lei ou predeterminada. Brouwer generalizou essa noção de sequência para incluir a possibilidade de construir os termos um por um, sendo a escolha de cada termo feita livremente ou sujeita apenas a certas restrições estipuladas previamente. A maioria das manipulações de sequências não exige que sejam predeterminadas e podem ser realizadas nessas sequências de escolha livre mais gerais.

Assim, para o intuicionista, um número real (bx = (x_1, x_2, / ldots)) - essencialmente, uma sequência cauchy de números racionais - não precisa ser dada por uma regra: seus termos (x_1, x_2, / ldots), são simplesmente números racionais, construídos sucessivamente, sujeitos apenas a algum tipo de restrição de Cauchy, como a seguinte usada por Bishop [1967]:

(forall m / forall n / left (abs {x_m - x_n} le / left (frac {1} {m} + / frac {1} {n} right) right])

Uma vez que as seqüências de livre escolha são admitidas na matemática, então, talvez para surpresa inicial de alguém, existem certos princípios de forte escolha. Seja (P) um subconjunto de (bN ^ { bN} times / bN) (onde (bN) denota o conjunto de números naturais e, para os conjuntos (A) e (B, B ^ A) denota o conjunto de mapeamentos de (A) para (B)) e suponha que para cada (ba / in / bN ^ { bN}) exista (n / in / bN) tal que ((ba, n) em P). Do ponto de vista construtivo, isso significa que temos um procedimento, aplicável às seqüências, que calcula (n) para qualquer dado (ba). Segundo Brouwer, a construção de um elemento de (bN ^ { bN}) é para sempre incompleta: uma sequência genérica (ba) é puramente extensional, no sentido de que, a qualquer momento, não podemos saber nada sobre (ba) que não seja um conjunto finito de termos. Daqui resulta que nosso procedimento deve ser capaz de calcular, a partir de alguma sequência inicial finita ((a_0, / ldots, a_N)) dos termos de (ba), um número natural (n) tal que (P (ba, n)). Se (bb / in / bN ^ { bN}) é qualquer sequência tal que (b_ {k} = a_ {k}) para (0 / le k / le N), então nosso procedimento deve retornar o mesmo (n) para (bb) como para (ba). Isso significa que (n) é uma função contínua de (ba) com relação à topologia em (bN ^ { bN}) fornecida pela métricaIsso significa que (n) é uma função contínua de (ba) com relação à topologia em (bN ^ { bN}) fornecida pela métricaIsso significa que (n) é uma função contínua de (ba) com relação à topologia em (bN ^ { bN}) fornecida pela métrica

(varrho: (ba, / bb) rightquigarrow / inf {2 ^ {- n}: a_k = b_k / text {para} 0 / le k / le n }.)

Somos, portanto, levados ao seguinte princípio de escolha contínua, que dividimos em uma parte de continuidade e uma parte de escolha.

CC1: Qualquer função de (bN ^ { bN}) a (bN) é contínua.

CC2: Se (P / subseteq / bN ^ { bN} times / bN) e para cada (ba / in / bN ^ { bN}) existe (n / in / bN) tal que ((ba, n) em P), existe uma função (f: / bN ^ { bN} rightarrow / bN) tal que ((ba, f (ba)) em P) para todos (ba / in / bN ^ { bN}).

Se (P) e (f) são como em CC2, então dizemos que (f) é uma função de escolha para (P).

Os princípios de onisciência LPO e LLPO são comprovadamente falsos sob as hipóteses CC1–2; mas MP é consistente com isso. Entre as conseqüências notáveis de CC1–2 estão as seguintes.

  • Qualquer função de (bN ^ { bN}) ou (2 ^ { bN}) a um espaço métrico é contínua em pontos.
  • Todo mapeamento de um espaço métrico separável completo não vazio para um espaço métrico é contínuo em pontos.
  • Todo mapa da linha real (bR) para si mesmo é contínuo em pontos.
  • Seja (X) um espaço normal separável completo, (Y) um espaço normalizado e ((u_n)) uma sequência de mapeamentos lineares de (X) a (Y), de modo que, para cada vetor de unidade (x) de (X), (phi (x) = / sup { Vert u_n (x) rVert: n / in / bN }) existe. Existe (c / gt 0) tal que (lVert u_n (x) rVert / le c) para todos (n / in / bN) e todos os vetores unitários (x) de (X) (princípio da delimitação uniforme).

Cada uma dessas afirmações parece contradizer os teoremas clássicos conhecidos. No entanto, a comparação com a matemática clássica não deve ser feita superficialmente: para entender que não há contradição real aqui, devemos entender que o significado de termos como "função" e até "número real" na matemática intuicionista é bem diferente disso no cenário clássico. (Na prática, a matemática intuicionista não pode ser comparada, rápida e diretamente, com a matemática clássica.)

A introspecção de Brouwer sobre a natureza das funções e o continuum o levou a um segundo princípio, que, diferentemente do da escolha contínua, é classicamente válido. Este princípio requer um pouco mais de fundo para sua explicação.

Para qualquer conjunto (S), denotamos por (S ^ *) o conjunto de todas as seqüências finitas de elementos de (S), incluindo a sequência vazia (()). Se (alpha = (a_1, / ldots, a_n)) estiver em (S ^ *), então (n) será chamado o comprimento de (alpha) e será indicado por (abs { alpha}). Se (m / in / bN) e (alpha) é uma sequência finita ou infinita em (S) de comprimento pelo menos (m), então denotamos por (bar { alpha} (m)) a sequência finita que consiste nos primeiros (m) termos de (alpha). Observe que (bar { alpha} (0) = ()) e (abs { bar { alpha} (0)}) = 0. Se (alpha / em S ^ *) e (beta = / bar { alpha} (m)) para alguns (m), dizemos que (alpha) é uma extensão de (beta) e esse (beta) é uma restrição de (alpha).

Diz-se que um subconjunto (sigma) de (S) é destacável (de (S)) se

(forall x / in S (x / in / sigma / vee x / not / in / sigma).)

Um subconjunto destacável (sigma) de (bN ^ *) é chamado de ventilador se

  • está fechado sob restrição: para cada (alpha / in / bN ^ *) e cada (n), se (bar { alpha} (n) em S), então (barra { alpha} (k) em S) sempre que (0 / le k / le n); e
  • para cada (alpha / in / sigma), o conjunto ({ alpha ^ * n / em S: n / in / bN }) é finito ou vazio, onde (alpha ^ * n) denota a sequência finita obtida ao unir o número natural (n) aos termos de (alpha).

Um caminho em um ventilador (sigma) é uma sequência (alpha), finita ou infinita, de modo que (bar { alpha} (n) in / sigma) para cada (n). Dizemos que um caminho (alpha) é bloqueado por um subconjunto (B) se alguma restrição de (alpha) estiver em (B); se nenhuma restrição de (alpha) estiver em (B), dizemos que (alpha) erra (B). Um subconjunto (B) de um ventilador (sigma) é chamado de barra para (sigma) se cada caminho infinito de (sigma) for bloqueado por (B); uma barra (B) para (sigma) é uniforme se existir (n / in / bN), de modo que cada caminho de comprimento (n) seja bloqueado por (B).

Finalmente, podemos afirmar o próximo princípio de intuição do Brouwer, o teorema do ventilador para barras destacáveis (FT (_ D)):

Cada barra destacável de um ventilador é uniforme.

Na sua forma contrapositiva clássica, FT (_ D) é conhecido como Lema de König: se para cada (n) existe um caminho de comprimento (n) que erra (B), existe um infinito caminho que erra (B) (ver Dummett 1977 [2000], 49–53). (É claro que, classicamente, a condição de destacável é supérflua.) É simples construir um contra-exemplo brouweriano ao lema de König.

Brouwer realmente colocou o teorema do ventilador sem a restrição de desmontagem da barra. Tentativas de provar que o teorema mais geral dos fãs se baseia construtivamente em uma análise de como poderíamos saber que um subconjunto é uma barra e levou Brouwer a uma noção de indução de barra; isso é discutido na Seção 3.6 da entrada sobre intuicionismo na filosofia da matemática; Outra boa referência para indução de barra é van Atten (2004). Voltaremos aos teoremas dos fãs na Seção 4.

Das muitas aplicações dos princípios de Brouwer, o mais famoso é o teorema da continuidade uniforme (que segue as conseqüências pontuais da continuidade do CC1-2 em conjunto, uma forma de teorema do ventilador mais geral que o FT (_ D)):

Todo mapeamento de um espaço métrico compacto (ou seja, completo, totalmente delimitado) para um espaço métrico é uniformemente contínuo.

O leitor é alertado mais uma vez para interpretar isso cuidadosamente dentro da estrutura intuicionista de Brouwer, e não para chegar à conclusão errônea de que o intuicionismo contradiz a matemática clássica. É mais sensato considerar os dois tipos de matemática incomparáveis. Para uma discussão mais aprofundada, consulte a entrada sobre lógica intuicionista.

Infelizmente - e talvez inevitavelmente, diante da oposição de matemáticos de estatura como Hilbert - a escola intuicionista de matemática e filosofia de Brouwer tornou-se cada vez mais envolvida naquilo que, pelo menos para os matemáticos clássicos, parecia especulação quase mística sobre a natureza do pensamento construtivo, em detrimento da prática da própria matemática construtiva. Essa infeliz polarização entre os brouwerianos e os hilbertianos culminou no notório bairro Grundlagens da década de 1920, cujos detalhes podem ser encontrados nas biografias de Brouwer por van Dalen [1999, 2005] e van Stigt [1990].

3.2 Matemática Construtiva Recursiva

No final da década de 1940, o matemático russo AA Markov começou o desenvolvimento de uma forma alternativa de matemática construtiva (RUSS), que é, essencialmente, teoria da função recursiva com lógica intuicionista (Markov [1954], Kushner [1985]). Nesta variedade, os objetos são definidos por meio de numerações de Gödel, e os procedimentos são todos recursivos; a principal distinção entre RUSS e a análise recursiva clássica desenvolvida após o trabalho de Turing, Church e outros em 1936 esclareceu a natureza dos processos computáveis é que a lógica usada no RUSS é intuicionista.

Um obstáculo enfrentado pelo matemático que tenta entender o RUSS é que, sendo expresso na linguagem da teoria da recursão, ele não é facilmente legível; de fato, ao abrir uma página das excelentes palestras de Kushner [1985], alguém pode ser perdoado por se perguntar se isso é análise ou lógica. (Essa observação deve ser temperada com referência aos dois livros relativamente legíveis sobre análise recursiva clássica de Aberth [1980, 2001].) Felizmente, pode-se chegar ao coração de RUSS por uma abordagem axiomática de Richman [1983] (ver também Capítulo 3 de Bridges & Richman [1987]).

Primeiro, definimos um conjunto (S) para ser contável se houver um mapeamento de um subconjunto destacável de (bN) para (S). Com a lógica intuicionista, não podemos provar que cada subconjunto de (bN) é destacável (o leitor é convidado a fornecer um exemplo brouweriano para demonstrar isso). Subconjuntos contáveis de (bN) na abordagem axiomática de Richman são os equivalentes de conjuntos recursivamente enumeráveis no desenvolvimento normal de RUSS.

Por uma função parcial em (bN), queremos dizer um mapeamento cujo domínio é um subconjunto de (bN); se o domínio for (bN), chamaremos a função de função parcial total em (bN). A abordagem de Richman ao RUSS é baseada na lógica intuicionista e em um único axioma de funções parciais computáveis (CPF):

Há uma enumeração (phi_0, / phi_1, / ldots) do conjunto de todas as funções parciais de (bN) a (bN) com domínios contáveis.

É notável o que pode ser deduzido de forma limpa e rápida usando esse princípio. Por exemplo, podemos provar o seguinte resultado, que quase imediatamente mostra que o LLPO e, portanto, o LPO, são falsos na configuração recursiva.

Existe uma função parcial total (f: / bN / times / bN / rightarrow {0,1 }) tal que

  • para cada (m) existe no máximo um (n) tal que (f (m, n) = 1); e
  • para cada função parcial total (f: / bN / rightarrow {0,1 }), existe (m, k) em (bN) de modo que (f (m, 2k + f (m)) = 1).

De mais interesse, no entanto, são resultados como os seguintes na RUSS.

  • Teorema de Specker (Specker [1949]): Existe uma sequência estritamente crescente ((r_1, r_2, / ldots)) de números racionais no intervalo fechado ([0,1]) tal que para cada (x / in / bR) existe (N / in / bN) e (delta / gt 0) de modo que (abs {x - r_n} ge / delta) para todos (n / ge N).
  • Para cada (varepsilon / gt 0), existe uma sequência ((I_1, I_2, / ldots)), de intervalos abertos limitados em (bR), de modo que (begin {align} tag {i} bR & / subseteq / bigcup_ {n = 1} ^ { infty} I_n, / text {e} / \ tag {ii} sum_ {n = 1} ^ N / abs {I_n} & / lt / varepsilon / text {para cada} N. / end {align}) (Essa sequência de intervalos é chamada de (varepsilon) - capa singular de (bR).)
  • Existe uma função contínua pontual (f: [0,1] rightarrow / bR) que não é uniformemente contínua.
  • Existe uma função uniformemente contínua com valor positivo (f: [0,1] rightarrow / bR) cujo menor é 0.

Do ponto de vista clássico, esses resultados se encaixam quando se percebe que palavras como "função" e "número real" devem ser interpretadas como "função recursiva" e "número real recursivo", respectivamente. Observe que o segundo dos quatro teoremas recursivos acima é um forte contra-exemplo recursivo à propriedade de compactação de cobertura aberta da linha real (recursiva); e o quarto é um contra-exemplo recursivo ao teorema clássico de que todo mapeamento uniformemente contínuo de um conjunto compacto em (bR) atinge seu máximo.

3.3 Matemática Construtiva do Bispo

O progresso em todas as variedades de matemática construtiva foi relativamente lento ao longo da próxima década e meia. O que era necessário para elevar o perfil do construtivismo na matemática era um matemático clássico de alto escalão para mostrar que era possível um desenvolvimento construtivo completo de análises profundas sem um compromisso com os princípios não clássicos de Brouwer ou com o mecanismo da teoria da função recursiva. Essa necessidade foi atendida em 1967, com o surgimento da monografia de Errett Bishop, Foundations of Constructive Analysis [1967], o produto de um par de anos surpreendentes em que, trabalhando no estilo informal, mas rigoroso, usado pelos analistas normais, Bishop forneceu um desenvolvimento construtivo. de grande parte da análise do século XX, incluindo o teorema de Stone-Weierstrass, os teoremas de Hahn-Banach e de separação,o teorema espectral para operadores independentes em um espaço de Hilbert, os teoremas de convergência de Lebesgue para integrais abstratas, a medida de Haar e a transformada abstrata de Fourier, os teoremas ergódicos e os elementos da teoria da álgebra de Banach. (Veja também Bishop & Bridges [1985].) Assim, de um só golpe, ele mentiu a visão comumente expressa com tanta força por Hilbert:

Tomar o princípio do meio excluído do matemático seria o mesmo, digamos, como proibir o telescópio ao astrônomo ou ao boxeador pelo uso de seus punhos. (Hilbert [1928])

Não apenas a matemática BISH de Bishop tem a vantagem da legibilidade - se você abrir o livro de Bishop em qualquer página, o que você vê é claramente reconhecível como análise, mesmo que, de tempos em tempos, seus movimentos no decorrer de uma prova possam parecer estranhos. alguém que estuda o uso da lei do meio excluído - mas, diferentemente da matemática intuicionista ou recursiva, admite muitas interpretações diferentes. Matemática intuicionista, matemática construtiva recursiva e até matemática clássica fornecem modelos de BISH. De fato, os resultados e as provas no BISH podem ser interpretados, com no mínimo pequenas alterações, em qualquer modelo razoável de matemática computável, como, por exemplo, a Teoria da Efetividade do Tipo Dois de Weihrauch (Weihrauch [2000]; Bauer [2005]).

Como é alcançada essa interpretabilidade múltipla? Pelo menos em parte pela recusa de Bishop em definir sua noção primitiva de "algoritmo" ou, em suas palavras, "rotina finita". Essa recusa levou à crítica de que sua abordagem carece da precisão que um lógico normalmente esperaria de um sistema fundamental. No entanto, essa crítica pode ser superada olhando mais de perto o que os praticantes de BISH realmente fazem quando provam teoremas: na prática, eles estão fazendo matemática com lógica intuicionista. A experiência mostra que a restrição à lógica intuicionista sempre força os matemáticos a trabalhar de uma maneira que, pelo menos informalmente, possa ser descrita como algorítmica; portanto, a matemática algorítmica parece ser equivalente à matemática que usa apenas lógica intuicionista. Se esse é o caso,então podemos praticar matemática construtiva usando lógica intuicionista em qualquer objeto matemático razoavelmente definido, não apenas em alguma classe de "objetos construtivos".

Essa visão, mais ou menos, parece ter sido apresentada por Richman [1990, 1996]. Tomando a lógica como característica principal da matemática construtiva, ela não reflete a primazia da matemática sobre a lógica que fazia parte da crença de Brouwer, Heyting, Markov, Bishop e outros pioneiros do construtivismo. Por outro lado, captura a essência da matemática construtiva na prática.

Assim, pode-se distinguir entre o construtivismo ontológico de Brouwer e outros que são levados à matemática construtiva por acreditar que objetos matemáticos são criações mentais, e o construtivismo epistemológico de Richman e aqueles que vêem a matemática construtiva caracterizada por sua metodologia, com base no uso da lógica intuicionista. Certamente, a primeira abordagem do construtivismo inevitavelmente leva à segunda; e o último certamente não é inconsistente com uma ontologia brouweriana.

Para fazer a matemática real, precisamos mais do que apenas lógica intucionista. Para Bishop, os elementos básicos da matemática foram os números inteiros positivos (veja a citação de Bishop [1967] na Seção 3.1 acima). Entre os primeiros sistemas formais para o BISH estavam a base axiomática de Myhill [1975], baseada em noções primitivas de número, conjunto e função; O sistema de Feferman [1975] para matemática explícita; e a teoria dos conjuntos ZF intuicionista de Friedman [1977]. Os dois fundamentos formais mais favorecidos do BISH nesta fase são a teoria dos conjuntos CZF de Aczel e Rathjen [2000] e a teoria do tipo intuicionista de Martin-Löf [1975, 1984].

3.4 Teoria construtiva dos tipos de Martin-Löf

Antes de encerrar nosso tour pelas variedades da matemática construtiva moderna, visitamos uma quarta variedade, baseada na teoria do tipo intuicionista (ML) de Per Martin-Löf. Martin-Löf publicou suas notas sobre matemática construtiva [1968], com base em palestras que ele dera na Europa em 1966–68; portanto, seu envolvimento com o construtivismo em matemática remonta pelo menos ao período em que Bishop escreveu os fundamentos da análise construtiva. O livro de Martin-Löf está no espírito de RUSS, em vez de BISH; de fato, seu autor não teve acesso ao livro de Bishop até que seu próprio manuscrito estivesse terminado. Mais tarde, Martin-Löf voltou sua atenção para sua teoria dos tipos como base para a matemática construtiva ao estilo do bispo.

Aqui, em suas próprias palavras, há uma explicação informal das idéias subjacentes a ML:

Pensaremos em objetos ou construções matemáticas. Todo objeto matemático é de um certo tipo ou tipo [… e] é sempre fornecido junto com seu tipo. … Um tipo é definido pela descrição do que devemos fazer para construir um objeto desse tipo. … Em outras palavras, um tipo é bem definido se entendermos … o que significa ser um objeto desse tipo. Assim, por exemplo, (bN / rightarrow / bN) [funções de (bN) a (bN)] é um tipo, não porque conhecemos funções teóricas de números específicos, como as recursivas primitivas, mas porque pensamos entender a noção de função teórica dos números em geral. (Martin-Löf [975])

Em particular, neste sistema, toda proposição pode ser representada como um tipo: a saber, o tipo de provas da proposição. Inversamente, cada tipo determina uma proposição: a proposição de que o tipo em questão é habitado. Então, quando pensamos em um certo tipo (T) como uma proposição, interpretamos a fórmula

[x / em T)

como "(x) é uma prova da proposição (T)".

Martin-Löf continua construindo novos tipos, como produtos cartesianos e sindicatos disjuntos, a partir de antigamente. Por exemplo, o produto cartesiano

[(Pi x / em A) B (x))

é o tipo de função que leva um objeto arbitrário (x) do tipo (A) para um objeto do tipo (B (x)). Na interpretação proposições como provas, em que (B (x)) representa uma proposição, o produto cartesiano acima corresponde à proposição universal

[(forall x / in A) B (x).)

Martin-Löf distingue cuidadosamente entre provas e derivações: um objeto de prova é uma testemunha do fato de que alguma proposição foi provada; enquanto uma derivação é o registro da construção de um objeto de prova. Além disso, ele exerce duas formas básicas (uma que não ousa dizer "tipos" aqui)) de julgamento. A primeira é uma relação entre objetos de prova e proposições, a segunda uma propriedade de algumas proposições. No primeiro caso, a sentença é de que um objeto de prova (a) é testemunha de uma proposição (A), ou então de que dois objetos de prova (a) e (b) são igual e ambos testemunham que (A) foi provado. O primeiro caso da segunda forma de julgamento afirma que uma proposição (A) é bem formada, e o segundo registra que duas proposições (A) e (B) são iguais.

Existe um conjunto cuidadoso e altamente detalhado de regras para formalizar o BC. Não abordaremos aqui, mas encaminhe o leitor a outras fontes, como Sambin & Smith [1998].

Ao fazer matemática construtiva na teoria dos tipos, muitas vezes é necessário equipar conjuntos (tipos) completamente apresentados com uma relação de equivalência, sendo a combinação conhecida como setoide. Os mapeamentos são funções que respeitam essas relações de equivalência. Isso está de acordo com a maneira como Bishop apresentou sua teoria informal dos conjuntos. Os tipos dependentes de Martin-Löf são úteis para construir subconjuntos. Por exemplo, os números reais podem ser construídos usando o tipo (Sigma) - (consulte Martin-Löf [1984]):

[(Sigma x / in / bN _ + / rightarrow / bQ) (Pi m / in / bN _ +) (Pi n / in / bN _ +) left (abs {x_ {m} - x_ {n }} le / left (frac {1} {m} + / frac {1} {n} right) right],)

Um elemento desse tipo (B) é, portanto, um par que consiste em uma sequência convergente (bx) de racionais e uma prova (p) de que é convergente. Uma relação de equivalência adequada ({ sim}) em (R) é definida assumindo ((x, p) sim (y, q)) como significando

(forall m / in / bN_ + / left (abs {x_ {m} - y_ {m}} le / frac {2} {m} right).)

O setoide resultante de números reais é (bR = (R, { sim})). Podemos provar prontamente que

(todo x / in / bR \, / existe n / em Z (n / lt x / lt n + 2))

e, usando o axioma de escolha teórico do tipo (consulte a Seção 4 abaixo), encontre uma função (f: / bR / rightarrow / bZ) tal que (f (x) lt x / lt f (x) +2). No entanto, não há razão para acreditar que a função (f) respeite as relações de equivalência - isto é, que (f (x) = f (y)) seja válida se (x / sim y).

Toda prova construtiva incorpora um algoritmo que, em princípio, pode ser extraído e reformulado como um programa de computador; além disso, a própria prova construtiva é uma verificação de que o algoritmo está correto - isto é, atende às suas especificações. Uma grande vantagem da abordagem formal de Martin-Löf à matemática construtiva é que ela facilita muito a extração de programas de provas. Isso levou a um trabalho sério sobre a implementação da matemática construtiva em vários locais (ver Martin-Löf [1980], Constable [1986], Hayashi & Nakano [1988], Schwichtenberg [2009]). Algumas implementações recentes da teoria de tipos para extração de provas são Coq e Agda (consulte os links em Outros recursos da Internet).

4. O axioma da escolha

O axioma completo da escolha pode ser indicado da seguinte forma:

Se (A, B) são conjuntos habitados e (S) um subconjunto de (A / vezes B) tal que

(todo x / em A \, / existe y / em B ((x, y) em S),)

existe uma função de escolha (f: A / rightarrow B) tal que

(forall x / in A ((x, f (x)) em S).)

Agora, se isso é válido sob uma interpretação construtiva, para um dado (x / in A), o valor (f (x)) da função de escolha dependerá não apenas de (x), mas também nos dados que provam que (x) pertence a (A.) Em geral, não podemos esperar produzir uma função de escolha desse tipo. No entanto, a interpretação BHK das hipóteses no axioma é que existe um algoritmo (mathcal {A}) que, aplicado a qualquer (x / in A), produz um elemento (y / em B) tal que ((x, y) em S). Se (A) é um conjunto completamente apresentado, para o qual nenhum trabalho além da construção de cada elemento do conjunto é necessário para provar que o elemento realmente pertence a (A), então podemos razoavelmente esperar que o algoritmo (mathcal {A}) é uma função de escolha. Na teoria de tipos de Martin-Löf, todo conjunto é completamente apresentado e,de acordo com a interpretação BHK, o axioma da escolha é derivável.

Por outro lado, na matemática do estilo bispo, conjuntos completamente apresentados ––– ou, em sua terminologia, conjuntos ––– básicos são raros, sendo um exemplo (bN); portanto, podemos esperar que o axioma da escolha não seja derivável. De fato, como foi mostrado por Diaconescu [1975] e Goodman & Myhill [1978], e prefigurado pelo próprio Bishop no Problema 2 na página 58 do bispo de 1967, o axioma da escolha implica a lei do meio excluído. Claramente, o teorema de Diaconescu-Goodman-Myhill se aplica apenas sob a suposição de que nem todo conjunto é apresentado completamente.

Os matemáticos construtivos que não trabalham em ML geralmente rejeitam o axioma completo da escolha, mas abraçam o axioma da escolha contável, no qual o domínio da escolha é (bN) e a escolha dependente. Mas alguns preferem trabalhar sem escolha contável, com o argumento de que falar de uma infinidade de opções sem estabelecer uma regra apresenta uma dificuldade que é tão grande quanto a infinidade ser ou não numerosa. Curiosamente, Lebesgue fez exatamente esse ponto em uma carta a Borel (ver Moore [2013], página 316):

Concordo totalmente com Hadamard quando ele afirma que falar de uma infinidade de opções sem dar uma regra apresenta uma dificuldade que é tão grande quanto a infinidade ser ou não numerável.

O efeito de abandonar mesmo as escolhas contáveis é a exclusão de muitos teoremas que, como estão, são provados usando argumentos sequenciais baseados em escolhas. Mas aqueles que advogam evitar a escolha argumentam que evitar a escolha obriga a formular melhor as coisas.

Um caso particular de interesse é o Teorema Fundamental da Álgebra: todo polinômio complexo tem pelo menos uma raiz no plano complexo. Richman [2000] mostrou que, sem escolha contável, embora possamos construir apenas raízes isoladas (possivelmente múltiplas), podemos construir aproximações arbitrariamente próximas do multiset de raízes. Essa abordagem concentra-se em encontrar uma fatoração linear aproximada do polinômio, em vez de encontrar aproximações separadas para cada uma de suas raízes.

Para uma análise mais aprofundada do axioma da escolha na teoria dos conjuntos e na teoria dos tipos, consulte Martin-Löf [2006] e as entradas do SEP sobre teoria das categorias, teoria dos tipos e teoria dos tipos intuicionista.

5. Matemática Reversa Construtiva

Na década de 1970, Harvey Friedman iniciou um programa de pesquisa em matemática reversa, com o objetivo de classificar os teoremas matemáticos de acordo com sua equivalência a um dentre um pequeno número de princípios da teoria dos conjuntos (Friedman, 1975). Essa classificação revela diferenças interessantes, às vezes notáveis, na complexidade teórica da prova. Por exemplo, embora o teorema de Ascoli-Arzelà seja usado na prova padrão do teorema da existência de Peano para soluções de equações diferenciais ordinárias (Hurewicz [1958], página 10), uma análise matemática reversa mostra que o primeiro é equivalente a um valor estritamente mais forte princípio da teoria dos conjuntos que o equivalente ao teorema de Peano (Simpson [1984], Teoremas 3.9 e 4.2). O tratado padrão sobre matemática reversa clássica é (Simpson [1999/2009]).

Por volta da virada deste século, Veldman (consulte Outros recursos da Internet), na Holanda, e Ishihara [2005, 2006], no Japão, iniciaram independentemente um programa de matemática reversa construtiva (CRM), baseado em intuições, em vez de clássicas, lógica. (Observe, porém, que o primeiro trabalho publicado na era moderna do CRM é provavelmente o de Julian e Richman [1984], que estavam vinte anos à frente de seu tempo.) Nesta seção do artigo, descrevemos uma abordagem menos formal ao CRM, no estilo e estrutura do BISH. O objetivo desse programa de CRM é classificar os teoremas nos três modelos padrão - CLASS, INT e RUSS - de acordo com os princípios que devemos e precisamos apenas adicionar ao BISH para prová-los.

Ressaltamos que nos restringimos aqui ao CRM informal, no qual tomamos como garantidos os princípios de construção de funções e conjuntos descritos nos primeiros capítulos de Bishop [1967] ou Bishop & Bridges [1985], e trabalhamos no setor informal, embora rigoroso, estilo do analista praticante, algebraista, topólogo,….

Na prática, o CRM se divide naturalmente em duas partes. No primeiro deles, consideramos um teorema (T) de INT ou RUSS e tentamos encontrar algum princípio, válido nesse modelo e diferente de (T), cuja adição ao BISH é necessária e suficiente para uma prova construtiva de (T). Na segunda parte do CRM, lidamos com um teorema (T) de CLASSE que suspeitamos não ser construtivo e tentamos provar que (T) é equivalente, em comparação com BISH, a um dentre um número conhecido de princípios não construtivos, como MP, LLPO, LPO ou LEM. Para um exemplo dessa parte do CRM, mencionamos nossa prova anterior de que o princípio clássico de limite mínimo implica e, portanto, é equivalente ao LEM.

Aliás, há um forte argumento de que Brouwer [1921] foi o primeiro a lidar com idéias matemáticas reversas: seus contra-exemplos brouwerianos (veja aquele que usa a conjectura de Goldbach, na Seção 1 acima) estão diretamente na segunda parte do CRM. Mesmo que Brouwer não tenha declarado esses exemplos como equivalências lógicas, mas como implicações do tipo

[P / Rightarrow / text {algum princípio não construtivo},)

é difícil acreditar que ele não sabia que o lado direito implicava a esquerda nesses casos.

5.1 Teoremas de fãs no CRM

Para ilustrar a primeira parte do CRM, agora nos concentramos em teoremas do tipo

(text {BISH} vdash / text {FT} _? / Leftrightarrow T,)

onde FT (_?) é alguma forma do teorema dos fãs de Brouwer e (T) é um teorema da INT. Para fazer isso, precisamos distinguir entre certos tipos de barra para o ventilador binário completo (2 ^ *) (o conjunto de todas as seqüências finitas em ({0,1 })).

Seja (alpha / equiv (alpha_1, / alpha_2, / ldots)) uma sequência binária finita ou infinita. A concatenação de (alpha) com outra string (beta) é

(alpha ^ { franzir as sobrancelhas} beta / equiv (alpha_1, / alpha_2, / ldots, / alpha_n, / beta_1, / ldots, / beta_m).)

Para (b) em ({0,1 }), escrevemos (alpha ^ { frown} b) em vez de (alpha ^ { frown} (b)). Por um (mathsf {c}) - subconjunto de (2 ^ *), queremos dizer um subconjunto (B) de (2 ^ *) tal que

(tag {1} B = {u / em 2 ^ *: / forall v / in 2 ^ * (u ^ { franzir as sobrancelhas} v / in D) })

para algum subconjunto destacável (D) de (2 ^ *). Todo subconjunto destacável de (2 ^ *) é um subconjunto (mathsf {c}). Por outro lado, por um subconjunto (Pi ^ {0} _1) de (2 ^ *), queremos dizer um subconjunto (B) de (2 ^ *) com a seguinte propriedade: existe um subconjunto destacável (S) de (2 ^ * / times / bN) tal que

(forall u / in 2 ^ * \, / forall n / in / bN \, ((u, n) in S / Rightarrow (u ^ { franzir as sobrancelhas} 0, n) in S / wedge (u ^ { franzir as sobrancelhas} 1, n) em S))

e

[B = {u / em 2 ^ *: / forall n / in / bN ((u, n) in S) }.)

Todo (mathsf {c}) - subconjunto (B) de (2 ^ *) é um (Pi ^ {0} _1) - subconjunto: basta pegar (S = D / times / bN), onde (D) é um subconjunto destacável de (2 ^ *) tal que (1) é válido.

Se (?) Denota uma propriedade dos subconjuntos de (2 ^ *), o teorema do ventilador de Brouwer para (?) - bars nos diz que toda barra com a propriedade (?) É uma barra uniforme. Estamos particularmente interessados no teorema do ventilador para barras destacáveis (já discutido na Seção 3.1):

FT (_ D): Cada barra destacável do ventilador binário completo é uniforme;

o teorema do ventilador para (mathsf {c}) - barras (ou seja, barras que são (mathsf {c}) - subconjuntos):

FT (_ { mathsf {c}}): Cada barra c do ventilador binário completo é uniforme;

o teorema do ventilador para (Pi ^ {0} _1) - barras (ou seja, barras que são (Pi ^ {0} _1) - subconjuntos):

FT (_ { Pi ^ {0} _1}): Cada (Pi ^ {0} _1) - a barra do ventilador binário completo é uniforme;

e o teorema do ventilador completo:

FT: Cada barra do ventilador binário completo é uniforme.

Observe que, em relação a BISH, FT (Rightarrow) FT (_ { Pi ^ {0} _1} Rightarrow) FT (_ c / Rightarrow) FT (_ D).

Lubarsky e Diener [2014] mostraram que essas implicações são estritas.

Normalmente, queremos provar que FT (_?) É equivalente, acima de BISH, à proposição de que, para cada conjunto (S) de um tipo apropriado, alguma propriedade pontual da forma

(tag {2} forall x / in S / existe t / em TP (s, t))

realmente se mantém uniformemente na forma

(tag {3} existe t / em T / forall s / em SP (s, t).)

Nossa estratégia para atacar esse problema é dupla. Primeiro, dado um conjunto (S) do tipo apropriado, construímos um? -Subset (N) de (2 ^ *) tal que

  • se (2) reter, então (B) será uma barra e
  • se (B) é uma barra uniforme, (3) é válido.

Isso, porém, é apenas metade da solução. Para provar que a implicação de (3) a (2) implica FT (_?), Consideramos um sub-conjunto? (B) de (2 ^ *) e construímos um conjunto correspondente (S) de tal modo que

  • se (B) é uma barra, (2) mantém e
  • se (3) valer, então (B) é uma barra uniforme.

O exemplo canônico de tais resultados é o de Julian e Richman [1984], no qual (S) é o conjunto de valores de um determinado mapeamento uniformemente contínuo (f: [0,1] rightarrow / bR, T) é o conjunto de números reais positivos e

[P (s, t) equiv (s / ge t).)

A propriedade pontual que consideramos é

(forall x / in [0,1] existe t / gt 0 (f (x) ge t),)

sendo sua versão uniforme

(existe t / gt 0 / forall x / in [0,1] (f (x) ge t).)

Os resultados de Julian-Richman são os seguintes.

Teorema 1: Seja (f: [0,1] rightarrow / bR) seja uniformemente contínuo. Existe um subconjunto destacável (B) de (2 ^ *) tal que

  • se (f (x) gt 0) para cada (x / in [0,1]), então (B) é uma barra e
  • se (B) for uma barra uniforme, (inf f / gt 0).

Teorema 2: Seja (B) um subconjunto destacável de (2 ^ *). Então existe um / uniformemente contínuo (f: [0,1] rightarrow / bR) tal que

  • se (B) for uma barra, então (f (x) gt 0) para cada (x / in [0,1]), e
  • se inf (f / gt 0), então (B) é uma barra uniforme.

As provas desses dois teoremas são sutis e complicadas; ver Julian e Richman [1984].

Os dois teoremas de Julian-Richman juntos revelam que, em relação ao BISH, o teorema do ventilador FT (_ D) é equivalente ao princípio da positividade, POS:

Cada função uniformemente contínua e com valor positivo em ([0,1]) tem um mínimo positivo.

Segue-se que o POS é derivável em INT, no qual o teorema completo do ventilador, não apenas FT (_ D), é um princípio padrão. A situação é silenciosa ao contrário em RUSS, onde existe uma barra destacável de (2 ^ *) que não é uniforme e uma função uniformemente contínua e com valor positivo em ([0,1]) que possui igual a 0; veja os capítulos 5 e 6 de Bridges & Richman [1987].

Berger e Ishihara [2005] adotaram uma rota diferente e indireta para estabelecer a equivalência de POS e FT (_ c). Eles estabelecem uma cadeia de equivalências entre POS, FT (_ c) e quatro princípios do tipo “se houver no máximo um objeto com propriedade (P), então existe um objeto”. Os quatro princípios de existência única são:

CIN!: Cada sequência descendente de subconjuntos localizados fechados habitados de um espaço métrico compacto com, no máximo, um ponto comum habitou a interseção (teorema da interseção de Cantor com exclusividade.) Observe que um subconjunto (S) de um espaço métrico ((X, / rho)) está localizado se, para cada (x) em (X), existir a menor distância entre (x) e (S).

MIN!: Cada função uniformemente contínua e com valor real em um espaço métrico compacto com no máximo um ponto mínimo possui um ponto mínimo.

WKL! Cada árvore infinita com no máximo um galho infinito possui um galho infinito (o fraco lema de König com exclusividade).

CONSERTAR!: Cada função uniformemente contínua de um espaço métrico compacto para si mesma com no máximo um ponto fixo e com pontos fixos aproximados possui um ponto fixo.

Por exemplo, no último deles, dizemos que um mapa (f) de um espaço métrico ((X, / varrho)) em si

  • tem no máximo um ponto fixo se (varrho (f (x), x) + / varrho (f (y), y) gt 0) sempre que (varrho (x, y) gt 0);
  • possui pontos fixos aproximados se para cada (varepsilon / gt 0) existir (x / em X) tal que (varrho (f (x), x) lt / varepsilon).

Um grande problema em aberto no CRM é o de encontrar uma forma do teorema do ventilador equivalente, acima do BISH, ao teorema da continuidade uniforme para ([0,1]), UCT (_ {[0,1]}): Todo mapeamento contínuo ponto a ponto de ([0,1]) em (bR) é uniformemente contínuo, a proposição para a qual Brouwer originalmente desenvolveu sua prova do teorema dos fãs. (Observe que UCT (_ {[0,1]}) é equivalente, em relação a BISH, ao teorema geral de continuidade uniforme para espaços métricos: Todo mapeamento contínuo pontual de um espaço métrico completo e totalmente delimitado para um espaço métrico é uniformemente contínuo (veja, por exemplo, Loeb [2005].)

Resulta dos resultados de Berger [2006] que

BISH (vdash) UCT (_ {[0,1]} Rightarrow) FT (_ c).

Diener e Loeb (2008) também demonstraram que

BISH (vdash) FT (_ { Pi ^ {0} _1} Rightarrow) UCT (_ {[0,1]}).

No entanto, não sabemos se uma dessas implicações pode ser substituída por uma bi-implicação. Talvez UCT (_ {[0,1]}) e, portanto, o teorema da continuidade uniforme para espaços métricos compactos, seja equivalente, em relação ao BISH, a uma versão natural, mas ainda não identificada, do teorema do ventilador.

Para material adicional sobre o teorema do ventilador em matemática reversa construtiva, veja, por exemplo, Berger & Bridges [2007]; Diener [2008, 2012]; Diener e Loeb [2009]; e Diener e Lubarsky [2014]. Em Dent [2013], há um diagrama claro, embora complexo, ilustrando as interconexões entre os teoremas dos ventiladores, a continuidade e os princípios de onisciência (consulte Outros recursos da Internet).

Os leitores interessados podem seguir o tópico da matemática reversa construtiva em mais detalhes no seguinte documento suplementar:

Princípio de Ishihara (BDN) e a propriedade anti-Specker

6. Álgebra Construtiva e Topologia

Os matemáticos construtivos tendem a concentrar seus esforços no campo da análise, com considerável testemunho de sucesso da riqueza da análise funcional desenvolvida em Bishop [1967]. Isso não significa que, por exemplo, a álgebra tenha sido excluída do empreendimento construtivo: o material da monografia de Mines et al [1986] pode ser considerado como uma contrapartida algébrica substancial da análise construtiva realizada por Bishop. Muito mais recentemente, Lombardi e Quitté [2011] publicaram o primeiro grande volume de um trabalho de dois volumes proposto sobre álgebra construtiva. No entanto, não sendo especialista em álgebra e ciente do perigo de tornar este artigo muito longo para prender a atenção do leitor, optamos por não discutir análises construtivas ou álgebra em detalhes; em vez disso, no seguinte documento complementar,nos voltamos para a topologia construtiva, descrevendo algumas abordagens bastante diferentes para esse assunto:

Abordagens à topologia construtiva

7. Economia e Finanças Matemáticas Construtivas

As investigações em economia matemática construtiva remontam a uma série de artigos sobre preferência, utilidade e demanda a partir de 1982; veja Bridges [1999]. Em sua tese de doutorado, Hendtlass [2013] enfraqueceu substancialmente as condições para a existência de uma função de demanda; ele também produziu uma riqueza de resultados na teoria do ponto fixo e suas aplicações, em particular nas construtivações de duas provas clássicas da existência de um equilíbrio econômico.

Em 2015, Berger e Svindland iniciaram um projeto de pesquisa em finanças matemáticas construtivas, na Ludwig-Maximilians-Universität em Munique, mostrando pela primeira vez que o teorema fundamental da precificação de ativos, o teorema do hiperplano separador e o princípio de Markov são construtivamente equivalentes (Berger & Svindland [2016]). Seu trabalho mais recente concentrou-se em como contornar a não-construtividade do teorema clássico do valor extremo, a fim de provar a existência de pontos extremos para funções na presença de propriedades de convexidade ainda relativamente fracas (Berger & Svindland [2016a]). Seu projeto sugere que as finanças matemáticas, como a economia matemática, podem ser uma fonte rica de teoremas construtivos elegantes e práticos.

8. Observações finais

O caminho tradicional adotado pelos matemáticos que desejam analisar o conteúdo construtivo da matemática é o que segue a lógica clássica; a fim de evitar decisões, como se um número real é igual a 0, que não pode ser feito por um computador real, o matemático deve então manter-se dentro de limites algorítmicos estritos, como os formados pela teoria da função recursiva. Por outro lado, o caminho adotado pelo matemático construtivo segue a lógica intuicionista, que cuida automaticamente de decisões computacionalmente inadmissíveis. Essa lógica (juntamente com uma estrutura teórica de conjunto ou de tipo) é suficiente para manter a matemática dentro de limites construtivos. Assim, o matemático é livre para trabalhar no estilo natural de um analista, algebraista (por exemplo, Mines et al. [1988]), geômetro, topólogo (por exemplo, Bridges &Vîță [2011], Sambin no prelo) ou outro matemático normal, as únicas restrições são as impostas pela lógica intuicionista. Como Bishop e outros demonstraram, a crença tradicional promulgada por Hilbert e ainda hoje amplamente difundida, de que a lógica intuicionista impõe restrições que impossibilitam o desenvolvimento de matemática séria é claramente falsa: grandes partes da matemática moderna profunda podem ser e têm produzido por métodos puramente construtivos. Além disso, o vínculo entre matemática construtiva e programação é uma grande promessa para a futura implementação e desenvolvimento da matemática abstrata no computador.a crença tradicional promulgada por Hilbert e ainda hoje amplamente difundida, de que a lógica intuicionista impõe restrições que impossibilitem o desenvolvimento de matemática séria é claramente falsa: grandes partes da matemática moderna profunda podem ser e foram produzidas por métodos puramente construtivos. Além disso, o vínculo entre matemática construtiva e programação é uma grande promessa para a futura implementação e desenvolvimento da matemática abstrata no computador.a crença tradicional promulgada por Hilbert e ainda hoje amplamente difundida, de que a lógica intuicionista impõe restrições que impossibilitem o desenvolvimento de matemática séria é claramente falsa: grandes partes da matemática moderna profunda podem ser e foram produzidas por métodos puramente construtivos. Além disso, o vínculo entre matemática construtiva e programação é uma grande promessa para a futura implementação e desenvolvimento da matemática abstrata no computador.o vínculo entre matemática construtiva e programação é uma grande promessa para a futura implementação e desenvolvimento da matemática abstrata no computador.o vínculo entre matemática construtiva e programação é uma grande promessa para a futura implementação e desenvolvimento da matemática abstrata no computador.

Bibliografia

Referências

  • Aberth, O., 1980, Computable Analysis, Nova Iorque: McGraw-Hill.
  • –––, 2001, Computable Calculus, Nova York: Academic Press.
  • Aczel, P. e Rathjen, M., 2001, Notas sobre a teoria dos conjuntos construtivos (Relatório nº 40), Estocolmo: Institut Mittag-Leffler, Academia Real Sueca de Ciências.
  • Bauer, A., 2005, “Realizabilidade como a conexão entre a matemática computacional e a construtiva”, notas da palestra para um tutorial em um seminário satélite do CCA2005, Kyoto, Japão [disponível on-line].
  • Beeson, M., 1985, Fundamentos da Matemática Construtiva, Heidelberg: Springer Verlag.
  • Berger, J., 2006, "A força lógica do teorema da continuidade uniforme", em Abordagens Lógicas às Barreiras Computacionais, A. Beckmann, U. Berger, B. Löwe e JV Tucker (eds.), Heidelberg: Springer Verlag.
  • Berger, J. e Bridges, DS, 2007, “Um equivalente teórico dos fãs da antítese do teorema de Specker”, Proceedings of Royal Dutch Mathematics Society (Indagationes Mathematicae) (Indag. Math. NS), 18 (2): 195 –202
  • –––, 2009, “O teorema do ventilador e funções uniformemente contínuas com valor positivo em intervalos compactos”, New Zealand Journal of Mathematics, 38: 129–135.
  • Berger, J. e Ishihara, H., 2005, "Teorema dos fãs de Brouwer e existência única na análise construtiva", Mathematics Logic Quarterly, 51 (4): 360–364.
  • Berger, J. e Schuster, PM, 2006, "Classifying Dini's Teorema", Notre Dame Journal of Formal Logic, 47: 253–262.
  • Berger, J. e Svindland, G., 2016, “Um teorema do hiperplano de separação, o teorema fundamental da precificação de ativos e o princípio de Markov”, Annals of Pure and Applic Logic, 167, 1161-1170.
  • –––, 2016a, “Convexidade e informações construtivas”, Archive for Mathematics Logic, 55: 873–881
  • Bishop, E., 1967, Fundamentos da Análise Construtiva, Nova York: McGraw-Hill.
  • –––, 1973, Esquizofrenia em Matemática Contemporânea (Palestras do Colóquio da Sociedade Americana de Matemática), Missoula: University of Montana; reimpresso em Errett Bishop: reflexões sobre ele e sua pesquisa, American Mathematical Society Memoirs 39.
  • Bishop, E. e Bridges, D., 1985, Constructive Analysis, (Grundlehren der mathematischen Wissenschaften, 279), Heidelberg: Springer Verlag.
  • Bourbaki, N., 1984, Elementos de História da Matemática, Paris: Masson; Edição em língua inglesa, Elements of the History of Mathematics, J. Meldrum (trad.), 2006, Berlin: Springer Verlag.
  • Bridges, DS, 1999, “Métodos construtivos em economia matemática”, em Zeitschrift für Nationalökonomie (Supplement), 8: 1–21.
  • Bridges, DS, e Diener, H., 2007, “O pseudocompacto de [0, 1] é equivalente ao teorema da continuidade uniforme”, Journal of Symbolic Logic, 72 (4): 1379–1383.
  • Bridges, DS, e Richman, F., 1987, Variedades de Matemática Construtiva, London Mathematical Society Lecture Notes 97, Cambridge: Cambridge University Press.
  • Pontes, DS e Vîță, LS, 2006, Técnicas de Análise Construtiva, Heidelberg: Springer Verlag.
  • –––, 2011, Apartness and Uniformity-A Development Development, Heidelberg: Springer Verlag
  • Brouwer, LEJ, 1907, Over de Grondslagen der Wiskunde, Tese de Doutorado, Universidade de Amsterdã; reimpresso com material adicional, D. van Dalen (ed.), por Matematisch Centrum, Amsterdã, 1981.
  • –––, 1908, “De onbetrouwbaarheid der logische principes”, Tijdschrift voor Wijsbegeerte, 2: 152-158.
  • –––, 1921, “Besitzt jede reelle Zahl eine Dezimalbruchentwicklung?”, Mathematische Annalen, 83: 201-210.
  • –––, 1924, “Beweis, dass jede volle Funktion gleichmässig stetig ist”, Proceedings of Royal Dutch Mathematics Society, 27: 189–193.
  • –––, 1924A, “Bemerkung zum Beweise der gleichmässigen Stetigkeit voller Funktionen”, Proceedings of Royal Dutch Mathematics Society, 27: 644-646.
  • Cederquist, J. e Negri, S., 1996, “Uma prova construtiva do teorema da cobertura de Heine-Borel para reais formais”, em Tipos para provas e programas (Notas de aula em Ciência da computação, volume 1158), 62–75, Berlim: Springer Verlag.
  • Constable, R., et al., 1986, Implementing Mathematics with Nuprl Proof Development System, Englewood Cliffs, NJ: Prentice-Hall.
  • Coquand, T., 1992, "Uma prova intuicionista do teorema de Tychonoff", Journal of Symbolic Logic, 57: 28–32.
  • –––, 2009, “Space of valuations”, Annals of Pure and Applic Logic, 157: 97-109.
  • –––, 2016, “Type Theory”, Stanford Encyclopedia of Philosophy (edição de inverno 2016), Edward N. Zalta (ed.), URL (= / lt) https://plato.stanford.edu/entries/ teoria dos tipos / (gt)
  • Coquand, T. e Spitters, B., 2009, “Integrais e avaliações”, Journal of Logic and Analysis, 1 (3): 1–22.
  • Coquand, T., Sambin, G., Smith, J. e Valentini, S., 2003, “Topologias formais geradas indutivamente”, Annals of Pure and Applic Logic, 124: 71-106.
  • Curi, G., 2010, “Sobre a existência da compactação de Stone-Čech”, Journal of Symbolic Logic, 75: 1137-1146.
  • Dent, JE, 2013, Propriedades Anti-Specker em Matemática Reversa Construtiva, Ph. D. tese, Universidade de Canterbury, Christchurch, Nova Zelândia.
  • Diaconescu, R., 1975, “Axioma da escolha e complementação”, Proceedings of the American Mathematics Society, 51: 176–178
  • Diener, H., 2008, Compacidade sob escrutínio construtivo, Ph. D. tese, Christchurch, Nova Zelândia: University of Canterbury.
  • –––, 2008a, “Generalizing compactness”, Mathematics Logic Quarterly, 51 (1): 49–57.
  • –––, 2012, “Reclassificando a antítese do teorema de Specker”, Archive for Mathematics Logic, 51: 687–693.
  • Diener, H. e Loeb, I., 2009, “Sequências de Funções Reais em [0, 1] em Matemática Reversa Construtiva”, Annals of Pure and Applic Logic, 157 (1): 50–61.
  • Diener, H. e Lubarsky, R., 2013, “Separando o Teorema do Ventilador e seus Pontos Fracos”, em Fundamentos Lógicos da Ciência da Computação (Lecture Notes in Computer Science, 7734), S. Artemov e A. Nerode (eds.), Berlim: Springer Verlag.
  • Dummett, Michael, 1977 [2000], Elements of Intuitionism (Oxford Logic Guides, 39), Oxford: Clarendon Press, 1977; 2ª edição, 2000. [As referências das páginas são para a 2ª edição.]
  • Ewald, W., 1996, De Kant a Hilbert: Um Livro Fonte nos Fundamentos da Matemática (Volume 2), Oxford: Clarendon Press.
  • Feferman, S, 1975, “Uma linguagem e axiomas para a matemática explícita”, em Álgebra e Logit, JN Crossley (ed.), Heidelberg: Springer Verlag, pp. 87–139.
  • –––, 1979, “Teorias construtivas de funções e classes”, no Logic Colloquium '78, M. Boffa, D. van Dalen e K. McAloon (eds.), Amsterdã: North Holland, pp. 159–224.
  • Friedman, H., 1975, “Alguns sistemas de aritmética de segunda ordem e seu uso”, em Anais do 17º Congresso Internacional de Matemáticos, Vancouver, BC, 1974.
  • –––, 1977, “Estabelecer fundamentos teóricos para análise construtiva”, Annals of Mathematics, 105 (1): 1–28.
  • Goodman, ND, e Myhill, J., 1978, “Choice Implies Excluded Middle”, Zeitschrift für Logik e Grundlagen der Mathematik, 24: 461.
  • Hayashi, S. e Nakano, H., 1988, PX: A Computational Logic, Cambridge MA: MIT Press.
  • Hendtlass, M., 2013, Construindo pontos fixos e equilíbrios econômicos, Ph. D. tese, Universidade de Leeds.
  • Heyting, A., 1930, “Die formalen Regeln der intuitionistischen Logik”, Sitzungsberichte der Preussische Akadademie der Wissenschaften. Berlim, 42-56.
  • –––, 1971, Intuitionism-an Introduction, 3a edição, Amsterdã: Holanda do Norte.
  • Hilbert, D., 1925, "Über das Unendliche", Mathematische Annalen, 95: 161–190; tradução, “On the Infinite”, de E. Putnam e G. Massey, em Filosofia da Matemática: Leituras Selecionadas, P. Benacerraf e H. Putnam (eds.), Englewood Cliffs, NJ: Prentice Hall, 1964, 134–151.
  • Hurewicz, W., 1958, Palestras sobre Equações Diferenciais Ordinárias, Cambridge, MA: MIT Press.
  • Ishihara, H., 1992, "Propriedades de continuidade em matemática construtiva", Journal of Symbolic Logic, 57 (2): 557-565.
  • –––, 1994, “Uma versão construtiva do teorema do mapeamento inverso de Banach”, New Zealand Journal of Mathematics, 23: 71–75.
  • –––, 2005, “Matemática Reversa Construtiva: propriedades de compactação”, de De Conjuntos e Tipos a Análise e Topologia: Em direção a Fundamentos Práticos para Matemática Construtiva, L. Crosilla e P. Schuster (eds.), Oxford: The Clarendon Press.
  • –––, 2006, “Matemática reversa na matemática construtiva de Bishop”, Philosophia Scientiae (Cahier Special), 6: 43–59.
  • –––, 2013, “Relacionando os Espaços Funcionais de Bishop aos Espaços da Vizinhança”, Annals of Pure and Applic Logic, 164: 482-490.
  • Johnstone, PT, 1982, Stone Spaces, Cambridge: Cambridge University Press.
  • –––, 2003, “O ponto da topologia sem sentido”, Boletim da Sociedade Americana de Matemática, 8: 41–53.
  • Joyal, A. e Tierney, M., 1984, "Uma extensão da teoria de Galois de Grothendieck", Memórias da Sociedade Americana de Matemática, 309: 85 pp.
  • Julian, WH e Richman, F., 1984, “Uma função uniformemente contínua em [0, 1] que é em toda parte diferente do seu mínimo”, Pacific Journal of Mathematics, 111: 333–340.
  • Kushner, B., 1985, Palestras sobre Análise Matemática Construtiva, Providence, RI: Sociedade Americana de Matemática
  • Lietz, P., 2004, Da Matemática Construtiva à Análise Computável via Interpretação da Realizabilidade, Dr. rer. nat. dissertação, Universität Darmstadt, Alemanha.
  • Lietz, P. e Streicher, T., "Modelos de realização que refutam o princípio da limitação de Ishihara", Annals of Pure and Applic Logic, 163 (12): 1803–1807.
  • Loeb, I., 2005, “Equivalentes do Teorema do Ventilador (Fraco)”, Annals of Pure and Applic Logic, 132: 51–66.
  • Lombardi, H., Quitté, C., 2011, Algèbre Commutative. Méthodes constructives, Nanterre, França: Calvage et Mounet.
  • Lorenzen, P., 1955, Einführung in the operative Logik und Mathematik (Grundlehren der mathematischen Wissenschaften, volume 78), 2ª edição, 1969, Heidelberg: Springer.
  • Lubarsky, R. e Diener, H., 2014, “Separando o Teorema dos Ventiladores e Seus Enfraquecimentos”, Journal of Symbolic Logic, 79 (3): 792–813.
  • Markov, AA, 1954, Teoria dos algoritmos, Trudy Mat. Istituta imeni VA Steklova, 42, Moscou: Izdatel'stvo Akademii Nauk SSSR.
  • Marquis, J.-P., “Category Theory”, The Stanford Encyclopedia of Philosophy (edição de inverno 2015), Edward N. Zalta (ed.), URL (= / lt) https://plato.stanford.edu / archives / win2015 / entradas / teoria da categoria / (gt).
  • Martin-Löf, P., 1968, Notas sobre Análise Construtiva, Estocolmo: Almquist & Wiksell.
  • –––, 1975, “Uma teoria intuicionista dos tipos: parte predicativa”, no Logic Colloquium 1973, HE Rose e JC Shepherdson (eds.), Amsterdã: Holanda do Norte.
  • –––, 1980, “Matemática construtiva e programação de computadores”, em Proc. 6o. Int. Congresso de Lógica, Metodologia e Filosofia da Ciência, L. Jonathan Cohen (ed.), Amsterdã: Holanda do Norte.
  • –––, 1984, Intuitionistic Type Theory, Notas de Giovanni Sambin sobre uma série de palestras proferidas em Padova, junho de 1980, Nápoles: Bibliopolis.
  • –––, 2006, “100 anos do axioma de escolha de Zermelo: qual era o problema?”, The Computer Journal, 49 (3): 345–350.
  • Menger, K., 1940, "Topologia sem pontos", Rice Institute Pamphlet, 27 (1): 80-107 [disponível on-line].
  • Mines, R., Richman, F., e Ruitenburg, W., 1988, Um Curso em Álgebra Construtiva, Universitext, Heidelberg: Springer Verlag.
  • Moerdijk, I., 1984, “Heine-Borel não implica o teorema do ventilador”, Journal of Symbolic Logic, 49 (2): 514-519.
  • Moore, GH, 2013, Axioma da escolha de Zermelo: suas origens, desenvolvimento e influência, Nova York: Dover.
  • Myhill, J., 1973, “Algumas propriedades da teoria dos conjuntos intuicionistas de Zermelo-Fraenkel”, na Cambridge Summer School em Mathematics Logic, A. Mathias e H. Rogers (eds.), Lecture Notes in Mathematics, 337, Heidelberg: Springer Verlag 206-231.
  • –––, 1975, “Constructive Set Theory”, Journal of Symbolic Logic, 40 (3): 347–382.
  • Naimpally, S., 2009, Abordagem de Proximidade de Problemas em Topologia e Análise, Munique: Oldenbourg Verlag.
  • Naimpally, S. e Warrack, BD, 1970, Proximity Spaces (Cambridge Tracts in Math. And Math. Phys., Volume 59), Cambridge: Cambridge University Press.
  • Nordström, B., Peterson, K. e Smith, JM, 1990, “Programming in Martin-Löf's Type Theory”, Oxford: Oxford University Press.
  • Palmgren, E., 2007, “Uma incorporação construtiva e funcional de espaços métricos localmente compactos em locais”, Topology and its Applications, 154: 1854–1880.
  • –––, 2008, “Resolução do problema uniforme dos limites inferiores na análise construtiva”, Mathematics Logic Quarterly, 54: 65–69.
  • –––, 2009, “Da topologia intuicionista à formal: algumas observações sobre os fundamentos da teoria da homotopia”, em: Logicismo, Intuicionismo e Formalismo - o que aconteceu com eles? S. Lindström, E. Palmgren, K. Segerberg e V. Stoltenberg-Hansen (orgs.), 237–253, Berlim: Springer Verlag.
  • Petrakis, I., 2016, “Uma abordagem teórica da função construtiva para compacidade topológica”, em Métodos Lógicos em Ciência da Computação 2016, Publicações da IEEE Computer Society: 605-614.
  • –––, 2016a, “The Theryem Urysohn Extension for Bishop Spaces”, em S. Artemov e A. Nerode (eds.), Simpósio sobre fundamentos lógicos em ciência da computação 2016 (notas de aula em ciência da computação 9537), Berlim: Springer Verlag 299-316.
  • Picado, J. e Pultr, A., 2011, Frames e Locales: Topologia sem Pontos, Basileia: Birkhäuser Verlag.
  • Richman, F., 1983, "Tese da Igreja Sem Lágrimas", Journal of Symbolic Logic, 48: 797-803.
  • –––, 1990, “Intuicionismo como generalização”, Philosophia Mathematica, 5: 124–128.
  • –––, 1996, “Entrevista com um matemático construtivo”, Modern Logic, 6: 247–271.
  • –––, 2000, “O Teorema Fundamental da Álgebra: Um Tratamento Construtivo Sem Escolha”, Pacific Journal of Mathematics, 196: 213-230.
  • Riesz, F., 1908, “Stetigkeitsbegriff und abstrakte Mengenlehre”, Atti IV Congresso Internacional de Matematica Roma II, 18–24.
  • Sambin, G., 1987, “Espaços formais intuicionistas - uma primeira comunicação”, em Lógica Matemática e suas Aplicações, D. Skordev (ed.), 187–204, Nova York: Plenum Press.
  • –––, a seguir, O Quadro Básico: Estruturas para Topologia Construtiva, Oxford: Oxford University Press.
  • Sambin, G. e Smith, J. (orgs.), 1998, Twenty Five Years of Constructive Type Theory, Oxford: Clarendon Press.
  • Schuster, PM, 2005, “O que é continuidade, construtivamente?”, Journal of Universal Computer Science, 11: 2076–2085
  • –––, 2006, “Topologia formal de Zariski: positividade e pontos”, Annals of Pure and Applic Logic, 137: 317–359.
  • Schwichtenberg, H., 2009, “Extração de programas em análise construtiva”, em Logicismo, Intuicionismo e Formalismo - o que aconteceu com eles? S. Lindström, E. Palmgren, K. Segerberg e V. Stoltenberg-Hansen (orgs.), Berlim: Springer Verlag, 255-275.
  • Simpson, SG, 1984, “Quais axiomas de existência definidos são necessários para provar o teorema de Cauchy / Peano para equações diferenciais ordinárias”, Journal of Symbolic Logic, 49 (3): 783–802.
  • –––, 2009, Subsistemas de Aritmética de Segunda Ordem, segunda edição, Cambridge: Cambridge University Press.
  • Specker, E., 1949, "Nicht konstruktiv beweisbare Sätze der Analysis", Journal of Symbolic Logic, 14: 145-158.
  • Steinke, TA, 2011, Noções Construtivas de Compacidade em Espaços de Apartness, M. Sc. Tese, Universidade de Canterbury, Christchurch, Nova Zelândia.
  • Troelstra, AS, 1978, "Aspectos da Matemática Construtiva", no Handbook of Mathematics Logic, J. Barwise (ed.), Amsterdã: Holanda do Norte.
  • Troelstra, AS e van Dalen, D., 1988, Construtivismo em Matemática: Uma Introdução (dois volumes), Amsterdã: Holanda do Norte.
  • van Atten, M., 2004, em Brouwer, Belmont: Wadsworth / Thomson Learning.
  • van Dalen, D., 1981, Brouwer Cambridge Lectures on Intuitionism, Cambridge: Cambridge University Press.
  • –––, 1999, Mystic, Geometer and Intuitionist: The Life of LEJ Brouwer (Volume 1), Oxford: Clarendon Press.
  • –––, 2005, Mystic, Geometer e Intuitionist: A Vida de LEJ Brouwer (Volume 2), Oxford: Clarendon Press.
  • van Stigt, WP, 1990, Intuitionism de Brouwer, Amsterdã: Holanda do Norte.
  • Vickers, S., 2005, “Conclusão local de espaços métricos generalizados I”, Theory and Applications of Categories, 14 (15): 328–356.
  • Waaldijk, F., 2005, Sobre os fundamentos da matemática construtiva, Foundations of Science, 10 (3): 249–324.
  • Wallman, H., 1938, “Malhas de espaços topológicos”, Annals of Mathematics, 39: 112–126.
  • Weihrauch, K., 2000, Análise Computável (Textos EATCS em Ciência da Computação Teórica), Heidelberg: Springer Verlag.
  • Weyl, H., 1946, "Matemática e lógica", American Mathematics Monthly, 53 (1): 2–13.
  • Whitehead, AN, 1919, Inquérito sobre os princípios do conhecimento natural, Cambridge: Cambridge University Press, segunda edição, 1925.

Literatura relacionada

  • Heijenoort, Jean van, 1967, De Frege a Gödel: Um Livro Fonte em Lógica Matemática 1879–1931, Cambridge, MA: Harvard University Press.
  • Hilbert, David, 1928, “Die Grundlagen der Mathematik”, Hamburger Mathematische Einzelschriften 5, Teubner, Leipzig. Reimpresso na tradução para o inglês em van Heijenoort 1967.

Ferramentas Acadêmicas

ícone de homem de sep
ícone de homem de sep
Como citar esta entrada.
ícone de homem de sep
ícone de homem de sep
Visualize a versão em PDF desta entrada nos Amigos da Sociedade SEP.
ícone inpho
ícone inpho
Consulte este tópico de entrada no Internet Philosophy Ontology Project (InPhO).
ícone de papéis phil
ícone de papéis phil
Bibliografia aprimorada para esta entrada na PhilPapers, com links para o banco de dados.

Outros recursos da Internet

  • O Agda Wiki, uma linguagem de programação funcional digitada e assistente de prova, Universidade de Gotemburgo e Universidade de Tecnologia de Chalmers.
  • Agda, entrada na Wikipedia.
  • O Coq Proof Assistant, Inria, 1984-2017.
  • Coq, entrada na Wikipedia.
  • Diagrama de James Dent.
  • Aczel, P. e Rathjen, M., 2018, Teoria dos Conjuntos Construtivos, PDF online.
  • Bauer, A., 2005, "Realizabilidade como a conexão entre matemática computável e construtiva".
  • Veldman, W., 2014, “Teorema dos fãs de Brouwer como axioma e como contraste com a alternativa de Kleene”, arxiv: 1106.2738https://arxiv.org/abs/1106.2738.

Recomendado: