Predicati primitivi ricorsivi per esponenziazione e moltiplicazione
Ho le seguenti convinzioni dichiarate in modo informale e sostenute debolmente, alcune delle quali mi sembrano incoerenti dopo un'ulteriore riflessione. Mi chiedo dove possa essere la fonte degli errori nel mio pensiero; gli errori nelle definizioni di base sono una possibilità definita.
È impossibile eseguire l'eliminazione del quantificatore nella teoria del primo ordine degli interi con addizione e moltiplicazione. (Questa è, per quanto ne so, una versione leggermente più forte del primo teorema di incompletezza.)
Nella teoria del primo ordine degli interi con addizione e moltiplicazione, è possibile definire un primitivo predicato ricorsivo per l'elevamento a potenza. (Con un predicato per esponenziale, intendo solo qualcosa che si comporta come "$Fabc\text{ just when }a^b = c.$")
È possibile eseguire l'eliminazione del quantificatore nella teoria del primo ordine degli interi con due operazioni$a \oplus b = \min(a, b)$e$a \otimes b = a + b$(cioè, somma ordinaria di numeri interi). Sono consapevole che abbiamo anche bisogno di predicati di divisibilità e operatori di moltiplicazione affinché i numeri primi eseguano effettivamente l'eliminazione del quantificatore.
Nella teoria del primo ordine degli interi con le operazioni$\oplus$e$\otimes$, è possibile definire un predicato ricorsivo primitivo per la moltiplicazione (quasi esattamente allo stesso modo del predicato per l'elevamento a potenza sopra).
In parole povere, sembra che ci sia una rottura nell'analogia tra la "torre operativa ordinaria"$(+, \times, \hat{\phantom{n}}, \cdots)$e la "torre tropicale delle operazioni"$(\min, +, \times, \cdots)$.
Più specificamente, se (4) e (3) sono vere, non capisco perché non si possa semplicemente usare liberamente il predicato di moltiplicazione e quindi avere una situazione in cui entrambi possiamo eseguire l'eliminazione del quantificatore (tramite (3)) e non farlo eliminazione del quantificatore (tramite (1)). Mi sorprenderebbe molto se (2) fosse vero ma (4) no, e mi sorprenderebbe ancora di più se (2) fosse falso.
Sospetto di non capire bene cosa si intende per predicato di esponenziale (cioè la mia definizione informale di$Fabc$non è corretto, oppure c'è qualche dettaglio in più riguardante "l'uso libero del predicato di moltiplicazione" di cui non sono a conoscenza.
Risposte
Le tue affermazioni$(1), (2)$, e$(3)$sono tutti corretti. Reclamo$(4)$, tuttavia, non è corretto ; anzi, se la moltiplicazione fosse definibile finita$(\mathbb{N};\max,+)$poi la teoria$Th(\mathbb{N};\max,+)$sarebbe complicato come$Th(\mathbb{N};+,\times)$. Ma il primo è ricorsivo mentre il secondo non è nemmeno definibile aritmeticamente.
Il problema è che la definizione "ovvia" di moltiplicazione in termini di addizione non è in realtà di primo ordine : le definizioni ricorsive non sono a priori qualcosa che la logica di primo ordine può fare. In strutture sufficientemente ricche possiamo trovare modi per eseguire definizioni ricorsive in modo di primo ordine, e in effetti è la ricchezza di$Th(\mathbb{N};+,\times)$in questo senso che rende possibile l'eorema di Gödel, ma l'addizione da sola non è abbastanza potente per far funzionare questo. La chiave è che se abbiamo sia l'addizione che la moltiplicazione possiamo "codificare" sequenze finite di naturali da singoli naturali (per esempio tramite il$\beta$function ) e quindi parlare di costruzioni ricorsive parlando delle sequenze che codificano i loro "comportamenti passo-passo", ma con la sola addizione non possiamo nemmeno codificare coppie di numeri con numeri individuali .
Elaborando l'ultima frase e tornando alla tua affermazione$(2)$, ecco uno schema di come definire l'elevamento a potenza usando l'addizione e la moltiplicazione in un modo di primo ordine:
abbiamo$a^b=c$se c'è un numero che, se interpretato come sequenza, ha lunghezza is$b$, primo termine$a$, ultimo termine$c$, e$i+1$esimo termine uguale a$a$volte il$i$esimo termine.
Si noti che questa è una definizione "tutto in una volta" piuttosto che una definizione mediante un "processo ricorsivo": modulo i dettagli della codifica di sequenze finite per numeri, implica solo la quantificazione su singoli numeri e il controllo delle proprietà di base, che è esattamente ciò che prima- la logica dell'ordine può fare. Senza la capacità di codificare sequenze finite come numeri individuali in un modo di primo ordine - quale$(\mathbb{N};\max,+)$manca - saremmo bloccati con la solita definizione non di primo ordine.
- Per inciso, è importante che questa sia una "definizione verificabile:" nella teoria$\mathsf{Q}$, che è un minuscolo frammento della teoria completa$Th(\mathbb{N};+,\times)$, lo abbiamo per ciascuno$a,b,c$la frase abbreviata da$$\underline{a}^{\underline{b}}=\underline{c}$$(dove$\underline{k}$è il numero che rappresenta il numero naturale$k$) è dimostrabile in$\mathsf{Q}$Se$a^b=c$ed è confutabile in$\mathsf{Q}$Se$a^b\not=c$. Questa si chiama rappresentabilità , ed è una delle idee chiave della dimostrazione di Gödel; infatti, ogni funzione ricorsiva è rappresentabile .