# The complexity of finiteness

Say that a second-order sentence in the empty language, $$\varphi$$, characterizes finiteness iff for every set $$X$$ we have $$X\models\varphi$$ iff $$X$$ is finite. I'm interested in the optimal complexity over $$\mathsf{ZF}$$ of sentences characterizing finiteness.

Many natural candidate sentences are $$\Sigma^1_2$$ (e.g. "$$X$$ admits a linear order which is well-ordered and co-well-ordered"), but we can do better: the sentence "$$X$$ can be linearly ordered and every linear ordering on $$X$$ is discrete" characterizes finiteness and is $$\Sigma^1_1\wedge\Pi^1_1$$. (Note that over $$\mathsf{ZFC}$$ we could drop the first clause, which would bring the comlpexity down to $$\Pi^1_1$$.)

Meanwhile,$$\mathsf{ZF}$$ alone proves that there is no $$\Sigma^1_1$$ sentence characterizing finiteness. First, note that $$\mathsf{ZFC}$$ proves the downward Lowenheim-Skolem theorem and that ultraproducts preserve $$\Sigma^1_1$$ sentences. From this we get that if $$\varphi$$ is $$\Sigma^1_1$$ and true in every finite structure then $$\omega\models\varphi$$ is true in $$L$$. But then by Mostowski absoluteness we in fact get $$\omega\models\varphi$$ in reality.

This leaves the $$\Pi^1_1$$ situation open:

Is there a $$\Pi^1_1$$ sentence in the empty language which $$\mathsf{ZF}$$ proves characterizes finiteness? Equivalently, is there a first-order sentence $$\psi$$ (in any language) such that $$\mathsf{ZF}$$ proves that the cardinalities of models of $$\psi$$ are exactly the infinite cardinalities?

My suspicion is that the answer is no - indeed, that every amorphous set satisfies all $$\Pi^1_1$$ sentences true in all finite sets. However, at the moment I don't see how to prove even the weaker claim.

EDIT: note that a negative answer to the question (which James Hanson has provided below) also shows that no $$\Sigma^1_1\vee\Pi^1_1$$ sentence can characterize finiteness. Suppose $$\psi\in\Sigma^1_1$$, $$\theta\in\Pi^1_1$$, and $$\psi\vee\theta$$ is true in every finite structure. Then either $$\psi$$ has arbitrarily large finite models in which case $$\psi$$ has an infinite model, or for some $$n\in\omega$$ the $$\Pi^1_1$$ sentence "$$\theta\vee[\forall x_1,...,x_{n+1}(\bigvee_{1\le i" is true of every finite structure and hence has an infinite model. Either way, $$\psi\vee\theta$$ has an infinite model. So James' answer in fact completely resolves the complexity of finiteness over $$\mathsf{ZF}$$.

