Skip to main content
English correction
Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

Say that a finitely axiomatizable first-order theory $T$ (in a finite language $\Sigma$) is persistently finitely axiomatizable iff the set $T_{\mathsf{w/o=}}$ of equality-free $T$-theorems is finitely axiomatizable in first-order logic without equality.

Building off ofon this earlier question, I would like to ask:

Is there a finitely axiomatizable relational theory which is not persistently finitely axiomatizable?

Here are the only two relevant facts I currently know:

  • One natural attempt for proving a negative answer is the following. Let $$I(x,y)\equiv\bigwedge_{R\in \Sigma} \forall \overline{u},\overline{v}(R(\overline{u},x,\overline{v})\leftrightarrow R(\overline{u},y,\overline{v})).$$ Then we might expect to have $\vdash A\leftrightarrow A_I$ for all first-order sentences $A$, where $A_I$ is gotten from $A$ by replacing "$s=t$" with "$I(s,t)$" throughout. However, this breaks down: consider e.g. $A\equiv \exists x,y(x=y\wedge \neg I(x,y))$. (This counterexample was pointed out by Emil Jerabek.)

  • If we allow function symbols we get a positive answer; this was observed by Rodrigo Freire, answering the above-linked original question.

Say that a finitely axiomatizable first-order theory $T$ (in a finite language $\Sigma$) is persistently finitely axiomatizable iff the set $T_{\mathsf{w/o=}}$ of equality-free $T$-theorems is finitely axiomatizable in first-order logic without equality.

Building off of this earlier question, I would like to ask:

Is there a finitely axiomatizable relational theory which is not persistently finitely axiomatizable?

Here are the only two relevant facts I currently know:

  • One natural attempt for proving a negative answer is the following. Let $$I(x,y)\equiv\bigwedge_{R\in \Sigma} \forall \overline{u},\overline{v}(R(\overline{u},x,\overline{v})\leftrightarrow R(\overline{u},y,\overline{v})).$$ Then we might expect to have $\vdash A\leftrightarrow A_I$ for all first-order sentences $A$, where $A_I$ is gotten from $A$ by replacing "$s=t$" with "$I(s,t)$" throughout. However, this breaks down: consider e.g. $A\equiv \exists x,y(x=y\wedge \neg I(x,y))$. (This counterexample was pointed out by Emil Jerabek.)

  • If we allow function symbols we get a positive answer; this was observed by Rodrigo Freire, answering the above-linked original question.

Say that a finitely axiomatizable first-order theory $T$ (in a finite language $\Sigma$) is persistently finitely axiomatizable iff the set $T_{\mathsf{w/o=}}$ of equality-free $T$-theorems is finitely axiomatizable in first-order logic without equality.

Building on this earlier question, I would like to ask:

Is there a finitely axiomatizable relational theory which is not persistently finitely axiomatizable?

Here are the only two relevant facts I currently know:

  • One natural attempt for proving a negative answer is the following. Let $$I(x,y)\equiv\bigwedge_{R\in \Sigma} \forall \overline{u},\overline{v}(R(\overline{u},x,\overline{v})\leftrightarrow R(\overline{u},y,\overline{v})).$$ Then we might expect to have $\vdash A\leftrightarrow A_I$ for all first-order sentences $A$, where $A_I$ is gotten from $A$ by replacing "$s=t$" with "$I(s,t)$" throughout. However, this breaks down: consider e.g. $A\equiv \exists x,y(x=y\wedge \neg I(x,y))$. (This counterexample was pointed out by Emil Jerabek.)

  • If we allow function symbols we get a positive answer; this was observed by Rodrigo Freire, answering the above-linked original question.

Bumped by Community user
Bumped by Community user
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
Source Link
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

Persistent finite axiomatizability, relational edition

Say that a finitely axiomatizable first-order theory $T$ (in a finite language $\Sigma$) is persistently finitely axiomatizable iff the set $T_{\mathsf{w/o=}}$ of equality-free $T$-theorems is finitely axiomatizable in first-order logic without equality.

Building off of this earlier question, I would like to ask:

Is there a finitely axiomatizable relational theory which is not persistently finitely axiomatizable?

Here are the only two relevant facts I currently know:

  • One natural attempt for proving a negative answer is the following. Let $$I(x,y)\equiv\bigwedge_{R\in \Sigma} \forall \overline{u},\overline{v}(R(\overline{u},x,\overline{v})\leftrightarrow R(\overline{u},y,\overline{v})).$$ Then we might expect to have $\vdash A\leftrightarrow A_I$ for all first-order sentences $A$, where $A_I$ is gotten from $A$ by replacing "$s=t$" with "$I(s,t)$" throughout. However, this breaks down: consider e.g. $A\equiv \exists x,y(x=y\wedge \neg I(x,y))$. (This counterexample was pointed out by Emil Jerabek.)

  • If we allow function symbols we get a positive answer; this was observed by Rodrigo Freire, answering the above-linked original question.