# Predicate logic: Negate and prove

last day I faced a task, in which one has to negate and prove the following predicate: $$\forall x \in \mathbb {N} \exists y \in \mathbb {N} \exists z \in \mathbb {N} : x^2=y^2+z \wedge y \neq x$$ Thus the negated statement shall be: $$\exists x \in \mathbb {N} \forall y \in \mathbb {N} \forall z \in \mathbb {N}: x^2 \neq y^2 + z \vee y = x$$

Now for the proof part:

As far as I know, if one was able to find a number that contradicts this property, the whole statement would be false. Otherwise one shall prove the statement is true. What I'm confused about is the order and the way I can pick numbers to check the statement.

If there exists an $x$ so that for all $z$ and $y$ $x^2\neq y^2+z \vee y=x$ am I about to find at least one that makes it work for all y and z? For example I pick $x=5$ than $25 \neq y^2 + z \vee y=x$ But it doesn't obviously hold for all possible $y$ and $z$. But if I was able to find such $x$ that satisfies all $y$ and $z$ the property holds then, right?

And on the other hand I could interpret the statement as: for all $y$ and $z$ there is an $x$ such that $x^2 \neq y^2 + z \vee y = x$ and in this case i would pick an y and z first and show that there would be an x such that the property holds. But then it will always be an $x$ for that it holds.

I think the first approach makes more sense to me, but correct me please if I was wrong.

• You want to prove : $\exists x \forall y \forall z \ldots$. This means (as you say) : " there exists an x so that for all z and y ...". This is stornger than "for all y and z there is an x such that ...". – Mauro ALLEGRANZA Oct 7 '16 at 7:57

## 2 Answers

HINT: Take $x$ to be the smallest member of $\Bbb N$; is there a $y\in\Bbb N$ such that $y\ne x$ and $x^2=y^2+z$ for some $z\in\Bbb N$?

Your negation is fine.

If I would chose $x=0$, then basically there is no $y \in \mathbb{N}$ with $y \neq x$ for that the property holds, and therefore the statement is false.

Correct?