if infinitely many statements can be built from an axiomatic system, how can you know if a theory is complete?

Question

yesterday I asked this question Does consistency imply completeness? and I finally understand the meaning of complete theory, which is, a theory is complete if all the well formed sentences that can be built from the terms of the axiomatic system can be either proved or disproved. Now, since infinite sentences can be built, how can you know if ALL of them can be proved or disproved?

Answer 1

since infinite[ly many] sentences can be built, how can you know if ALL of them can be proved or disproved?

Well, let me answer your question with some other questions:

• Since infinitely many natural numbers exist, how can you know that ALL of them can be factored into primes?

• Since infinitely many rational numbers exist, how can you know that ALL of them square to something other than $2$?

• Since there are infinitely many proofs in first-order Peano arithmetic, how can you know that ALL of them fail to prove the Godel sentence for first-order Peano arithmetic?

The point is that there's nothing special about logic here - math is all about$^1$ proving statements applicable to domains too large for us to check each instance. The topic makes the situation seem more mysterious, but remember: mathematical logic is part of mathematics, and the tools we use to prove results in logic are not fundamentally different from the tools we use to prove results in (say) number theory.

$^1$OK, saying that math is "all about" something is inherently troublesome, but I'd say this is pretty close to accurate as far as such things go - especially since I've phrased things to be somewhat compatible with ultrafinitist stances. For a historical example, Zermelo's Thesis I constitutes a strong version of this claim (one which I largely agree with, FWIW).

---

A bit more specifically, here are some examples of proofs of completeness of theories.

• First, a pretty trivial one: if $\mathcal{A}$ is any structure, then $Th(\mathcal{A})=\{\varphi:\mathcal{A}\models\varphi\}$ is complete. For suppose $\varphi\not\in Th(\mathcal{A})$. Then by definition of $\models$, we have $\mathcal{A}\models\neg\varphi$, so $\neg\varphi\in\mathcal{A}$.

• A bit more interesting is the proof that the theory consisting of all sentences true in every dense linear order without endpoints is complete. To prove this, we show that any two dense linear orders without endpoints (DLOs for short) are elementarily equivalent (= satisfy the same first-order sentences). By downward Lowenheim-Skolem we know that every DLO is elementarily equivalent to a countable one. But by a back-and-forth argument any two countable DLOs are isomorphic (so a fortiori elementarily equivalent).

• A much more interesting situation (in particular, the isomorphism trick from the previous bulletpoint doesn't work) is the proof that Presburger arithmetic is complete. I've given a very brief summary of it here; it boils down to some logical tricks and a proof by induction (on formula complexity). The induction argument is used to show that a certain theory (not Presburger arithmetic, but a conservative extension) is complete for quantifier-free sentences, and the logical tricks amount to both producing this theory and showing how that result implies completeness of Presburger arithmetic. So effectively the proof proceeds by reducing the "big" infinitary claim we're trying to show (full completeness of Presburger arithmetic) to a "small" infinitary claim (quantifier-free completeness of a related theory) which is easier to prove (by a more-or-less straightforward induction argument).