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

1 Answer 1

6
$\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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .