# Functional completeness over a structure

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$$.

• Here is a very ad hoc idea that might be an example (I couldn’t actually figure out how to prove $\leftrightarrow$ is necessary, but it does seem like it should be): let $\Sigma$ consists of a constant symbol $0$ and two binary function symbols $f, g$. Let $\mathfrak{A}$ have infinite domain and $f, g$ be so chosen s.t.: 1. For each $x$, there are infinitely many $y \neq x$ s.t. $f(x, y) = 0$ and also infinitely many $y \neq x$ s.t. $f(x, y) \neq 0$; 2. For each $y$, there are infinitely many $x \neq y$ s.t. $f(x, y) = 0$ and also infinitely many $x \neq y$ s.t. $f(x, y) \neq 0$; … Commented Jul 7 at 5:04
• 3. Whenever $x, y$ is s.t. $x \neq y$, $f(x, y) = 0$, we have $g(x, y) = 0$; 4. Whenever $x, y$ is s.t. $x \neq y$, $f(x, y) \neq 0$, we have $g(x, y) \notin \{0, f(x, y)\}$; 5. There are infinitely many $x$ s.t. $f(x, x) = 0$ and also infinitely many $x$ s.t. $f(x, x) \neq 0$; 6. Whenever $x$ is s.t. $f(x, x) = 0$, we have $g(x, x) \neq 0$, and $\{g(x, x): f(x, x) = 0\}$ is infinite; 7. Whenever $x$ is s.t. $f(x, x) \neq 0$, we have $g(x, x) = 0$… Commented Jul 7 at 5:08
• Another good example of this concept is any field $F$ whose theory is model-complete in the language of rings (like $\mathbb{R}$ or $\mathbb{C}$). By model-completeness, any formula is equivalent over $F$ to an existential formula. Now inside the quantifier-free part, we can push the negations inside to the atomic formulas, and then replace $\lnot (p(x)=q(x))$ by $\exists y\,(y(p(x)-q(x))=1)$. So $\{\exists,\land,\lor,=\}$ is sufficient for first-order definability. Commented Jul 7 at 12:39
• @AlexKruckman You can do better: in any field, every existential formula is equivalent to a pp formula (i.e. $\{\exists,\land,=\}$), and if the field does not include the algebraic closure of the prime field (or of a larger field from which you are allowed to take parameters), to an existentially quantified identity ($\{\exists,=\}$). Thus, $\{\exists,\land,=\}$ and $\{\exists,=\}$ are sufficient for FO definability in algebraically closed and real-closed fields, respectively. Commented Jul 8 at 5:41
• You use $f=0\lor g=0\equiv fg=0$, and $f=0\land g=0\equiv h(f,g)=0$, where $h(x,y)$ is the homogeneous polynomial $y^dh_0(x/y)$ for $h_0(x)$ a polynomial without a root of degree $d\ge1$. Commented Jul 8 at 5:46

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.

• Great, thanks! (I can't award the bounty yet, some time limit - I think 24 hours? - has to pass first.) Commented Jul 12 at 2:22