Just having a last minute pre-exam panic, would be really grateful if someone could help me understand this question (I don't know why but maybe tiredness is stopping me from understanding??)

I'm asked to let $\phi$ be the following $\mathcal{L}$ sentence: $$\phi:\forall x\forall y\exists w\forall z((x\dot=y\land \lnot f(z)\dot =w)\lor (\lnot f(x) \dot=f(y) \land \lnot w \dot= f(z))$$

and express in ordinary mathematical terms what $\phi$ says about $f$.

I don't really understand: I get that given $x$ and $y$ we there is a $w$ such that for any $z$ either $x=y$ and $f(z)≠w$ or $f(x)≠f(y)$ and $f(z)≠w$.

But what actually does this tell me about $f$???


I assume the $\dot=$ is simply $=$?

If so, your statement becomes:

$$\forall x\forall y\exists w\forall z((x=y\land \lnot f(z) =w)\lor (\lnot f(x) =f(y) \land \lnot w = f(z))$$

which is equivalent to (since $\neg f(z)=w$ is equivalent to $\neg w = f(z)$)

$$\forall x\forall y\exists w\forall z((x=y\land \lnot f(z)=w)\lor (\lnot f(x) =f(y) \land \lnot f(z) = w)$$

which by Distribution is equivalent to:

$$\forall x\forall y\exists w\forall z((x=y \lor \lnot f(x) =f(y)) \land \lnot w = f(z))$$

and by the Prenex Laws that is equivalent to:

$$\forall x\forall y((x=y \lor \lnot f(x) =f(y)) \land \exists w\forall z \lnot w = f(z))$$

and that to:

$$\forall x\forall y(x=y \lor \lnot f(x) =f(y)) \land \exists w\forall z \lnot w = f(z)$$

So, you really have two parts to your statement:

$$\forall x\forall y(x=y \lor \lnot f(x) =f(y))$$

which is equivalent to:

$$\forall x\forall y(f(x) =f(y) \rightarrow x=y )$$

and that says that $f$ is injective, and the second part is:

$$\exists w\forall z \lnot w = f(z)$$

and that says that $f$ is not surjective (or onto)

So: $\phi$ says that $f$ is injective but not surjective.

  • $\begingroup$ yes the $\dot=$ is just the notation used at my university, it basically means $=$. Thanks very much for your answer. $\endgroup$
    – elDin0
    May 29 '17 at 21:37
  • $\begingroup$ @elDin0 You're welcome! :) $\endgroup$
    – Bram28
    May 29 '17 at 21:40

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.