I am getting two answer for this 1st order logic question.

Question

I had a doubt about a first order logic question given in this lecture which is a series on Discrete Mathematical structures from IIT.

If $x*y=x$ for all $y$, then $x=0$. You have to represent this in predicate logic. The universe of discourse is set of non-negative integers.

Let $P(x,y,z)$ represent: $x*y=z$

Answer given by the instructor is; $$∀x[∀y P(x,y,x) => x=0]$$ Which I understood and is true. But the answer I managed was: $$∃x[∀y P(x,y,x) ∧ x=0]$$ This also seems right.

Also if you expand the first assertion, $$∀x[∀y P(x,y,x) => x=0]$$ $$∀x[¬∀y P(x,y,x) ∨ x=0]$$ $$∀x ¬[∀y P(x,y,x) ∧ x≠0]$$ $$¬∃x[∀y P(x,y,x) ∧ x≠0]$$ Which is not the same as I managed but I am not able to figure out where I am wrong. Or are they both right?

My first question so sorry for any mistakes. Thanks!

Answer 1

If x*y=x for all y, then x=0

It is not directly mentioned here, but usually this means that the above should be true for all $x$, and not just for some $x$. Hence the answer from your instructor is the right one.

Answer 2

Your sentence

$$∃x[∀y P(x,y,x) ∧ x=0]$$

is saying that $0*y=0$ for all $y$. But the sentence you are looking for says that $0$ is the only possible value for $x$ for which $x*y=x$ for all $y$, i.e. that there aren't any non-zero values for $x$ for which $x*y=x$ . Notice that the latter is exactly:

$$¬∃x[∀y P(x,y,x) ∧ x≠0]$$

Also notice that this sentence does not even imply that $0*y=0$ for all $y$, which is good, since

If x*y=x for all y, then x=0.

does not imply either that $0*y=0$ for all $y$ (maybe the antecedent is always false!).

In other words, your sentence is at once too weak (it does not rule out anything other than $x=0$ to satisfy $x*y=x$ for all $y$), and too strong (it asserts that $0*y=0$ for all $y$, which is not asserted by the original sentence)

Your instructor's solution is correct though.