Completeness theorem: validity in some non-empty domain

Question

The completeness theorem in my text says that if a formula $G$ is valid in the domain of natural numbers, then $G$ is provable in the predicate calculus. The corollary also says that then $G$ is valid in any non-empty domain.

My question is:

If $G$ if valid in some non-empty domain, then is $G$ provable? i.e. are there other domains that $G$ can be valid in which satisfy the completeness theorem?

e.g. if $G$ were valid in the domain of real numbers, then would $G$ be provable?

Answer 1

Your language is rather unclear; I'll take Eric Wofsey's suggested interpretation:

• "Predicate calculus" here refers to first-order logic without equality.

• "Valid in the domain $D$" means "Satisfied in every structure with underlying set $D$."

Under this interpretation, your text's statement of the completeness theorem is true, and the answer to your question is that "$D$ is a set for which validity = provability" iff $D$ is infinite.

---

We have the following key fact: if $\varphi$ is a first-order sentence without equality and $\varphi$ is satisfied in some structure, then $\varphi$ is satisfied in an infinite structure. This is an easy exercise, the point being that since equality isn't allowed we can take an arbitrary model of $\varphi$ and "enlarge" it by duplicating elements ad nauseam without changing its equality-free properties (in particular, $\varphi$ will remain true in the enlarged structure).

• Note that the absence of equality is crucial here: consider the sentence $$\forall x\exists y(\neg x=y).$$ This sentence is satisfied in every structure with domain $\mathbb{N}$ (or indeed with infinite domain), but is not provable - it is false in any structure with domain a single element.

Then in conjunction with the downwards part of the Lowenheim-Skolem theorem we get that any satisfiable sentence of first-order logic without equality has a countably infinite model - and of course we can WLOG take $\mathbb{N}$ to be that set. The completeness theorem then identifies unsatisfiability with disprovability, and so we get the following true statement:

If $\varphi$ is a first-order sentence without equality and $\varphi$ is valid in the domain $\mathbb{N}$ (= satisfied in every model with underlying set $\mathbb{N}$), then $\varphi$ is provable.

Meanwhile, the full Lowenheim-Skolem theorem (which has two parts - the downwards part mentioned above, and the upwards part, which is really just a corollary of the compactness theorem) tells us that if $\varphi$ is valid in some infinite domain then $\varphi$ is valid in every infinite domain. So in particular, we have

If $D$ is an infinite set and $\varphi$ is valid in the domain $D$, then $\varphi$ is provable.

On the other hand, even without equality we can whip up a sentence $\eta_k$ - in the language with a single unary relation symbol "$U$" - which is valid in a domain $D$ iff $D$ has at most $k$ elements: $$\eta_k\equiv\exists x_1,...,x_k\forall y(U(x_1)\wedge ...\wedge U(x_k)\implies U(y)).$$ But clearly no $\eta_k$ is provable: $\neg\eta_k$ is satisfied, for example, in any structure of size $>k$ with exactly $k$-many elements on which $U$ holds.

So we get:

If $D$ is finite, then there is some sentence which is valid in the domain $D$ but not provable.

So this gives a complete answer to your question.