1
$\begingroup$

The following definitions and Theorems come from M. Magidor's paper "On the Role of Supercompact and Extendible Cardinals in Logic" (Israel J. Math., Vol. 10, 1971):

"Definition: Logic is called $\kappa$ compact iff for every set of formulae A in this logic, if every subset of A of cardinality $\lt$$\kappa$ has a model, then A has a model.

The $L^{n}_{\kappa}$ logic is like the n-th order logic, except that we allow conjunction and disjunctions of less than $\kappa$ formulae. The usual second order logic is of course $L^{2}_{\omega}$.

Theorem 4. $\kappa$ is extendible iff $L^{2}_{\kappa}$ is $\kappa$ compact. $\kappa$ is the first extendible iff it is the first $\alpha$ such that second order logic is $\alpha$ compact." He also proves this theorem as well: "if $\kappa$ is extendible it is supercompact". However, nowhere in his paper does he say whether he is using full semantics or Henkin models when he refers to $\kappa$ compactness. I therefore will go out on a limb here (so to speak) and presume (rightly or wrongly) that he is using full semantics rather than Henkin models (after all, he does speak of "the usual second order logic" and that, I suppose, might be a subtle indication that he means to use full semantics).

Under this assumption, it is well known that $L^{2}_{\omega}$ is not compact. Under this assumption, it seems one can prove the noncompactness of $L^{2}_{\omega}$ using Theorem 4 and "if $\kappa$ is extendible then it is supercompact". I argue in the following manner: by Theorem 4, if $L^{2}_{\omega}$ is $\omega$ compact (i.e. compact) then $\omega$ is extendible. If $\omega$ is extendible it is supercompact. However, in his answer to arsmath's mathoverflow question, "$\aleph_0$ (arsmath writes it "Aleph 0") as a large cardinal", Amit Kumar Gupta shows that $\omega$ is not supercompact, hence by this, the chain of contrapositives of the implications I use and modus ponens, $L^{2}_{\omega}$ is not $\omega$ compact (i.e. not compact).

This, however, raises the following question: even if $L^{2}_{\omega}$ is not compact, by Theorem 4, if there exists some extendible $\kappa$ ($\gt$$\omega$) then $L^{2}_{\kappa}$ is $\kappa$ compact (i.e. second order logic satisfies some compactness theorem). Those who do not believe in the existence of large cardinals should ask themselves whether second order logic should be $\kappa$ compact under full semantics. Another question that arises is this: since $L^{2}_{\omega}$ is compact under Henkin models, does Theorem 4 hold over Henkin models?

$\endgroup$
2
$\begingroup$

For your second question, the answer is "no." Since, with Henkin semantics, second-order logic is just re-syntacted first-order logic, of course theorem 4 fails for Henkin semantics: $L_\kappa^2$ with Henkin semantics is compact iff $L_{\kappa,\omega}$ is compact - that is, iff $\kappa$ has the tree property (which is implied by, but not equivalent to, $\kappa$ being weakly compact - weakly compact = tree property plus inaccessible).

Meanwhile, I'm not sure what your first question is asking. It is quite reasonable to have a sequence of stronger logics $\mathcal{L}_\alpha$ ($\alpha\in ON$) such that compactness fails early ($\mathcal{L}_\omega$ is not $\omega$-compact) but holds occasionally later on ($\mathcal{L}_\kappa$ is $\kappa$-compact for some $\kappa$). For instance, take $\mathcal{L}_\alpha=L_{\aleph_\alpha,\omega}$. Then $\mathcal{L}_\alpha$ is compact iff $\aleph_\alpha$ has the tree property - in particular, it is enough for $\alpha$ to be weakly compact. So I don't see what challenge this raises for "those who do not [or do?] believe in the existence of large cardinals."

$\endgroup$
  • $\begingroup$ Thanks for your very nice answer. Since Theorem 4 does not hold under Henkin semantics, it is clear that Magidor was assuming $L^2_{\kappa}$ with full semantics. $\endgroup$ – Thomas Benjamin Oct 20 '15 at 1:14
  • $\begingroup$ (cont.) I will have to think about the question posed in the second part of your answer. Is there some way '$L^2_{\kappa}$ is $\kappa$-compact' could be shown to be independent of $L^2_{\kappa}$ ( a type of forcing argument, for instance)? $\endgroup$ – Thomas Benjamin Oct 20 '15 at 1:32
  • $\begingroup$ @ThomasBenjamin I'm not sure what you mean by "Is there some way '$L_\kappa^2$ is $\kappa$-compact could be shown to be independent of $L_\kappa^2$' - can you clarify? $\endgroup$ – Noah Schweber Oct 20 '15 at 1:56
  • $\begingroup$ Some further questions. Under full semantics, it is known that $L^2_{\omega}$ is incomplete, that is, the set of truths and the set of falsities of $L^2_{\omega}$ each are not r.e. (what is the position of each of these sets in the Kleene hierarchy)? If $L^2_{\omega}$ is incomplete, then is $L^2_{\kappa}$ also incomplete under full semantics as well? Let me assume now, for the sake of argument, that the sentence "$L^2_{\kappa}$ is $\kappa$-compact" is independent of $L^2_{\kappa}$. Then $\lnot$$L^2_{\kappa}$ is not provable in $L^2_{\kappa}$ either, so one can have $\endgroup$ – Thomas Benjamin Oct 23 '15 at 11:56
  • $\begingroup$ (cont.) models of full semantics in which either "$L^2_{\kappa}$ is $\kappa$-compact" or "$\lnot$$L^2_{\kappa}$ is $\kappa$-compact" holds. Is there some reason that " '$L^2_{\kappa}$ is ${\kappa}$-compact' is independent of $L^2_{\kappa}$" is not tenable? $\endgroup$ – Thomas Benjamin Oct 23 '15 at 12:06

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.