16
$\begingroup$

I would like to get a better idea of how badly compactness fails in $\mathcal{L}_{\omega_1\omega}$.

Let $\Gamma$ be an arbitrary set of sentences from $\mathcal{L}_{\omega_1\omega}$. Let the underlying signature $\tau$ also have arbitrary cardinality. Is there some cardinal $\kappa $ such that if every $\Delta\subseteq\Gamma$ where $|\Delta|\leq\kappa$ is satisfiable, then $\Gamma$ is satisfiable?

It is relatively easy to show that any such $\kappa$ would need to be $\geq \beth_{\omega_1}$, but I am unsure of how to proceed beyond there. If there is no such $\kappa$, I am also interested in weakening the question.

$\endgroup$
2
  • $\begingroup$ I suppose one could carefully read the proof that compactness does not fail in the weakly-compact case and tweak it to have the answer here. $\endgroup$
    – Asaf Karagila
    May 16 '12 at 9:02
  • 2
    $\begingroup$ If you weaken your demands to just having the upward Lowenheim-Skolem property, then Morley proved that the Hanf number of $L_{\omega_1, \omega}$ is $\beth_{\omega_1}$. $\endgroup$
    – Haim
    May 16 '12 at 12:15
22
$\begingroup$

I like the question very much.

First, let me mention briefly that the question has a flaw in the quantifier order, since you have first fixed the theory $\Gamma$ and then ask for a cardinal $\kappa$ such that if all subtheories $\Delta\subset\Gamma$ of size at most $\kappa$ are consistent, then $\Gamma$ is consistent. This is trivially affirmative, since we may simply let $\kappa=|\Gamma|$, in which case $\Delta=\Gamma$ is one of the allowed subtheories.

The actual question here is the following (and note that I replace your $\leq\kappa$ with $\lt\kappa$, since this is how one usually frames it with weakly and strongly compact cardinals):

Question. Is there are a cardinal $\kappa$ such that if $\Gamma$ is any $L_{\omega_1,\omega}$ theory in any signature, and every $\kappa$-small subtheory is consistent, then $\Gamma$ is consistent?

Let us call this property the $\kappa$-compactness property for $L_{\omega_1,\omega}$. Just to be clear, $L_{\omega_1,\omega}$ is the infinitary language in which one is allowed to form countable conjunctions and disjunctions, but still only finitely many quantifiers at a time. Meanwhile, $L_{\kappa,\lambda}$ allows conjunctions and disjunctions of size less than $\kappa$ and blocks of quantifiers of size less than $\lambda$. One instinctively thinks of the following large cardinals:

  • A cardinal $\kappa$ is weakly compact if and only if it is uncountable and $L_{\kappa,\kappa}$ has the $\kappa$-compactness property for theories in a language of size at most $\kappa$.

  • A cardinal $\kappa$ is strongly compact if and only if it is uncountable and $L_{\kappa,\kappa}$ has the $\kappa$-compactness property for any theory without any size restriction.

One crucial difference between $L_{\omega_1,\omega}$ and $L_{\kappa,\kappa}$ or even $L_{\omega_1,\omega_1}$ is that in $L_{\omega_1,\omega_1}$, one can express the assertion that a relation is well-founded, since you can say that it has no infinite descending sequence. This does not seem possible to express in $L_{\omega_1,\omega}$, because one can quantify only finitely many variables at a time.

Theorem. If $\kappa$ is strongly compact, then $L_{\omega_1,\omega}$ has the $\kappa$-compactness property.

Proof. This is immediate, since any $L_{\omega_1,\omega}$ theory is also a $L_{\kappa,\kappa}$ theory. QED

Theorem. If $L_{\omega_1,\omega}$ has the $\kappa$-compactness property, then there is a measurable cardinal.

Proof. Suppose that $L_{\omega_1,\omega}$ has the $\kappa$-compactness property. Let $\Gamma$ be the theory including the following assertions:

  • the full $L_{\omega_1,\omega}$ diagram of the structure $\langle \kappa,\in,\hat A\rangle_{A\subset \kappa}$, in the language with a predicate $\hat A$ for each $A\subset\kappa$ and constants $\hat\alpha$ for each $\alpha\in\kappa$.
  • the assertions $c\neq \hat\alpha$ for each $\alpha\in\kappa$.

Note that any $\kappa$-small subtheory of $\Gamma$ is consistent, since we may interpret $c$ inside $\kappa$ if only fewer than $\kappa$ many $\alpha$ are excluded. So by the $\kappa$-compactness property, $\Gamma$ has a model $\langle M,\hat\in,\hat A^M\rangle$. Let $U$ be the set of $A$ for which $M\models c\in\hat A$. This $U$ is an ultrafilter and it is countably complete, since the assertions $(\forall x. \bigwedge_n x\in A_n)\to x\in A$, whenever $A=\cap A_n$, are part of $\Gamma$. It is nonprincipal since $c\neq \hat\alpha$ for any $\alpha$. So there is a countably complete nonprincipal ultrafilter, and hence there is a measurable cardinal, since the degree of completeness of such an ultrafilter is always measurable. QED

