I thought about this question as a result of the following exercise in logic:
Consider the following 4 formulae in first order logic:
- $\forall x(xx=x)$ (idempotency)
- $\forall x\forall y(xy=yx)$ (commutativity)
- $\forall x \forall y \forall z((xy)z=x(yz))$ (associativity)
- $\forall x \forall y \forall z ((xx=xz \land yy=yz) \rightarrow xx=zx)$ (not sure what this means)
Notice that $xy$ is short for $x*y$ here.
Prove or disprove: (in regards to structures that interpret equality normally)
- $\phi_1,\phi_2,\phi_3 \vdash_{FOL}\phi_4$
- $\phi_1, \phi_2, \phi_4 \vdash_{FOL} \phi_3$
As for 1, I managed to prove it after quite some hard work using Herbrand's theorem. I wonder if there's an easier way?
But my main question is about disproving the second claim. Consider the following signature: $\sigma \cong \{0, s(x), =, * \}$. I thought about the following structure over $\sigma$: $M=<D,I>$ where $D=\mathbb{N}$ and we define $I$ the interpretation function as follows:
$I[=] \cong \{x,x|x\in\mathbb{N}\}$ i.e. we interpret equality the "standard way". $I[*] \cong \lambda x,y.(x+y)/2$ i.e. we interpret the binary operation as the average function between the operands. Also $I[0] \cong 0$ and $I[s] \cong \lambda x.x+1$ i.e. the standard constant zero and successor function.
Now, this question was rather interesting because it took me a long time to find a counter-example, specifically an operation. This disproves the claim because $M\models \phi_1, \phi_2, \phi_4$ but $M \not\models \phi_3$, that is quite easy to see because of properties of average.
Now for the main part: I am having doubts this actually disproves the claim, because average is not closed under positive integers, so maybe this entire definition was problematic: for example $(3+4)/2 \not\in \mathbb{N}$ so maybe this means the entire function interpretation was illegal? And we had to instead define $D^M \cong \mathbb{Q}$? As in, the domain should've been the rationals. So if anyone could tell me if this was O.K. I would really appreciate it. If not, I would appreciate a counter example over $D^M \cong \mathbb{N}$. Also, I am still very much wondering about the meaning of the fourth formula.
Answers to anyone of these questions would be greatly appreciated!