Let $f$ be a function symbol. Which of these statements are equivalent to each other?

Question

The statements are:

1. $\forall x \exists y(fx = y)$
2. $\forall x \exists x(fx = x)$
3. $\exists x(fx = x)$

I know that two statements $\alpha, \beta$ are equivalent iff $I \vDash (\alpha)\equiv (\beta)$ for every interpretation $I.$

It might be wise trying to prove $I \vDash (\alpha) \rightarrow (\beta)$ and $I \vDash (\alpha) \leftarrow (\beta)$ seperately.

But how do I do that?

Obviously, the first statement doesn't imply the second, whereas the second statement does indeed imply the first. The second statement describes a constant function, whereas the first statement describes a function in general. Of course every constant function is a function, but not the other way around. But I don't think that this is a proper answer.

Answer 1

2 and 3 are cleary equivalent, because there is no $x$ free into $∃x(fx=x)$.

Using the quantifier axiom $\forall x \varphi \to \varphi(t/x)$, we have that $\forall x \varphi \vdash \varphi$.

And from Generalization Theorem we have that :

if $x$ is not free in $\varphi$, then $\varphi \vdash \forall x \varphi$.

For a formal proof of $\vdash \varphi \leftrightarrow \forall x \varphi$, when $x$ is not free in $\varphi$, we need the specification of the proof system : Natural Deduction, etc.

A "semantical" proof needs the details regarding the semantical specifications: e.g. $M \vDash \forall x \varphi$ iff $M \vDash \varphi[m/x]$, for every $m \in M$.

Thus, $M \vDash \forall x \exists x (fx=x)$ iff $M \vDash \exists x (fx=x)[m/x]$, for every $m \in M$.

But $x$ is not free in $\exists x (fx=x)$ and thus $\exists x (fx=x)[m/x] = \exists x (fx=x)$.

---

1 and 3 are not: we can find a counterexample in $\mathbb N$ interpreting $f$ as the successor function.

We have that : $\mathbb N \vDash ∀x∃y(s(x)=y)$ but clearly $\mathbb N \nvDash ∃x(s(x)=x)$.