2
$\begingroup$

Gödel's first incompleteness theorem states roughly that "for any axiomatization of arithmetic, there are statements that can neither be proven to be false nor true."

Does this still hold when it comes to quantifier-free statements?

I.e. if we have the structure of arithmetic: $(\mathbb N, +,\cdot, 0,1)$, and we restrict to sentences $\Phi^{QF}$ about this structure that don't contain $\exists, \forall$, can we then for all $\phi\in \Phi^{QF}$ either prove or disprove $\phi$?

$\endgroup$
4
  • 1
    $\begingroup$ I don't know about completeness, but this fragment is apparently undecidable: math.stackexchange.com/q/1815098/14578. $\endgroup$
    – D.W.
    Mar 17, 2018 at 17:22
  • $\begingroup$ Nitpick: I suspect you mean formulas rather than sentences, i.e., you allow $\phi$ to contain variables, and you want to prove validity of $\phi$ (i.e., you want to prove the truth of $\forall x . \phi$ where $x$ ranges over all the variables in $\phi$). Is that right? $\endgroup$
    – D.W.
    Mar 17, 2018 at 17:27
  • $\begingroup$ @D.W., No i really meant sentences. No variables allowed. $\endgroup$
    – user56834
    Mar 17, 2018 at 19:14
  • 2
    $\begingroup$ Huh. Then I guess I'm confused. If there are no variables, then it seems like you can just evaluate all the expressions in the obvious way (i.e., recursively). What more is there to do? That seems too trivial, so I suspect I must not understand the problem statement... $\endgroup$
    – D.W.
    Mar 17, 2018 at 19:48

2 Answers 2

4
$\begingroup$

What you are referring to is called Baby Arithmetic ($\mathsf{BA}$) in Peter Smith's book An introduction to Gödel's Theorems.

$\mathsf{BA}$'s language [has] one single individual constant $0$, the one-place function symbol $S$, and the two-place function symbols $+$ and $\times$. [...] it lacks quantifiers and variables.

$\mathsf{BA}$ is complete, negation complete, and decidable.

$\endgroup$
0
$\begingroup$

I would say that any quantifier-free sentence $\varphi$ is true in $\mathbb{N}$ must be provable from, say, $PA^-$, since it can only be a boolean combination of things like $t_1(n_1,\dots,n_a)\leq t_2(m_1,\dots,m_b)$, where the $n$'s and $m$'s are just expressions of the form $1+\dots+1$, and it can be seen quite easily that weak theories (like $PA^-$) decide all of them.

i think this would also be true for formulas where only bounded quantifiers are used (this follows for example from absoluteness of $\Delta_0$ formulas by end-extensions of $\mathbb{N}$).

$\endgroup$
6
  • 1
    $\begingroup$ Do you have a proof or justification of the claim that any true sentence must be provable in $PA^-$? I don't understand the rest of the first sentence; what are the $t_i$'s? Sentences $\phi$ can contain multiplication, so they're not just sums. $\endgroup$
    – D.W.
    Mar 17, 2018 at 17:14
  • 1
    $\begingroup$ In Kaye's book even more is proved: the $\Sigma_1$-theory of $\mathbb{N}$ can be proved in $PA^-$, and the first part of my sentence is a corollary of this. $\endgroup$
    – Leo163
    Mar 17, 2018 at 17:21
  • $\begingroup$ The $t_i$'s are terms, so are expression of the $n$'s built using $+$ and $\cdot$, where the $n$'s are built combining the constant symbols $0$ and $1$, and everything of this form can be expressed as a sum of $1$'s. $\endgroup$
    – Leo163
    Mar 17, 2018 at 17:24
  • 1
    $\begingroup$ There are none: if $\varphi$ is a sentence, there are no free variables, but if $\varphi$ has no quantifier, then there can be no variables. $\endgroup$
    – Leo163
    Mar 17, 2018 at 17:32
  • 1
    $\begingroup$ The book I was mentioning in the comment above is "Models of Peano Arithmetic" by Richard Kaye. The result I mentioned is in chapter 2. $\endgroup$
    – Leo163
    Mar 17, 2018 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.