Are infinite subsets of the rationals definable?

Question

This is really two questions in one. Consider the structure $(\mathbb{Q},<)$. We adjoin to it a subset $S$ of $\mathbb{Q}$. Is there a first-order formula $F$ in the expanded language such that $F$ is true precisely when $S$ is an infinite subset of $\mathbb{Q}$? If it is not definable in that language alone, is it definable in the expanded language $(+,-,*,0,1,<)$?

Answer 1

Hagen von Eitzen has answered the second question (and note that the answer is exactly the same idea as David C. Ullrich's answer to your previous question).

The answer to the first question is no. Fix an irrational number $\alpha\in \mathbb{R}$. Let $(a_i)_{i\in \mathbb{N}}$ be a strictly increasing sequence of rational numbers approaching $\alpha$ from below, and let $(b_i)_{i\in \mathbb{N}}$ be a strictly decreasing sequence of rational numbers approaching $\alpha$ from above. Let $S = \{a_i\mid i\in \mathbb{N}\}\cup \{b_i\mid i\in \mathbb{N}\}$. The motivation for picking $S$ this way is that it is a discrete linear order with endpoints and with no limit point in $\mathbb{Q}$, just like every finite subset of $\mathbb{Q}$.

I claim that $S$ is indistinguishable from a finite set inside $(\mathbb{Q};<)$. More precisely, for any formula $\varphi$, there exists an $N$ such that $(\mathbb{Q};<,S)\models \varphi$ if and only if $(\mathbb{Q};<,T)\models \varphi$, where $T$ is any subset of $\mathbb{Q}$ of size $N$. This can be proven using the Ehrenfeucht-Fraïssé game.

---

Here's another proof that trades out the Ehrenfeucht-Fraïssé game for Łoś's theorem and countable categoricity of $(\mathbb{Q},<)$.

Suppose for contradiction that $\varphi$ is a sentence in the language $L' = \{<,S\}$ such that $(\mathbb{Q};<,S)\models\varphi$ if and only if $S$ is infinite.

For each natural number $n$, let $Q_n = (\mathbb{Q};<,T_n)$, where $T_n$ is a subset of $\mathbb{Q}$ of size $n$. So $Q_n\models \lnot \varphi$. Let $U$ be a non-principal ultrafilter on $\mathbb{N}$, and let $Q^\star$ be the ultraproduct $\prod_{n\in \mathbb{N}} Q_n / U$. In $Q^\star$, the interpretation of the relation symbol $S$ is infinite, but $Q^\star\models \lnot \varphi$, by Łoś's theorem.

Now let $(Q;<,S)$ be a countable elementary substructure of $Q^\star$, so again $S$ is infinite and $Q\models \lnot \varphi$. But the reduct $(Q;<)$ to the order language is a countable dense linear order without endpoints, so it is isomorphic to $(\mathbb{Q};<)$. Let $f\colon Q\to \mathbb{Q}$ be the isomorphism, and let $S' = f(S) \subseteq \mathbb{Q}$, the image of $S$ under the isomorphism. Then $(Q;<,S)\cong(\mathbb{Q};<,S')$, so $(\mathbb{Q};<,S')\models \lnot \varphi$, contradicting the fact that $S'$ is infinite.

Answer 2

Yes on the second part: $S$ is infinite iff it is non-empty, and either not bounded or there exist arbitrarily close elements.

$$\exists a\colon a\in S \land (\forall a\in S\,\exists b\in S\,a<b \lor \forall a\in S\,\exists b\in S\,b<a\\ \lor \forall d\in\Bbb Q\,d>0\to \exists a\in S\,\exists b\in S\,a<b\land b<a+d )$$