In some systems, not all. Maybe alcontali can tell us which, and why. — tim wood
An example of a system that is weak enough as such that the incompleteness problem does not occur is the
Presburger arithmetic. It only uses "0" and "1" as numbers and only addition "+" as operator.
So, it is only capable of saying things of the following form:
1) 0+0=0
2) 0+1=1 and 1+0=1
3) 1+1=0
Universal quantifiers only run over {0,1}. So, in my impression, they may not even be needed. For example,
can be always be replaced by x=0 or x=1 (This is known as
quantifier elimination).
The following remark supports that:
The decidability of Presburger arithmetic can be shown using quantifier elimination, supplemented by reasoning about arithmetical congruence (Enderton 2001, p. 188).
Still, there is also the following remark:
Generally, any number concept leading to multiplication cannot be defined in Presburger arithmetic, since that leads to incompleteness and undecidability.
I am not really sure why that is, though. According to the remark above, axiomatizing the following would cause incompleteness. Not sure why, though:
1) 0*0=0
2) 1*0=0 and 0*1=0
3) 1*1=1
I do not completely understand how adding this simple multiplication scheme would prevent quantifier elimination, but the text seems to claim that it does. It has something to do with "arithmetical congruence". (how!?)
So, my take on the matter is that, if quantifier elimination is not possible, because for example that would lead to infinitely long axioms, then the theory really requires first-order logic, and in that case, it will be incomplete.
For example, normal (=Peano) arithmetic runs over an infinite set n
{ 1, 3, 4, ... }. Quantifier elimination would lead to replacing it by sentences that look like: n=1 or n=2 or n=3 or n=4 ... which is an infinitely long sentence. Hence, the use of first-order logic quantifiers cannot be avoided -- to keep the size of the theory's rules finite -- leading to incompleteness.
"For each natural number the following is true" becomes: it is true for 1. It is true for 2. It is true for 3 ... ad infinitum. "There exists a natural number for which the following is true" becomes: It could be true for 1. It could be true for 2. It could be true for 3 ... ad infinitum.
So, my tentative interpretation is that when a theory gets rephrased in propositional logic (=without universal quantifiers), and it will always consist of infinitely-long construction rules, then the theory will be incomplete.
(but issues with "arithmetical congruence" can apparently also cause incompleteness, but I am not finished trying to figure that out yet ...)