5

Does FOL augmented with the two-variable Härtig quantifier $\text{FOL}[(\text{I}2)]$ produce a more expressive logic than FOL with the ordinary Härtig quantifier $\text{FOL}[\text{I}]?$

I will use $I$ to denote the Härtig quantifier. If $x$ is a variable and $\varphi(x)$ and $\psi(x)$ are well-formed formulas that possibly depend on $x$, then the following holds.

$$ (I_x)(\varphi(x), \psi(x)) \;\;\text{is a well-formed formula} $$

And its truth conditions

$$ M \vDash (I_x)(\varphi(x),\psi(x)) \;\;\text{iff}\;\; \bigg|\{x \mathop| x \in M \;\text{and}\; \varphi(x)\}\bigg| \;\text{is equal to}\; \bigg|\{ x \mathop| x \in M \;\text{and}\; \psi(x) \} \bigg| $$

I'll also define the two-variable Härtig quantifier as follows.

$$ (I_{xy})(\varphi(x, y), \psi(x, y)) \;\; \text{is a well-formed formula} $$

$$ M \vDash (I_{xy})(\varphi(x, y), \psi(x, y)) \\ \textbf{if and only if} \\ \bigg|\{(x, y) \mathop| x \in M \land y \in M \land \varphi(x, y) \}\bigg| \;\; \text{is equal to}\;\; \bigg|\{(x, y) \mathop| x \in M \land y \in M \land \psi(x, y) \} \bigg| $$

A sentence in $\text{FOL}[\text{I}]$ can clearly be rewritten into an equivalent statement in $\text{FOL}[(\text{I}2)]$.

$$ (I_{x})(\varphi(x), \psi(x)) \;\;\text{is equivalent to}\;\; (I_{xy})(\,(\varphi(x) \land x=y), (\psi(x) \land x=y)\,) $$

In the other direction though, I'm really not sure whether $\text{FOL}[(\text{I}_2)]$ is as expressive as or more expressive than $\text{FOL}[\text{I}]$.

It's easy to form an intuitive argument for why $\text{FOL}[\text{more}]$ is as expressive as or more expressive than $\text{FOL}[\text{I}]$. This answer contains a more detailed proof of this fact.

Greg Nisbet
  • 11,657
  • 3
    FOL[I] can express that $M$ is infinite as $\exists y (I_x)(\top,x\neq y)$. – Eric Wofsey Mar 19 '21 at 04:11
  • I removed my addendum that $(I_{xy})(x=y, x\ne y)$ holds when $M$ is infinite but lacks function or predicate symbols because having such a sentence isn't unique to $\text{FOL}[\text{I}2]$. Thanks. That example sentence is great please keep the comment around. – Greg Nisbet Mar 19 '21 at 04:17

0 Answers0