Skip to main content
Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Draw attention by Noah Schweber
Bounty Started worth 400 reputation by Noah Schweber
Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
edited body
Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

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}$$\mathcal{L}_{\omega_1,\omega}$ nor $\mathcal{L}_{\omega_2,\omega}$$\mathcal{L}_{\omega_2,\omega}$ is SED, the latterthe latter proof starting similarly to but being substantially harder than the formerthe 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?

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?

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?

Notice added Draw attention by Noah Schweber
Bounty Started worth 200 reputation by Noah Schweber
Source Link
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?