• Oh, nice question! Absolutely nice question! – Asaf Karagila Jul 22 at 21:23
• @AsafKaragila Hehehe. (I'm glad to hear you say that, I was worried I was missing something painfully obvious!) – Noah Schweber Jul 22 at 21:25
• What language is this first-order $\psi$? – Asaf Karagila Jul 22 at 21:37
• @AsafKaragila Any whatsoever. Basically, we want to think of a $\Pi^1_1$ sentence $$\forall X_1,...,X_n\psi$$ with $\psi$ not containing any second-order quantifiers as saying "There is no $\{R_1,...,R_n\}$-structure - where $R_i$ is a relation symbol with the same arity as $X_i$ - with domain our set which is a model of the first-order sentence gotten from $\neg\psi$ by replacing each $X_i$ with $R_i$." – Noah Schweber Jul 22 at 21:47
• @HanulJeon I'm not sure what you mean. While a first-order (indeed, $\Sigma^1_1$) sentence cannot characterize finiteness, a sentence of the form "The domain cannot be expanded to a model of $\psi$" for a first-order sentence $\psi$ might characterize finiteness. E.g. "The domain cannot be expanded to a model of DLO" characterizes finiteness in $\mathsf{ZFC}$. – Noah Schweber Jul 23 at 14:32

As you discussed in the comments, $$\Pi_1^1$$ formulas $$\varphi(X)$$ in the empty language are equivalent to statements of the form 'there is no model of $$\psi$$ whose underlying set is $$X$$,' where $$\varphi$$ is a fixed first-order sentence in some language. So if we can show that

• for any structure $$\mathfrak{A}$$, if the underlying set $$A$$ is amorphous, then $$\mathrm{Th}(\mathfrak{A})$$ is pseudo-finite,

where a theory $$T$$ is pseudo-finite if every sentence $$\varphi \in T$$ has a finite model, then it will follow that it is consistent with $$\mathsf{ZF}$$ that no $$\Pi_1^1$$ sentence characterizes finiteness, because this implies a sort of reverse overspill property for first-order sentences: any sentence that has no finite models has no amorphous models as well.

The desired statement follows from a couple of results that exist in the literature.

Fact 1. If $$\mathfrak{A}$$ is a structure whose underlying set $$A$$ is amorphous, then $$\mathrm{Th}(\mathfrak{A})$$ is $$\omega$$-categorical and strongly minimal.

I don't know an original reference for this fact (I believe you can find it here), but it's not that hard to prove yourself if you know the Engeler–Ryll-Nardzewski–Svenonius theorem characterizing $$\omega$$-categorical theories and the characterization of strongly minimal theories as those in which every formula $$\varphi(x,\bar{y})$$ has a natural number $$n_\varphi$$ such that for any $$\bar{a}$$, if $$\varphi(x,\bar{a})$$ is satisfied by more than $$n_\varphi$$ many elements, then it is satisfied by all but at most $$n_\varphi$$ elements. (Note that this means that strong minimality of a theory is an arithmetical property. It's also not hard to show that $$\omega$$-categoricity is an arithmetical property of a theory.)

Fact 2 (Zilber; Cherlin, Harrington, Lachlan). A countable, complete, totally categorical theory is pseudo-finite.

While Fact 2 is proven in $$\mathsf{ZFC}$$, like many model theoretic statements it boils down to an arithmetical statement of low complexity, so by absoluteness it holds in $$\mathsf{ZF}$$ as well. (A more precise proof would be to let $$T$$ be the theory of whatever structure you have on some given amorphous set, pass to $$L(T)$$ (thinking of $$T$$ as a real) and then running one of these proofs there and getting the relevant finite models in $$L(T)$$, which are then models in $$V$$ by absoluteness. More advanced model theoretic facts (specifically the fact that every $$\omega$$-categorical $$\omega$$-stable theory can be axiomatized by some finite set of axioms together with axioms for each finite $$n$$ stating that the structure has more than $$n$$ elements) imply that $$T$$ is actually just in $$L$$ anyways, but we don't need this.)

So together with the easy fact that strongly minimal sets are uncountably categorical, we get that any structure on an amorphous set has a pseudo-finite theory. (I'm curious if there is a much more direct proof of this fact.) Therefore any $$\Pi_1^1$$ sentence in the empty language satisfied by all finite sets is satisfied by all amorphous sets as well.

• Ugh. I should have known that. I had an itch that this was a result. – Asaf Karagila Jul 23 at 22:41
• Plotkin proved in 1969 that if $T$ is $\aleph_0$-categorical, then it is consistent with ZF that it has a model where all subsets are definable (with parameters). In particular if a theory is strongly minimal, like the theory of equality, we get an amorphous set. Hodges proved a similar lemma in his work later (see Six Impossible Rings), and finally Agatha, to my knowledge, was the one to prove the converse for certain types of Dedekind-finite sets. – Asaf Karagila Jul 24 at 0:13
• I was trying to remember who proved that first result. Thanks. – James Hanson Jul 24 at 3:32