In particular, the hypothesis is strictly stronger than a weakly compact cardinal.

I'm not yet sure of the exact strength, but I'm inclined to think it is equiconsistent with a strongly compact cardinal, in light of the following observation:

Theorem. If $\kappa$ is the least measurable cardinal, then $L_{\omega_1,\omega}$ has the $\kappa$-compactness property if and only if $\kappa$ is strongly compact.

Proof. Suppose $\kappa$ is the smallest measurable cardinal and $L_{\omega_1,\omega}$ has the $\kappa$-compactness property. Fix any regular cardinal $\theta\geq\kappa$, and let $\Gamma$ be the $L_{\omega_1,\omega}$ theory of $\langle\theta,\in,\hat\alpha,\hat A\rangle_{\alpha\in\theta,A\subset\theta}$, plus the assertion $\hat\alpha\lt c$ for each $\alpha\in\theta$. This theory is $\kappa$-satisfiable, and indeed, $\theta$-satisfiable. So it is satisfiable, and there is therefore a model $\langle M,\in^M,\hat\alpha^M,\hat A^M,c^M\rangle$. Let $U$ be the set of $A\subset \theta$ such that $M\models c\in \hat A$. This is a countably complete nonprincipal uniform ultrafilter on $\theta$. Since $\kappa$ is the least measurable cardinal, it follows that $U$ must be $\kappa$-complete. So we have a $\kappa$-complete nonprincipal uniform ultrafilter on every regular $\theta\geq\kappa$. By a theorem of Menas, this implies that $\kappa$ is strongly compact. QED

Note that results of Magidor show that it is indeed possible for the least measurable cardinal to be strongly compact.

$\endgroup$
7
  • $\begingroup$ Correction, in the last paragraph, it should be Ketonen's theorem, not Menas'. $\endgroup$ May 16 '12 at 13:46
  • $\begingroup$ Isn't the $\kappa$-compactness of $\mathcal L_{\kappa,\kappa}$ and $\mathcal L_{\kappa,\omega}$ equivalent? I recall it is so at east in the weakly compact case. $\endgroup$
    – Asaf Karagila
    May 16 '12 at 14:09
  • $\begingroup$ If you mean $L_{\kappa,\omega_1}$, then I agree. $\kappa$ is weakly compact iff $L_{\kappa,\kappa}$ has $\kappa$-compactness iff $L_{\kappa,\omega_1}$ has $\kappa$-compactness, for theories in a language of size at most $\kappa$, and the same for strong compactness if one uses larger theories. But with $L_{\kappa,\omega}$, you cannot seem to say "well-founded", and so the usual arguments break donw. $\endgroup$ May 16 '12 at 14:15
  • 1
    $\begingroup$ I'm inclined to think that $L_{\omega_1,\omega}$ has the $\kappa$-compactness property if and only if there is a strongly compact cardinal $\leq\kappa$. The reverse direction is clear. For the forward direction, my argument above shows that for all regular $\theta\geq\kappa$, there is a countably complete uniform ultrafilter on $\theta$. But I'm not clear on whether this gives a strongly compact cardinal or not. But this property certainly fails in $L[\mu]$, and so a measurable cardinal is not sufficient. I think it will similarly fail in many other canonical inner models. $\endgroup$ May 16 '12 at 15:38
  • 2
    $\begingroup$ Sorry for a not quite on-topic comment, but in case someone reading this is wondering: that no $L_{\kappa,\omega}$ can define well-foundedness is known for fact, it was proved by Lopez-Escobar eudml.org/doc/213903 . For fascinating connections of $L_{\infty,\omega}$ extended with a means for expressing well-foundedness, see Barwise dx.doi.org/10.1016/0003-4843(72)90002-2 . $\endgroup$ Dec 10 '13 at 23:50
5
$\begingroup$

This answer is a complement to Joel David Hamkin's very nice answer.

By recent work of J. Bagaria and M. Magidor, there is a large cardinal notion between measurable and strongly compact that answers your question (as formulated by Hamkins). This notion is $\omega_1$-strongly compact cardinals.

Definition A cardinal $\kappa$ is $\delta$-strongly compact, if every $\kappa$-complete filter on a set $I$ can be extended to an $\delta$-complete ultrafilter on $I$. We focus on the case where $\delta=\omega_1$.

