TransWikia.com

The complexity of finiteness

Mathematics Asked on December 1, 2021

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}$.

One 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.

Answered by James Hanson on December 1, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP