16
$\begingroup$

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<j\le n+1}x_i=x_j)]$" 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}$.

$\endgroup$
  • 3
    $\begingroup$ Oh, nice question! Absolutely nice question! $\endgroup$ – Asaf Karagila Jul 22 at 21:23
  • $\begingroup$ @AsafKaragila Hehehe. (I'm glad to hear you say that, I was worried I was missing something painfully obvious!) $\endgroup$ – Noah Schweber Jul 22 at 21:25
  • $\begingroup$ What language is this first-order $\psi$? $\endgroup$ – Asaf Karagila Jul 22 at 21:37
  • $\begingroup$ @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$." $\endgroup$ – Noah Schweber Jul 22 at 21:47
  • 1
    $\begingroup$ @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}$. $\endgroup$ – Noah Schweber Jul 23 at 14:32
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ugh. I should have known that. I had an itch that this was a result. $\endgroup$ – Asaf Karagila Jul 23 at 22:41
  • 2
    $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jul 24 at 0:13
  • 1
    $\begingroup$ I was trying to remember who proved that first result. Thanks. $\endgroup$ – James Hanson Jul 24 at 3:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.