1
$\begingroup$

I need to understand the logic of below FOL statement. Can someone help?

$$ \forall x \exists y \forall z (z \neq y \iff f(x) \neq z) $$

Does this imply that x, y and z cannot be same or f(x) has no value?

$\endgroup$
  • 1
    $\begingroup$ Predicate logic questions might be better suited in the computer sceince SE. $\endgroup$ – solarflare Apr 15 at 5:42
3
$\begingroup$

The statement is

"for all $x$, there exists a value of $y$ such that for all $z$,
$z\neq y$ if and only if $z \neq f(x)$".

This can be simplified: $$\begin{align} & & \forall x \exists y \forall z (z\neq y \iff z \neq f(x))\\ &\implies & \forall x \exists y \forall z (z=y \iff z = f(x))\\ &\implies & \forall x \exists y \forall z (y = f(x))\\ &\implies & \forall x \exists y (y = f(x))\\ \end{align}$$

If we denote the set of all values of $x$ by $X$ and the set of all values of $y$ by $Y$, then this tells us that the function $f$ maps every $x$ in $X$ to a $y$ in $Y$. That is, $f: X \to Y$.

$\endgroup$
  • $\begingroup$ Thanks a lot Philip, I got that for each value of x there is a corresponding y mapping, will there be a case such that- 1. x,y,z cannot be same, 2. for each argument x, f(x) is unique, 3) y indicates that f(x) has no value .. $\endgroup$ – ammu Apr 20 at 4:54
  • 1
    $\begingroup$ No to all. The first two are more restrictive than the given statement. For 1, let f be the identity mapping. For 2, f could be a constant function. I'm assuming all variables share the same domain. 3 is in direct contradiction with the statement, which says that f(x) always has a value. $\endgroup$ – Philip Raeisghasem Apr 20 at 5:08
  • $\begingroup$ @ammu Don't forget to accept answers by clicking the check mark if they solved your problem. $\endgroup$ – Philip Raeisghasem Apr 20 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.