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 150 reputation by Noah Schweber
added 7 characters in body
Source Link
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

Below, by "logic" I mean "regular logic without equality;" see Badia/Caicedo/Noguera, Maximality of logic without identity.

Given a logic $\mathcal{L}$, a structure $\mathfrak{M}$, and an equivalence relation $E$ on $\mathfrak{M}$, say that $E$ is $\mathcal{L}$-equality-like iff for every $\mathcal{L}$-formula $\varphi(\overline{x})$ with parameters from $\mathfrak{M}$ and every pair of appropriate-length tuples of elements $\overline{a},\overline{b}$ of $\mathfrak{M}$ with $a_iEb_i$ for each $i$, we have $\varphi(\overline{a})^\mathfrak{M}\iff\varphi(\overline{b})^\mathfrak{M}$. Basically, $E$ is $\mathcal{L}$-equality-like iff it satisfies the substitution principle for $\mathcal{L}$-formulas with parameters.

Now an $\mathcal{L}$-equality-like relation is automatically a congruence, so we can consider quotients of structures by $\mathcal{L}$-equality-like relations. Say that a logic $\mathcal{L}$ is simple-for-equality iff $$(\mathfrak{M}, E)\equiv_\mathcal{L}(\mathfrak{M}/E,=)$$ for every structure $\mathfrak{M}$ and every $\mathcal{L}$-equality-like $E$ on $\mathfrak{M}$. Intuitively, $\mathcal{L}$ is simple-for-equality if the entire behavior of equality, as far as $\mathcal{L}$ is concerned, is captured by (the equivalence relation axioms and) the substutitution principle.

It isIt's easy to show that equality-free, while both full first-order logic $\mathsf{FOL_{w/o=}}$ isand its equality-free version are simple-for-equality, while its expansion $\mathsf{FOL_{w/o=}}(\exists!)$the intermediate logic gotten from the latter by adding the unique-existence quantifier is not simple-for-equality (see this earlier answer of mine)(see this earlier answer of mine). However, this is rather contrived since in some sense equality is already implicit in $\exists!$. My first question is whether there is a better example:

Question 1: Are there any "natural" logics which are not simple-for-equality?

My second question, in the opposite direction, is whether there are any more-standard 'tameness' properties of logics which entail simplicity-for-equality:

Question 2: Are there already-studied model-theoretic properties which imply that a logic is simple-for-equality (and so could explain a lack of natural examples)?

Below, by "logic" I mean "regular logic without equality;" see Badia/Caicedo/Noguera, Maximality of logic without identity.

Given a logic $\mathcal{L}$, a structure $\mathfrak{M}$, and an equivalence relation $E$ on $\mathfrak{M}$, say that $E$ is $\mathcal{L}$-equality-like iff for every $\mathcal{L}$-formula $\varphi(\overline{x})$ with parameters from $\mathfrak{M}$ and every pair of appropriate-length tuples of elements $\overline{a},\overline{b}$ of $\mathfrak{M}$ with $a_iEb_i$ for each $i$, we have $\varphi(\overline{a})^\mathfrak{M}\iff\varphi(\overline{b})^\mathfrak{M}$. Basically, $E$ is $\mathcal{L}$-equality-like iff it satisfies the substitution principle for $\mathcal{L}$-formulas with parameters.

Now an $\mathcal{L}$-equality-like relation is automatically a congruence, so we can consider quotients of structures by $\mathcal{L}$-equality-like relations. Say that a logic $\mathcal{L}$ is simple-for-equality iff $$(\mathfrak{M}, E)\equiv_\mathcal{L}(\mathfrak{M}/E,=)$$ for every structure $\mathfrak{M}$ and every $\mathcal{L}$-equality-like $E$ on $\mathfrak{M}$. Intuitively, $\mathcal{L}$ is simple-for-equality if the entire behavior of equality, as far as $\mathcal{L}$ is concerned, is captured by (the equivalence relation axioms and) the substutitution principle.

It is that equality-free first-order logic $\mathsf{FOL_{w/o=}}$ is simple-for-equality, while its expansion $\mathsf{FOL_{w/o=}}(\exists!)$ by the unique-existence quantifier is not simple-for-equality (see this earlier answer of mine). However, this is rather contrived since in some sense equality is already implicit in $\exists!$. My first question is whether there is a better example:

Question 1: Are there any "natural" logics which are not simple-for-equality?

My second question, in the opposite direction, is whether there are any more-standard 'tameness' properties of logics which entail simplicity-for-equality:

