Functional completeness over a structure

Question

The set of propositional connectives $\{\wedge,\vee\}$ is of course not functionally complete; correspondingly, the logical vocabulary $\{\forall,\exists,=,\wedge,\vee\}$ is not sufficient for developing all of first-order logic. However, the situation is different over the natural numbers in the following sense:

Every first-order formula $\varphi(\overline{x})$ in the language of arithmetic is equivalent, in terms of the relation it defines in the structure $(\mathbb{N};+,\times,0,1)$, to one in which the only logical symbols occurring are $\forall,\exists,\wedge,\vee$, and $=$.

Proof: By "pushing negations inside" and replacing $\neg s=t$ with $\exists x(x+1+s=t \vee x+1+t=s)$. Note that even though we only need $\vee$ for handling inequalities, the process of pushing negations inside will introduce $\wedge$s even if the original formula only contained $\vee$s (and will similarly flip quantifiers), so we can't do better than the set $\{\forall,\exists,=,\wedge,\vee\}$ via this argument - and indeed it's not hard (if rather tedious) to show that this is optimal.

In general, I'm not very familiar with results focusing on the Boolean aspects of first-order formulas. The following seems like a fun test question:

Question: Is there a first-order structure $\mathfrak{A}$ in a finite language $\Sigma$ over which $\{\wedge,\vee,\leftrightarrow\}$ is functionally complete but $\{\wedge,\vee\}$ isn't?

Precisely: it should be the case that

• every formula $\varphi(\overline{x})$ is equivalent over $\mathfrak{A}$ (= defines the same relation on $\mathfrak{A}$ as) some formula $\psi(\overline{x})$ using only the logical symbols $\{\forall,\exists,=,\wedge,\vee,\leftrightarrow\}$, but

• the previous bulletpoint fails if we don't include $\leftrightarrow$.

Answer 1

This is basically the idea I proposed in comments, coupled with the OP's own suggestion to consider quotient structures:

Let $\Sigma = \{0, f, g\}$ where $0$ is a constant symbol and $f, g$ are binary function symbols. Let $\mathcal{A}$ be the structure with underlying set $\mathbb{N}$. Let $0^\mathcal{A} = 0$ and $f^\mathcal{A}$ be defined by,

$$f^\mathcal{A}(x, y) = \begin{cases} 0 &, \text{ if }x = y\text{ is even}\\ x &, \text{ if }x = y\text{ is odd}\\ \max\{x, y\} &, \text{ if }x \neq y\text{ and both }x, y\text{ are even}\\ x &, \text{ if }x\text{ is odd and }y\text{ is even}\\ y &, \text{ if }x\text{ is even and }y\text{ is odd}\\ \min\{x, y\} &, \text{ if }x \neq y\text{ and both }x, y\text{ are odd} \end{cases}$$

Let $g^\mathcal{A}$ be defined by, $$g^\mathcal{A}(x, y) = \begin{cases} 1 &, \text{ if }x = y\text{ is even}\\ 0 &, \text{ if }x = y\text{ is odd}\\ 1 &, \text{ if }x \neq y\text{ and both }x, y\text{ are even}\\ x &, \text{ if }x\text{ is odd and }y\text{ is even}\\ y &, \text{ if }x\text{ is even and }y\text{ is odd}\\ \max\{x, y\} &, \text{ if }x \neq y\text{ and both }x, y\text{ are odd} \end{cases}$$

Then the equivalence relation $\sim$ defined by $[0]_\sim = [2]_\sim =\{0, 2\}$ and $[n]_\sim = \{n\}$ for $n \neq 0, 2$ is a congruence relation. Indeed,

$$\begin{split} f^\mathcal{A}(0, 0) = 0 &\sim 2 = f^\mathcal{A}(2, 0)\\ f^\mathcal{A}(0, 2) = 2 &\sim 0 = f^\mathcal{A}(2, 2)\\ f^\mathcal{A}(0, x) = x &\sim x = f^\mathcal{A}(2, x) \; \text{if }x \neq 0, 2\\ f^\mathcal{A}(0, 0) = 0 &\sim 2 = f^\mathcal{A}(0, 2)\\ f^\mathcal{A}(2, 0) = 2 &\sim 0 = f^\mathcal{A}(2, 2)\\ f^\mathcal{A}(x, 0) = x &\sim x = f^\mathcal{A}(x, 2) \; \text{if }x \neq 0, 2\\ g^\mathcal{A}(0, x) = 1 &\sim 1 = g^\mathcal{A}(2, x) \; \text{if }x\text{ is even}\\ g^\mathcal{A}(0, x) = x &\sim x = g^\mathcal{A}(2, x) \; \text{if }x\text{ is odd}\\ g^\mathcal{A}(x, 0) = 1 &\sim 1 = g^\mathcal{A}(x, 2) \; \text{if }x\text{ is even}\\ g^\mathcal{A}(x, 0) = x &\sim x = g^\mathcal{A}(x, 2) \; \text{if }x\text{ is odd} \end{split}$$

