3
$\begingroup$

Previously asked and bountied on MSE without success:

Given a logic $\mathcal{L}$ and a signature $\Sigma$, let the $\Sigma$-system of $\mathcal{L}$ be the pair $Sys_\Sigma(\mathcal{L})=(Struc(\Sigma),\preccurlyeq_\mathcal{L})$ of $\Sigma$-structures partially ordered by the $\mathcal{L}$-elementary substructure relation. Say that a logic yields AECs iff its $\Sigma$-system is an AEC for every signature $\Sigma$; note that we only have to check the Tarski-Vaught and Lowenheim-Skolem axioms in this case. Examples of logics which yield AECs include first-order logic and the "small" infinitary logic $\mathcal{L}_{\omega_1,\omega}$, while the most natural examples of logics not yielding AECs in my opinion are second-order logic $\mathsf{SOL}$ and the "big" infinitary logic $\mathcal{L}_{\omega_1,\omega_1}$.

Quick caveat: note that the Lowenheim-Skolem axiom for AECs is stronger than what one might expect coming from non-AEC land. Also, the Tarski-Vaught axiom has nothing to do with the Tarski-Vaught test, so this question is unrelated to a couple previous questions of mine.

Now suppose we have a logic which doesn't yield AECs, but we want to find a reasonably large and canonically definable fragment of it which does. There's a trick which seems promising, at least as far as the Tarski-Vaught axiom goes. For a logic $\mathcal{J}$, let $\hat{\mathcal{J}}$ be the set of $\mathcal{J}$-formulas stable under elementary chains, that is, the set of $\varphi\in\mathcal{J}$ such that whenever $(\mathfrak{A}_i)_{i<\eta}$ are structures with $\mathfrak{A}_i\preccurlyeq_\mathcal{L}\mathfrak{A}_j$ for all $i<j<\eta$ we have $\varphi^{\mathfrak{A}_0}=\varphi^{\bigcup_{i<\eta}\mathfrak{A}_i}\cap\mathfrak{A}_0^{arity(\varphi)}$. Now given a logic $\mathcal{L}$ we can iterate this process through the ordinals, starting with $\mathcal{L}$ itself and taking intersections at limit stages as usual; we eventually hit a fixed point $\mathcal{L}^*$, and it's easy to show that $(i)$ for each $\Sigma$, if $Sys_\Sigma(\mathcal{L}^*)$ satisfies the Lowenheim-Skolem axiom then it is an AEC and $(ii)$ every sublogic of $\mathcal{L}$ which yields AECs is a sublogic of $\mathcal{L}^*$.

I'd like to know what happens to the two "bad" logics mentioned at the beginning:

Does $\mathsf{SOL}^*$ yield AECs? Does $\mathcal{L}_{\omega_1,\omega_1}^*$ yield AECs?

I strongly suspect the answer to the first question is negative: failures of the Lowenheim-Skolem axiom for $Sys_\emptyset(\mathsf{SOL})$ are easy to come by, e.g. there is a second-order sentence true in exactly those structures of infinite limit cardinality. However, while there are lots of such failures, each one I can think of goes away when we pass to $\mathsf{SOL}^*$. I'm much more ambivalent about $\mathcal{L}_{\omega_1,\omega_1}^*$. Tentatively I'll suspect that it does, but I have no good ideas here.


EDIT: A possible starting point is the following: do either $\mathsf{SOL}^*$ or $\mathcal{L}_{\omega_1,\omega_1}^*$ contain sentences not (equivalent to any sentence) in the tamer logic $\mathcal{L}_{\infty,\omega}$?

$\endgroup$
0
3
+200
$\begingroup$

It's been so long since I've seen a good AEC question on here! In fact, so long I forgot the account info that gives me enough reputation to post this as a comment.

I think this will get you rather close to an AEC (and in fact close to getting ALL AECs, if you start with $\mathbb{L}_{\kappa,\lambda}$).

