Predicados recursivos primitivos para exponenciação e multiplicação
Eu tenho as seguintes crenças declaradas informalmente e fracamente sustentadas, algumas das quais parecem inconsistentes para mim após uma reflexão mais aprofundada. Estou me perguntando onde pode estar a fonte do(s) erro(s) em meu pensamento; erros em definições básicas são uma possibilidade definitiva.
É impossível fazer a eliminação do quantificador na teoria de primeira ordem dos inteiros com adição e multiplicação. (Até onde posso dizer, essa é uma versão um pouco mais forte do primeiro teorema da incompletude.)
Na teoria de primeira ordem dos inteiros com adição e multiplicação, é possível definir um predicado recursivo primitivo para exponenciação. (Por predicado para exponenciação, quero dizer apenas algo que se comporta como "$Fabc\text{ just when }a^b = c.$")
É possível fazer a eliminação do quantificador na teoria de primeira ordem dos inteiros com duas operações$a \oplus b = \min(a, b)$e$a \otimes b = a + b$(ou seja, adição ordinária de números inteiros). Estou ciente de que também precisamos de predicados de divisibilidade e operadores de multiplicação para que os primos realmente façam a eliminação do quantificador.
Na teoria de primeira ordem dos inteiros com as operações$\oplus$e$\otimes$, é possível definir um predicado recursivo primitivo para multiplicação (quase exatamente da mesma maneira que o predicado para exponenciação acima).
Grosso modo, parece que há uma quebra na analogia entre a "torre de operações comum"$(+, \times, \hat{\phantom{n}}, \cdots)$e a "torre tropical de operações"$(\min, +, \times, \cdots)$.
Mais especificamente, se (4) e (3) forem verdadeiros, não entendo por que não se pode simplesmente usar livremente o predicado de multiplicação e, em seguida, ter uma situação em que podemos fazer a eliminação do quantificador (via (3)) e não fazer eliminação do quantificador (através de (1)). Eu ficaria muito surpreso se (2) fosse verdadeiro, mas (4) não fosse, e me surpreenderia ainda mais se (2) fosse falso.
Suspeito que não estou entendendo bem o que significa um predicado de exponenciação (ou seja, minha definição informal de$Fabc$está incorreto, ou então há mais alguns detalhes sobre "usar livremente o predicado de multiplicação" que eu não conheço.
Respostas
Suas reivindicações$(1), (2)$, e$(3)$estão corretos. Alegar$(4)$, no entanto, está incorreto ; de fato, se a multiplicação fosse definível em$(\mathbb{N};\max,+)$então a teoria$Th(\mathbb{N};\max,+)$seria tão complicado quanto$Th(\mathbb{N};+,\times)$. Mas o primeiro é recursivo, enquanto o último não é nem mesmo aritmeticamente definível.
A questão é que a definição "óbvia" de multiplicação em termos de adição não é realmente de primeira ordem : definições recursivas não são a priori algo que a lógica de primeira ordem pode fazer. Em estruturas suficientemente ricas, podemos encontrar maneiras de executar definições recursivas de primeira ordem e, de fato, é a riqueza de$Th(\mathbb{N};+,\times)$nesse sentido, o que torna o teorema de Gõdel possível, mas a adição sozinha não é poderosa o suficiente para fazer isso funcionar. A chave é que, se tivermos adição e multiplicação, podemos "codificar" sequências finitas de naturais por naturais individuais (por exemplo, por meio do$\beta$function ) e, portanto, falar sobre construções recursivas falando sobre as sequências que codificam seus "comportamentos passo a passo", mas apenas com a adição não podemos codificar pares de números por números individuais .
Elaborando a última frase e voltando à sua reivindicação$(2)$, aqui está um esboço de como definir exponenciação usando adição e multiplicação de primeira ordem:
Nós temos$a^b=c$se existe algum número que, quando interpretado como uma sequência, tem comprimento é$b$, primeiro termo$a$, último termo$c$, e$i+1$º termo igual a$a$vezes o$i$º termo.
Observe que esta é uma definição "de uma só vez" em vez de uma definição por um "processo recursivo:" modulo os detalhes da codificação de sequências finitas por números, envolve apenas a quantificação de números individuais e a verificação de propriedades básicas, que é exatamente o que primeiro a lógica de ordem pode fazer. Sem a capacidade de codificar sequências finitas como números individuais de maneira de primeira ordem - o que$(\mathbb{N};\max,+)$falta - estaríamos presos com a definição usual de não-primeira ordem.
- Como um aparte, é importante que esta seja uma "definição verificável:" na teoria$\mathsf{Q}$, que é um pequeno fragmento da teoria completa$Th(\mathbb{N};+,\times)$, temos isso para cada$a,b,c$a frase abreviada por$$\underline{a}^{\underline{b}}=\underline{c}$$(Onde$\underline{k}$é o numeral que representa o número natural$k$) é demonstrável em$\mathsf{Q}$E se$a^b=c$e é refutável em$\mathsf{Q}$E se$a^b\not=c$. Isso é chamado de representabilidade e é uma das ideias-chave da prova de Gõdel; de fato, toda função recursiva é representável .