Thus, $\mathcal{A}/\sim$ is a well-defined $\Sigma$-structure. I claim that $\mathcal{A} \simeq \mathcal{A}/\sim$. Indeed, let $\pi: \mathcal{A} \to \mathcal{A}/\sim$ be defined by,

$$\pi(x) = \begin{cases} [0]_\sim &, \text{ if }x = 0\\ [x + 2]_\sim &, \text{ if }x \geq 2\text{ and }x\text{ is even}\\ [x]_\sim &, \text{ if }x\text{ is odd} \end{cases}$$

One easily verify that $\pi$ is a bijection. $\pi(0^\mathcal{A}) = [0]_\sim = 0^{\mathcal{A}/\sim}$. Moreover,

$$f^{\mathcal{A}/\sim}(\pi(x), \pi(y)) = \begin{cases} [0]_\sim &, \text{ if }x = y\text{ is even}\\ [x]_\sim &, \text{ if }x = y\text{ is odd}\\ [y + 2]_\sim = \pi(\max\{x, y\}) &, \text{ if }x = 0\text{ and }y \geq 2\text{ is even}\\ [x + 2]_\sim = \pi(\max\{x, y\}) &, \text{ if }y = 0\text{ and }x \geq 2\text{ is even}\\ [\max\{x + 2, y + 2\}]_\sim = \pi(\max\{x, y\}) &, \text{ if }x \neq y; \, x, y \geq 2; \text{ and both }x, y\text{ are even}\\ [x]_\sim &, \text{ if }x\text{ is odd and }y\text{ is even}\\ [y]_\sim &, \text{ if }x\text{ is even and }y\text{ is odd}\\ [\min\{x, y\}]_\sim &, \text{ if }x \neq y\text{ and both }x, y\text{ are odd} \end{cases}$$

Matching the definition case-by-case, we see that $f^{\mathcal{A}/\sim}(\pi(x), \pi(y)) = \pi(f^\mathcal{A}(x, y))$. For $g$,

$$g^{\mathcal{A}/\sim}(\pi(x), \pi(y)) = \begin{cases} [1]_\sim &, \text{ if }x = y\text{ is even}\\ [0]_\sim &, \text{ if }x = y\text{ is odd}\\ [1]_\sim &, \text{ if }x \neq y\text{ and both }x, y\text{ are even}\\ [x]_\sim &, \text{ if }x\text{ is odd and }y\text{ is even}\\ [y]_\sim &, \text{ if }x\text{ is even and }y\text{ is odd}\\ [\max\{x, y\}]_\sim &, \text{ if }x \neq y\text{ and both }x, y\text{ are odd} \end{cases}$$

Matching the definition case-by-case, we see also that $g^{\mathcal{A}/\sim}(\pi(x), \pi(y)) = \pi(g^\mathcal{A}(x, y))$. Hence, $\pi$ is an isomorphism.

Finally, in $\mathcal{A}$, we observe that, $x \neq y$ is equivalent to,

$$f(x, y) = 0 \leftrightarrow g(x, y) = 0$$

Because there are no relation symbols in $\Sigma$, the same argument showing every formula is equivalent to one using only $\{\forall, \exists, =, \wedge, \vee\}$ over $(\mathbb{N}; +, \times, 0, 1)$ shows every formula is equivalent to one using only $\{\forall, \exists, =, \wedge, \vee, \leftrightarrow\}$ over $\mathcal{A}$. However, $\leftrightarrow$ is necessary. Indeed, assume to the contrary that $x \neq y$ is equivalent to some $\varphi(x, y)$ over $\mathcal{A}$, where $\varphi$ uses only $\{\forall, \exists, =, \wedge, \vee\}$. As $0 \neq 2$, we have $\varphi^\mathcal{A}(0, 2)$. Any formula using only $\{\forall, \exists, =, \wedge, \vee\}$ is preserved after taking quotients, which can be easily verified by an induction. Thus, $\varphi^{\mathcal{A}/\sim}([0]_\sim, [2]_\sim)$. But $\mathcal{A} \simeq \mathcal{A}/\sim$, so over $\mathcal{A}/\sim$, $x \neq y$ is also equivalent to $\varphi(x, y)$. Thus, $[0]_\sim \neq [2]_\sim = [0]_\sim$, which is a contradiction.