Set of formulas that define uncountable subsets of $\mathbb{R}$.

Question

This is a follow-up to my previous question about a formula in the language of ordered fields that can distinguish infinite subsets of $\mathbb{R}$. My current question is this. Consider the structure $(\mathbb{R};+,*,0,1,<)$. We adjoin to it a new unary predicate $S$, that picks out a certain subset of the reals. Is there a single formula, or if not, an infinite set of formulas, in the expanded language that holds precisely when $S$ is an uncountable subset of the reals? I think there is not, but I would like a proof.

Answer 1

Your question is answered in an old paper of Abraham Robinson, Solution of a Problem of Tarski (Fundamenta Mathematicae, 1959). Robinson proved (see Theorem 4.1) that the theory of real closed fields with a predicate $S$ naming a dense proper real closed subfield is complete.

As a consequence (since any subfield of $\mathbb{R}$ contains $\mathbb{Q}$ and hence is dense in $\mathbb{R}$), for any two proper real closed subfields $R_1$ and $R_2$ of $\mathbb{R}$, $(\mathbb{R};+,\times,0,1,<,R_1)$ and $(\mathbb{R};+,\times,0,1,<,R_2)$ are elementarily equivalent. In particular, when $R_1$ is countable and $R_2$ is uncountable, there is no set of first-order sentences that holds in $(\mathbb{R};+,\times,0,1,<,R_2)$ but not in $(\mathbb{R};+,\times,0,1,<,R_1)$.

This result was extended by Angus Macintyre in his PhD thesis "Classifying pairs of real closed fields" in 1967. Among other things, Macintrye showed that the theory of real closed fields with a predicate $S$ naming a real closed subfield (but not necessarily dense) has $2^{\aleph_0}$-many completions.

By the way, the "problem of Tarski" referenced in the title of Robinson's paper was to give a decision procedure for the theory of the structure $(\mathbb{R};+,\times,0,1,<,A)$, where $A$ is the field of real algebraic numbers. Robinson solved this problem by giving a complete recursive axiomatization of the theory of this structure (just the axioms of of real closed fields with a predicate $S$ naming a dense proper real closed subfield).

Answer 2

Alex Kruckman has answered your question, and shown in particular that Eric Wofsey's original guess was correct. Let me add, however, a brief comment about the general situation - when we replace $\mathcal{R}=(\mathbb{R};+,\times)$ with some other "base structure."

Specifically, suppose we add a unary predicate naming the natural numbers to $\mathcal{R}$ to get $\mathcal{R}_\mathbb{N}=(\mathbb{R};+,\times,\mathbb{N})$. There is over $\mathcal{R}_\mathbb{N}$ a definable surjection from reals to infinite sequences of reals - or more precisely, there is a formula $\psi(x,y,z)$ such that in $\mathcal{R}_\mathbb{N}$ we have

• whenever $\psi(x,y,z)$ holds, $y\in\mathbb{N}$, and

• for each map $f:\mathbb{N}\rightarrow\mathbb{R}$ there is some $x$ such that for each integer $y$ we have $\psi(x,y,z)\leftrightarrow z=f(y)$.

Building such a $\psi$ is rather tedious; if you prefer, just add your favorite surjection $\mathbb{N}\times\mathbb{R}\rightarrow\mathbb{R}$ to $\mathcal{R}_\mathbb{N}$ as well. Note that while such surjections are messy, they're not set-theoretically messy (e.g. they can be low-level Borel), so we're still staying in the realm of reasonably concrete structures.

The point is that with such a formula in hand we can identify countability of a set over the base structure $\mathcal{R}_\mathbb{N}$: $S$ is countable iff the corresponding further expansion $\mathcal{R}_{\mathbb{N},S}$ satisfies $$\exists x\forall z\in S\exists y\in\mathbb{N}(\psi(x,y,z)).$$ In fact, it turns out that we potentially have lots of "cardinality-defining" power in $\mathcal{R}_\mathbb{N}$ per this mathoverflow discussion.

Now admittedly nothing like this coding apparatus is available to us when our base structure is $\mathcal{R}=(\mathbb{R};+,\times)$ and our base logic is $\mathsf{FOL}$. Indeed, by o-minimality $\mathcal{R}$ doesn't even have a $\mathsf{FOL}$-definable pairing operation. However, this does show that no "coarse" argument is going to apply. At this point one natural, if extremely broad and unfocused, question is whether we can identify any structural "dividing lines" relating to the problem of capturable cardinalities; at present, however, I don't have any thoughts on this.