Question 2: Are there already-studied model-theoretic properties which imply that a logic is simple-for-equality (and so could explain a lack of natural examples)?

Below, by "logic" I mean "regular logic without equality;" see Badia/Caicedo/Noguera, Maximality of logic without identity.

Given a logic $\mathcal{L}$, a structure $\mathfrak{M}$, and an equivalence relation $E$ on $\mathfrak{M}$, say that $E$ is $\mathcal{L}$-equality-like iff for every $\mathcal{L}$-formula $\varphi(\overline{x})$ with parameters from $\mathfrak{M}$ and every pair of appropriate-length tuples of elements $\overline{a},\overline{b}$ of $\mathfrak{M}$ with $a_iEb_i$ for each $i$, we have $\varphi(\overline{a})^\mathfrak{M}\iff\varphi(\overline{b})^\mathfrak{M}$. Basically, $E$ is $\mathcal{L}$-equality-like iff it satisfies the substitution principle for $\mathcal{L}$-formulas with parameters.

Now an $\mathcal{L}$-equality-like relation is automatically a congruence, so we can consider quotients of structures by $\mathcal{L}$-equality-like relations. Say that a logic $\mathcal{L}$ is simple-for-equality iff $$(\mathfrak{M}, E)\equiv_\mathcal{L}(\mathfrak{M}/E,=)$$ for every structure $\mathfrak{M}$ and every $\mathcal{L}$-equality-like $E$ on $\mathfrak{M}$. Intuitively, $\mathcal{L}$ is simple-for-equality if the entire behavior of equality, as far as $\mathcal{L}$ is concerned, is captured by (the equivalence relation axioms and) the substutitution principle.

It's easy to show that, while both full first-order logic and its equality-free version are simple-for-equality, the intermediate logic gotten from the latter by adding the unique-existence quantifier is not (see this earlier answer of mine). However, this is rather contrived since in some sense equality is already implicit in $\exists!$. My first question is whether there is a better example:

Question 1: Are there any "natural" logics which are not simple-for-equality?

My second question, in the opposite direction, is whether there are any more-standard 'tameness' properties of logics which entail simplicity-for-equality:

Question 2: Are there already-studied model-theoretic properties which imply that a logic is simple-for-equality (and so could explain a lack of natural examples)?

Source Link
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

Is there a natural logic in which equality has this weird behavior?

Below, by "logic" I mean "regular logic without equality;" see Badia/Caicedo/Noguera, Maximality of logic without identity.

Given a logic $\mathcal{L}$, a structure $\mathfrak{M}$, and an equivalence relation $E$ on $\mathfrak{M}$, say that $E$ is $\mathcal{L}$-equality-like iff for every $\mathcal{L}$-formula $\varphi(\overline{x})$ with parameters from $\mathfrak{M}$ and every pair of appropriate-length tuples of elements $\overline{a},\overline{b}$ of $\mathfrak{M}$ with $a_iEb_i$ for each $i$, we have $\varphi(\overline{a})^\mathfrak{M}\iff\varphi(\overline{b})^\mathfrak{M}$. Basically, $E$ is $\mathcal{L}$-equality-like iff it satisfies the substitution principle for $\mathcal{L}$-formulas with parameters.

Now an $\mathcal{L}$-equality-like relation is automatically a congruence, so we can consider quotients of structures by $\mathcal{L}$-equality-like relations. Say that a logic $\mathcal{L}$ is simple-for-equality iff $$(\mathfrak{M}, E)\equiv_\mathcal{L}(\mathfrak{M}/E,=)$$ for every structure $\mathfrak{M}$ and every $\mathcal{L}$-equality-like $E$ on $\mathfrak{M}$. Intuitively, $\mathcal{L}$ is simple-for-equality if the entire behavior of equality, as far as $\mathcal{L}$ is concerned, is captured by (the equivalence relation axioms and) the substutitution principle.

It is that equality-free first-order logic $\mathsf{FOL_{w/o=}}$ is simple-for-equality, while its expansion $\mathsf{FOL_{w/o=}}(\exists!)$ by the unique-existence quantifier is not simple-for-equality (see this earlier answer of mine). However, this is rather contrived since in some sense equality is already implicit in $\exists!$. My first question is whether there is a better example:

Question 1: Are there any "natural" logics which are not simple-for-equality?

My second question, in the opposite direction, is whether there are any more-standard 'tameness' properties of logics which entail simplicity-for-equality:

Question 2: Are there already-studied model-theoretic properties which imply that a logic is simple-for-equality (and so could explain a lack of natural examples)?