Satisfiability of sentences with generic functions.

25 Views Asked by At

I can never get my head round proofs without specific functions.

Given the signature $\langle c,f\rangle$ where $c$ is a constant and $f$ is unary, prove the following:

a) $\forall x\, (c \neq f(x)) \not\models \forall x\, \forall y\, ( f(x)=f(y) \implies x=y)$

b) $\forall x\, (c \neq f(x)) \not\models \exists x\, \exists y\, ( f(x)=f(y) \land x=y)$

1

There are 1 best solutions below

0
On

HINT: Translating (a) into words helps considerably: it says that knowing that (the interpretation of) $c$ is not in the range of $f$ does not guarantee that (the interpretation of) $f$ is injective. This is pretty clearly true, and you should be able to find a model with two elements that satisfies $\forall x\,(c\ne f(x))$ and ‘$f$ is not injective’.

The second one is perhaps a little trickier. Again you need a model in which $c$ is not in the range of $f$, but this time there cannot be any element $x$ of the model such that $f(x)=f(x)$ and $x=x$. If there’s any element at all in the domain of $f$, it’s going to satisfy both of those equalities, so ... ?