Compactness of existential second order logic and definability of certain quantifiers

Question

It is known (as a slogan) that the "existential fragment of second-order logic (ESO) is compact".

My first question is:

(1) Is ESO compact for:

(a) uncountable languages

(b) languages with constants or just for relational vocabularies?

The possible answers are obviously:

1. ESO is compact only for countable languages (with or without constants, it doesn't matter here)
2. ESO is compact for uncountable vocabularies as well, but not the uncountable ones that contain constants
3. ESO is compact for uncountable languages - also the ones with constants.

Which one is correct? I can't see any problem in rewriting the usual compactness proofs for FO (also the ultraproduct one) to get compactness for ESO via Skolemization, but maybe there is something I cannot notice.

The second question is actually a motivation for the first one and concerns generalized quantifiers.

I stumbled upon a slogan that:

$\alpha$: The quantifier "there exist at most countably many" does not have a $\Sigma^1_1$ definition,

but the authors of the paper where I found it provide neither a proof nor a reference. I have checked in the most "obvious" sources ("Model-theoretic logics", Krynicki-Mostowski anthology on quantifiers, Keisler's paper on logic with "there exist at least uncountably many" quantifier, Westerstahl's book on quantifiers among couple others, some of them giving some results on those quantifiers in MSO on strings and trees, but I'm interested in the general case here).

The proof of $\alpha$ would be obvious, if we knew, that the complement of the class of countable models actually is $\Sigma^1_1$-definable, but it doesn't seem to be the case or at leas I can't see that.

There are easy deifnitions of countability and "at most countability" with higher complexity. One might write a sentence that says:

"The set of all elements $X$ is infinite and for any inifnite set $Y$ (i.e. subset of the universe) there is an injection from $X$ to $Y$"

Such a sentence is true in a model $\mathcal{M}$ if and only if $M$ is countably inifnite and the definition is $\Pi^1_2$, as it is a conjunction of a $\Sigma^1_1$ sentence and a $\Pi^1_2$ sentence.

One could also give a $\Sigma^1_2$ definition, aka "The Enumerability Axiom" (or at least that is the way G. Boolos called it) - the definition simply defines the natural numbers via the inductive properties of the successor function.

One can give a similar one, stating that there is a well-ordering of the universe with all the sets of predecessors of a given element being finite (but then the complexity grows).

From this we can also easily see how to give a definition of "at most countability" which still is not $\Pi^1_1$ obviously.

The only thing that comes to my mind for defining the class of uncountable models is stating that "the universe is infinite and is not countable".

Therefore I do not see a way to prove the result by a standard Craig's Interpolation or Lindstrom's First argument (referring to the fact that a given class of models is FO-definable (elementary), provided both the class and its complement are pseudoelementary, or $\Sigma^1_1$ definable).

Thus the questions: (2) What is the (minimal) complexity of the definition of at most countable models (or "there exist at most countably many" quantifier)?

(3) What is the (minimal) complexity of the definition of inifnite countable models (or "there exist inifnitely countably many" quantifier)?

(4) What is the (minimal) complexity of the definition of uncountable models (or "there exist uncountably many" quantifier)?

And now: the connection between the first part of my question and the second one(s).

If ESO is compact for uncountable languages with constants, then it is trivial to prove that the class of at most countable models cannot have a $\Sigma^1_1$ deifnition. Simply put: asuume that it has such a definition, call it $\varphi$. Add an uncountable set of constants $\{c_\alpha: \alpha < \omega_1\}$ and look at the following theory:

$\{\varphi\} \cup \{c_\alpha \neq c_\beta: \alpha < \beta < \omega_1\}$.

Then each finite subset of this theory is satisfiable, but the entire theory is not. So if we had "full" compactness for ESO, we would have the result (leaving questions (3) and (4) to answer, and, at least to me, interesting).

Thanks in advance.

Answer 1

Existential second-order logic is indeed compact for arbitrary languages. The proof I know is via ultraproducts, which I'll sketch here. (I once saw a Henkinization-style argument, but it was quite messy.)

As in the usual case, suppose $\Gamma$ is a set of ESO sentences which is finitely satisfiable. Let $F$ be the set of finite subsets of $\Gamma$, and for $X\in F$ let $M_X\models X$. Let $\mathcal{U}$ be any ultrafilter on $F$ such that for each $X\in F$, the set $$U_X=\{Y\in F: Y\supseteq X\}$$ is in $\mathcal{U}$. (Why does such a $\mathcal{U}$ exist? Just show that the set $\{U_X: X\in F\}$ has the finite intersection property, which in turn follows from the fact that the union of finitely many finite sets is finite.)

Then look at the ultrapower $\mathcal{N}=\prod_{X\in F} M_X/\mathcal{U}$. The proof that $\mathcal{N}$ satisfies $\Gamma$ is just Los' theorem, with an additional clause for the existential second order quantifiers. Specifically, suppose that every $M_X$ satisfies $\exists S\varphi(S)$, where $\varphi$ is a first-order sentence. (The proof with "every" replaced with "$\mathcal{U}$-many", or with more than one existential second-order quantifier in the front, is identical.) For each $X\in F$, let $S_X$ be a witnessing set for $M_X\models\exists S\varphi(S)$. Now let $S_\infty=\{f\in\mathcal{N}: \{X: f(X)\in S_X\}\in\mathcal{U}\}$. It's not hard to show that $S_\infty$ witnesses that $\mathcal{N}\models\exists S\varphi(S)$.

Note that the version of Los' Theorem we've established here is one-directional: we show that if $\mathcal{U}$-many factors satisfy an existential second-order sentence, then so does the ultraproduct; but we did not show the "downwards" direction. That's because the downwards direction is false in general! Consider, in the language of arithmetic, the universal second-order sentence $\psi$ asserting full induction. Now let $\mathcal{U}$ be a nonprincipal ultrafilter on $\mathbb{N}$, and let $\mathcal{N}=\prod\mathbb{N}/\mathcal{U}$ be the ultrapower over $\mathcal{U}$ of the standard model of arithmetic. Here's an explicit descending chain in $\mathcal{N}$: $$[(1, 2, 3, 4, 5, ...)]_\mathcal{U}>[(0, 1, 2, 3, 4, ...)]_\mathcal{U}>[(0, 0, 1, 2, 3, ...)]_\mathcal{U}> . . .$$

Indeed, in order for an ultrafilter $\mathcal{U}$ on an index set $\kappa$ to satisfy Los' theorem for universal second-order sentences, $\kappa$ has to be measurable!

Answer 2

Given a collection $\Gamma$ of existential second order sentences, form a collection $\Gamma'$ of first-order sentences as follows. For each sentence in $\Gamma$, say $(\exists S_1,\dots,S_k)\,\phi(S_1,\dots,S_k)$ with first-order $\phi$, remove the second-order quantifiers, leaving just $\phi(S_1,\dots,S_k)$, and then replace the second-order variables $S_i$ with predicate symbols of the same arity, making sure to use new, distinct predicate symbols for all of these sentences. ("New" means that you use predicate symbols that don't already occur in $\Gamma$; "distinct" means that each $\phi$ gets its own predicate symbols that are not used for any other $\psi$.) Let $\Gamma'$ be the set of first-order sentences so obtained from the second-order sentences in $\Gamma$. Then $\Gamma$ is satisfiable if and only if $\Gamma'$ is satisfiable. Apply this observation not only to $\Gamma$ but also to each of its finite subsets. In this way, compactness for $\Gamma$ is equivalent to compactness for $\Gamma'$; so ESO compactness follows from first-order compactness.

Answer 3

A stronger logic than ESO, namely FO(H) - first order logic with all Henkin quantifiers, does not define countability. This is so because in empty vocabulary it has Skolem-Loewenheim property. Leszek Kołodziejczyk used this fact for showing much simpler than mine argument separating FO(H) and Delta^1_2. countable models are Delta^1_2--definable, but not FO(H).

Of course FO(H) is not compact.