The complexity of finiteness

Question

Say that a second-order sentence in the empty language, $varphi$, characterizes finiteness iff for every set $X$ we have $Xmodelsvarphi$ 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_1wedgePi^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 $omegamodelsvarphi$ is true in $L$. But then by Mostowski absoluteness we in fact get $omegamodelsvarphi$ 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_1veePi^1_1$ sentence can characterize finiteness. Suppose $psiinSigma^1_1$, $thetainPi^1_1$, and $psiveetheta$ 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 $ninomega$ the $Pi^1_1$ sentence "$thetavee[forall x_1,...,x_{n+1}(bigvee_{1le i<jle n+1}x_i=x_j)]$" is true of every finite structure and hence has an infinite model. Either way, $psiveetheta$ has an infinite model. So James' answer in fact completely resolves the complexity of finiteness over $mathsf{ZF}$.

James Hanson · Answer

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.

The complexity of finiteness

One Answer

Add your own answers!

Ask a Question