Skip to main content
1 of 2
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

Existing literature on logics "describing their own equivalence notions"

Say that a regular logic $\mathcal{L}$ is self-equivalence-describing (SED) iff for every finite language $\Sigma$ there is a larger language $\Sigma'$ containing at least $\Sigma$ and two new unary relation symbols $A,B$ and a $\mathcal{L}[\Sigma']$-sentence $\eta$ such that the following are equivalent for any pair of $\Sigma$-structures $\mathcal{A},\mathcal{B}$:

  • $\mathcal{A}\equiv_\mathcal{L}\mathcal{B}$.

  • There is a model $\mathcal{M}$ of $\eta$ such that $A^\mathcal{M}\cong\mathcal{A}$ and $B^\mathcal{M}\cong\mathcal{B}$.

For example, first-order logic is SED via Fraisse's theorem (this is a crucial point in the proof of Lindstrom's theorem), and in fact Fraisse's theorem also implies the SED-ness of second-order logic since - roughly speaking - powersethood is second-order definable and second-order equivalence corresponds to first-order equivalence of "powerstructures." On the other hand, infinitary first-order logics are usually not SED; Farmer S. has shown that neither $\mathcal{L}_{\omega_1,\omega}$ nor $\mathcal{L}_{\omega_2,\omega}$ is SED, the latter proof starting similarly to but being substantially harder than the former, and it seems that there is a decently strong negative result implicit in these arguments.

SED seems like a reasonable property to consider, but I haven't been able to find existing literature on the topic (although to be fair my literature search has largely been limited to the book Model-theoretic logics and its bibliography). So I would like to ask:

Are there any sources on (non-)SED-ness in the existing abstract-model-theoretic literature?

Here are some concrete-ish questions which I am interested in and suspect have been looked at already:

  • Which $\mathcal{L}_{\kappa,\omega}$s are SED? Which $\mathcal{L}_{\kappa,\kappa}$s are SED? What about infinitary second-order logics?

  • Are there any "natural" logics which are SED for reasons not having to do with Fraisse's theorem?

  • Is there (or when is there) a reasonably-natural way to take a non-SED logic $\mathcal{L}$ and construct a stronger logic $\mathcal{L}'$ which does have SED, or at least can characterize $\mathcal{L}$-equivalence with a single sentence?

Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331