Validity of a first order formula depends only on cardinality of domain?

Question

In chapter 4, exercise 1 of Smullyan's First-Order Logic he asks for a proof to the question appearing on the title. His phraseology is this: Show that the validity or satisfiability of a formula in a universe U depends only on the cardinality of U.

This seems wrong on the face of it to me; I mean doesn't the internal structure of the domain matter? A formula claiming a least element is true in $\mathbb{N}_{<}$ but not true in $\mathbb{Z}_{<}$. I know I am shifting domains here and he is asking for U-validity, not unrestricted validity.

What is it that I am not seeing? Thanks in advance.

Answer 1

"... within a specific universe $\text U$", where $\text U$ is any non-empty set.

You have not to rely on the "intended" interpretation... Consider e.g. :

$\exists x \forall y P^2xy$.

If we interpret $P$ as "less-equal" it is satisfied in $\mathbb N$ but not in $\mathbb Z$. But if we interpret $P$ as "less-than" is it false also in $\mathbb N$ [see similar Example page 48].

Conclusion : the above formula is not $\mathbb N$-valid.

---

Compare with $k$-validity, see :

• Geoffrey Hunter, Metalogic : An Introduction to the Metatheory of Standard First Order Logic (1971), pag 160-on.

Simple example of $1$-valid formula :

$Px \to \forall x Px$.

By the way, the above formula is not $2$-valid, and thus it is not valid.

In order to show that the above formula is $1$-valid, we have no need to interpret the predicate symbol $P$; it is enough to consider a single-element universe $U= \{ a \}$.

Two cases : (i) $P(a)$ does not hold, and thus the formula is true. (ii) $P(a)$ holds, and thus also $\forall x Px$, and again the formula is true.

Answer 2

Simple example:

$$ \exists x \exists y\ x \neq y. $$

True in any model whose domain has cardinality greater than 1. False in any model whose domain has cardinality 1.

The example is easily extended to all finite cardinalities.