4
$\begingroup$

(Note that the logic systems described in this question only refer to logic systems restricted to the language $\in$)

1. Can $\mathcal{L}_{\kappa,\kappa}$ express $n$-th order finitary logic? It is clear that it can express first-order logic ($\Pi_{<\omega}^0$), but it seems unlikely that $\mathcal{L}_{\kappa,\kappa}$ can express even $\Pi_{<\omega}^1$.

By the answer to this question: Gödel's Constructible Universe in Infinitary Logics (A Possible Approach to HOD Problem), it is known that $L^{\Pi_{<\omega}^1}=HOD$. Assuming $\mathcal{L}_{\kappa,\kappa}$ expresses $\Pi_{<\omega}^1$, it is then not difficult to show that $HOD\subseteq L^{\mathcal{L}_{\kappa,\kappa}}\subseteq L(V_\kappa)$. Thus, unless $L(V_\kappa)=V$ (which is true iff $L=V$), $V\neq HOD$.

Therefore, the existence of such a $\kappa$ is inconsistent with $V\neq L\land V=HOD$. This is very doubtful.

2. Can $\mathcal{L}_{\kappa,\kappa}$ express $\Pi_n^1$ for $n>0$? For $n=0$, it is once again easy to see that, yes, this is true ($\Pi_0^1=\Pi_0^0$) for every $\kappa$. Other than this, I have no information for this question.

$\endgroup$
  • $\begingroup$ Are you sure you've written what you meant to? Note that since you've put the "there is a formula" after all the "for all"s, everything you've said collapses, and your definition amounts to: "For every $S\subseteq U^{<\omega}$there is an $\mathcal{L}_{\kappa\kappa}$-formula $\varphi$ such that for every finite sequence $\nu$ we have $\varphi(\nu)\iff \nu\in S$." Maybe you want to put some sort of requirement on what $T$ can be? $\endgroup$ – Noah Schweber Nov 2 '17 at 3:29
  • $\begingroup$ Yes, obviously. Sorry, my mistake. $\endgroup$ – Keith Millar Nov 2 '17 at 3:42
  • $\begingroup$ It doesn't look to me like you've fixed this ... $\endgroup$ – Noah Schweber Nov 2 '17 at 23:05
  • $\begingroup$ @NoahSchweber I was a little busy, sorry. Here I have fixed it. $\endgroup$ – Keith Millar Nov 3 '17 at 2:28
10
$\begingroup$

The answer is no.

Suppose that $\kappa$ is a Mahlo cardinal. This is $\Pi^1_1$ expressible in $V_\kappa$, since it amounts to the assertion that every closed unbounded subset of $\kappa$ contains a regular cardinal. But it cannot be expressible by an assertion of $\mathcal{L}_{\kappa,\kappa}$, since there is a forcing extension $V[G]$ in which $V_\kappa$ is preserved, but which destroys the Mahloness of $\kappa$. Since $V_\kappa$ is preserved, the truth of any $\mathcal{L}_{\kappa,\kappa}$ assertion is invariant by the forcing, but the Mahloness of $\kappa$ is not.

One can make other similar kinds of examples. For example, "$\kappa$ is regular" is expressible in $V_\kappa$ by a $\Pi^1_1$ assertion, but it cannot be provably equivalent to any $\mathcal{L}_{\kappa,\kappa}$ assertion, since for example with a measurable cardinal, this can be changed by forcing without changing $V_\kappa$.

Here is another way to argue, without forcing. Let $\kappa$ be an inaccessible cardinal. The assertion that $\kappa$ is regular is $\Pi^1_1$ expressible in $V_\kappa$. If we fix a $\mathcal{L}_{\kappa,\kappa}$ truth predicate for $V_\kappa$, we can find many $\gamma<\kappa$ with $V_\gamma\prec_{\mathcal{L}_{\gamma,\gamma}}V_\kappa$. In particular, there will be such $\gamma$ of cofinality $\omega$ above the size of any particular $\varphi$ in $\mathcal{L}_{\kappa,\kappa}$. So $V_\gamma$ and $V_\kappa$ will agree on the truth of $\varphi$, but not on the assertion that the ordinals are regular.

I believe that one can likely press this further to make an example in ZFC, without any large cardinals.

$\endgroup$
  • 3
    $\begingroup$ For a ZFC example, what about the following: let $\lambda$ be a limit cardinal of cofinality $>\kappa^+$, and look at a generic extension $V[G]$ in which $cof(\lambda)=\kappa^+$ but $V[G]$ has no new $\kappa$-sequences of elements of $\lambda$. Then since "$cof(\alpha)=\beta$" is $\Pi^1_1$ over $V_\alpha$ with a parameter for $\beta$, and $\mathcal{L}_{\kappa\kappa}$-truth in a structure depends only on the length-$\kappa$ sequences of elements, we have a contradiction. Does this work? $\endgroup$ – Noah Schweber Nov 3 '17 at 16:31
  • 1
    $\begingroup$ In the non-forcing example, why can we find $\gamma$ with $V_\gamma \preceq_{\mathcal{L}_{\kappa \kappa}} V_\kappa$? For every $\alpha < \kappa$ there is a formula asserting $\alpha$ exists. We really want to fix a small fragment in which the formula $\phi$ lies. $\endgroup$ – Douglas Ulrich Nov 3 '17 at 16:39
  • 1
    $\begingroup$ @DouglasUlrich Yes, thannks. I had meant $V_\gamma\prec_{\mathcal{L}_{\gamma,\gamma}} V_\kappa$. For $\gamma$ large enough, this includes any $\varphi$ in $\mathcal{L}_{\kappa,\kappa}$. I have now editted to correct this. $\endgroup$ – Joel David Hamkins Nov 3 '17 at 16:44
  • 1
    $\begingroup$ @NoahSchweber That seems to work. $\endgroup$ – Joel David Hamkins Nov 3 '17 at 16:48

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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