To answer your starting point, all AECs I know* can be axiomatized by looking at some fragment of some $\mathbb{L}_{\kappa,\lambda}$ that has a finitary skolemization. For instance, the quantifier "there exists uncountably many" works so well because both $Qx\phi(x,y)$ and $\neg Qx \psi(x,y)$ can be expressed in this logic: \begin{eqnarray*} \exists \{x_\alpha : \alpha < \omega_1\} \left(\bigwedge_{\alpha<\omega_1}\phi(x_\alpha,y) \wedge \bigwedge_{\alpha<\beta<\omega_1} x_\alpha \neq x_\beta \right)\\ \exists\{x_n:n<\omega\} \left(\bigwedge_{n<\omega}\phi(x_n,y) \wedge \left( \forall z \left(\phi(z,y) \to \bigvee_{n<\omega} z=x_n \right)\right) \right) \end{eqnarray*}

Other AEC quantifiers can be done in this way as well. Moreover, looking at fragments and elementarity in $\mathbb{L}_{\omega_2, \omega_2}$ gives exactly the strong substructure for these AECs!

Also, this observation directly relates to your questions because any $\mathbb{L}_{\kappa,\lambda}$ theory with a finitary Skolemization will have the union property, and moreover is an AEC.

So what's missing still?

  1. From a "finding all AECs" perspective, there's a worry that you might have some AEC where the individual formulas are not in your construction, but you can combine them in some way to "cancel out" the poor interaction with unions.
  2. More importantly, it seems perfectly reasonable that having a Skolem function of infinite arity will break your union property (and I think I can prove something like this). So what exists between "finite arity Skolemization" and "infinite arity Skolemization?" What I've been calling (in my head) "essentially finite Skolemization," where the Skolem functions are either a) formally infinite arity, but each tuple is determined by some finite chunk or b) functions with domain $M^{<\omega}$.

Expanding on 2., notice these sorts of formulas satisfy your union property since each value is determined by some finite point in the union. Essentially what this means is that you have these Skolem functions, but you can limit the dependence of the Skolem functions by fiat, rather than just that they depend on everything (sort of like a branching quantifier). This is fantastic because you can jerry-rig some syntactic version of Shelah's Presentation Theorem with some infinitary versions of branching quantifiers.

The downside is that once you move to "essentially finitary Skolemization" or branching quantifiers, you do have this nice union property and downward Lowenheim-Skolem, but you actually lose coherence (the Tarski-Vaught Test axiom), so you don't get AECs. I don't actually have an example off the top of my head, but if you try to prove this, the problem becomes clear.

Finally, I've kind of been ignoring second-order. The reason for this is the notion of elementary submodel for second-order logic is unclear/doesn't behave like you might expect/want (or like I expect/want). There's a notion where you only look at formulas with free variables in the element sort and a version where you allow all sorts to be free but requires some more work (I talk about this second one in Section 4.3 of "Model-theoretic Characterizations of Large Cardinals"). Also, my prior is believing that all AECs turn out to be $\mathbb{L}_{\kappa,\lambda}$ axiomatizeable in this nice way, so maybe I'm just ignoring them out of spite...

$\endgroup$
3
  • $\begingroup$ This is really nice, thanks! FWIW the elementary substructurehood relation I had in mind for $\mathsf{SOL}$ was the free-object-variables-only one - this is because this is the $\mathsf{SOL}$-instance of the notion of elementary substructurehood applicable to all regular logics in the Ebbinghaus/Flum/Thomas/Barwise/etc. sense. (Finding "surprisingly tame" fragments of $\mathsf{SOL}$ is one of my major interests ... despite a complete lack of progress w/r/t same. :P) I may have some follow-up questions on this answer for which this comment thread wouldn't be ideal, do you mind if I email you? $\endgroup$ – Noah Schweber Apr 9 at 22:09
  • $\begingroup$ For sure! I actually tried to email you (about your other questions related to this quest), but the math.wisc.edu email bounced back. $\endgroup$ – Will Boney Apr 12 at 1:08
  • 1
    $\begingroup$ Good seeing you, Bill! $\endgroup$ – Asaf Karagila Apr 13 at 11:35

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.