Some consequences of the definition:

  1. Every strongly compact cardinal is $\omega_1$-strongly compact.
  2. If $\kappa$ is $\omega_1$-strongly compact, then the same is true for every $\lambda\ge\kappa$. So, the interest is in the first $\omega_1$-strongly compact.
  3. If $\kappa$ is $\omega_1$-strongly compact and $\mu$ is the first measurable, then $\kappa$ is $\mu$-strongly compact. So, the first measurable can not be above the first $\omega_1$-strongly compact.

It follows that if first measurable=first strongly compact, then first measurable=first $\omega_1$-strongly compact=first strongly compact. This complements the three theorems from Hamkin's answer.

To your question now, Bagaria and Magidor proved the following.

Theorem The following are equivalent:

  • $\kappa$ is a strong compactness cardinal for $L_{\omega_1,\omega}$
  • $\kappa$ is a strong compactness cardinal for $L_{\omega_1,\omega_1}$
  • $\kappa$ is $\omega_1$-strongly compact
  • For every set $I$ there is an $\omega_1$-complete fine measure of $P_\kappa(I)$.

They actually prove more since they provide a list of 5-6 equivalent formulations of $\omega_1$-strong compactness. See these slides from one of Magidor's talks.

In the second reference below, it is proved using Radin forcing that consistently the first $\omega_1$-strongly compact is singular (of measurable cofinality) and therefore, strictly between the first measurable and the first strongly compact. This justifies the claim that (consistently) neither a measurable nor a strongly compact cardinal can answer your question.

References:

Bagaria, Joan; Magidor, Menachem, On $\omega_1$-strongly compact cardinals, J. Symb. Log. 79, No. 1, 266-278 (2014). ZBL1337.03076.

and

Bagaria, Joan; Magidor, Menachem, Group radicals and strongly compact cardinals, Trans. Am. Math. Soc. 366, No. 4, 1857-1877 (2014). ZBL1349.03055.

$\endgroup$
4
$\begingroup$

This is really a comment, but (a) it's too long and (b) is ought to be attached to both of the answers. Not only does the characterization of the $\kappa$-compactness property not depend on the availability of infinite quantifier strings (as discussed in the comments on Joel's answer and as explicitly stated in Ioannis's answer), it doesn't depend on quantifiers at all. Propositional logic suffices.

More precisely, consider propositional logic with countable conjunctions and disjunctions. Suppose $\kappa$ is a cardinal and, for any set $\Gamma$ of sentences in this logic, if every subset of size $<\kappa$ is satisfiable, then so is $\Gamma$. I claim that $\kappa$ is $\omega_1$-strongly compact, i.e., every $\kappa$-complete filter on any set $I$ can be extended to a countably complete ultrafilter.

To prove this, let $I$ and a $\kappa$-complete filter $\mathcal F$ on it be given. Consider the following set $\Gamma$ of sentences in the propositional logic described above, with a propositional variable $\bar A$ for every subset $A$ of $I$. $\Gamma$ contains:

First, the sentences $(\bar A\land\bar B)\leftrightarrow\overline{A\cap B}$ and $\neg\bar A\leftrightarrow\overline{I-A}$, for all $A,B\subseteq I$,

Second, the sentences $\bar A$ for all $A\in\mathcal F$,

Third, the sentences $\bigwedge_{n\in\omega}\overline{A_n} \leftrightarrow \overline{\bigcap_{n\in\omega}A_n}$ for all countable sequences $(A_n)$ of subsets of $I$.

Then any subset of $\Gamma$ of cardinality $<\kappa$ is satisfiable. In fact, we can satisfy all the sentences of the first and third sorts along with any $<\kappa$ sentences of the second sort as follows. The $<\kappa$ sentences of the second sort are $\bar A$ for some $<\kappa$ elements $A$ of $\mathcal F$. As $\mathcal F$ is $\kappa$-complete, these $A$'s have a nonempty intersection (in fact, their intersection is in $\mathcal F$), so let $i$ be a point in that intersection. Then give each propositional variable $\bar X$ the truth value "true" if $i\in X$ and "false" otherwise. It is easy to check that our subset of $\Gamma$ is satisfied by this valuation.

So, by hypothesis, there is a valuation $v$ making all of $\Gamma$ true. Define $\mathcal U\subseteq\mathcal P(I)$ to be $$ \mathcal U=\{A\subseteq I:v(\bar A)=\text{true}\}. $$ Then $\mathcal U$ is an ultrafilter on $I$ because $v$ satisfies the first batch of sentences in $\Gamma$; it extends $\mathcal F$ because of the second batch; and it is countably complete becuse of the third batch.

$\endgroup$
2
  • 1
    $\begingroup$ @godelian Thanks for the correction. $\endgroup$ Mar 21 '18 at 21:54
  • $\begingroup$ Very interesting! $\endgroup$ Mar 22 '18 at 10:51

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.