Why ZFC+FOL cannot uniquely describe/characterize $\mathbb{R}$ or $\mathbb{N}$?

Question

I find the following text on the Wikipedia page on first order logic:

First-order logic is the standard for the formalization of mathematics into axioms and is studied in the foundations of mathematics. Peano arithmetic and Zermelo–Fraenkel set theory are axiomatizations of number theory and set theory, respectively, into first-order logic. No first-order theory, however, has the strength to uniquely describe a structure with an infinite domain, such as the natural numbers or the real line. Axioms systems that do fully describe these two structures (that is, categorical axiom systems) can be obtained in stronger logics such as second-order logic.

Here, what I want to ask is what does uniquely describe/characterize mean? Why is it that $\textbf{FOL}$ cannot uniquely describe/characterize $\mathbb{R}$ or $\mathbb{N}$?

Answer 1

Why is it that FOL . . . cannot uniquely describe/characterize $\mathbb{R}$ or $\mathbb{N}$?

Here's the precise statement: if $\Phi$ is any set of first order sentences true in $\mathcal{N}=(\mathbb{N}; +, \times)$, then there is a structure $\mathcal{A}$ such that

• The sentences in $\Phi$ are also true in $\mathcal{A}$, and

• $\mathcal{A}\not\cong\mathcal{N}$.

That is, no set of first-order sentences characterizes $\mathcal{N}$ up to isomorphism. The same is true for any other infinite structure.

This is a consequence of the compactness theorem for first-order logic; but you may also be interested in the Lowenheim-Skolem theorem, which describes another fundamental obstacle to describing structures in first-order logic.

---

Belatedly incorporating and expanding on an observation by Vladimir Kanovei, if we're a bit flexible about our requirements and push a little into the second-order realm we can find a lot of positive results:

• $\mathcal{N}=(\mathbb{N}; +,\times)$ is characterizable up to isomorphism as the minimal model of a particular first-order theory.

• By the downward Lowenheim-Skolem theorem no minimality characterization is possible for the field $\mathcal{R}=(\mathbb{R};+,\times)$, and compactness (in its guise as the upward Lowenheim-Skolem theorem) prevents any maximality characterization for any infinite structure whatsoever. However, $\mathcal{R}$ is characterizable as the maximal model of the first-order theory of real closed fields which additionally omits the partial type describing an infinite element (= is Archimedean).

  • Interestingly, $\mathcal{R}$ is not the maximal rigid real closed field. There are in fact rigid non-archimedean real closed fields. Weirdly, it is currently open whether countable rigid non-Archimedean real closed fields exist!

• Somewhat less naturally, $\mathcal{R}^-=(\mathbb{R};+,<)$ is the minimal model of the first-order theory of divisible ordered abelian groups which realizes every type over a countable set of parameters which is bounded above and has ordertype $\omega$.

It's worth noting that $(i)$ pretty much every naturally-occurring structure can be described up to isomorphism by a second-order theory or even sentence (Vaananen: "the ordered structure of the natural numbers, the complete separable Archimedian field of reals numbers, the complex field, as well as practically all commonly occurring mathematical structures have a categorical second order axiomatisation"), and $(ii)$ we usually only need a small fragment of $\mathsf{SOL}$ to do this.

Answer 2

A concrete way of viewing this phenomenon is to note that the ultrapower of a given model $M$ will produce a new model ${}^\ast\! M$ which can easily be shown to be nonisomorphic to $M$. It is an elementary extension of $M$ by Los's theorem. The construction of the ultrapower can be carried out in ZFC. Note that to apply compactness theorems you will typically also require some form of the axiom of choice.

Here $\mathbb N$ and $\mathbb R$ are sometimes claimed be to categorical. Two remarks are in order.

(1) Whatever the merits of the claimed categoricity, it requires more than first order logic. For example, to characterize the reals we need the completeness property which requires a quantifier running over all subsets of $\mathbb R$.

(2) The categoricity is dependent on a background model of ZFC. Model-dependence is sometimes concealed behind talk about intended models or intended interpretations; see e.g., this post for a discussion. In different models of ZFC the natural numbers will behave very differently, and similarly for the reals.

Answer 3

There are two ways to interpret this question, and the distinction is indeed important.

Working inside a universe of $\sf ZFC$, using first-order logic inside the universe, it is indeed impossible to characterize $\Bbb R$ or $\Bbb N$, as Noah wrote. Using one of myriad of methods (Lowenheim-Skolem theorems, compactness, ultrapowers) we can produce models with the same theory as $\Bbb R$ or $\Bbb N$ which have a completely different cardinality. In fact, we can even produce models of the same cardinality which are not isomorphic to them.

At the same time, one can interpret this as asking, assuming that we work with framework of first-order logic and $\sf ZFC$. Can we uniquely characterize the reals or the natural numbers? Namely, we work inside a fixed universe of $\sf ZFC$, with first-order logic as the underlying logic. Can we characterize the natural numbers or the real numbers inside the model? The answer to that is "yes, up to isomorphism (inside the model)". What we can prove is that:

1. There exists a set which represents the natural numbers, and there exists a set which represents the real numbers.
2. Any other object $X$ inside the model, that the model satisfies the condition "$X$ is a well-founded model of Peano" or "$X$ is a Dedekind-complete ordered field" is isomorphic---inside the model---to the natural numbers or the real numbers respectively.

In fact, this is why we bother using first-order logic and set theory as a foundation. Second-order logic has no proof verification algorithm. So instead of using second-order logic on the natural numbers, we instead prove that $\sf ZFC$ proves such and such, and thus transforming a second, or third, or higher order logic statements into a first-order statement in the language of set theory. And since first-order logic does have an algorithmic method of verifying if something is a valid proof, this means that we can program a computer to check if our proof is sound.

Answer 4

Still to some extent $\mathbb N$ is characterisable in FOL plus a small increment. The increment being the non-FOL requirement of being a least structure satisfying some list of axioms (Peano's axioms in the FOL version for $\mathbb N$). What about $\mathbb R$ ?