# Discrete Math quantified formulae?

State whether the following quantified formulae are true over the natural numbers.

ℕ = {1.2.3……}:

i) ∃x ∀y ∀ z[(x > y^2 + z^2) →(y > z)]

ii) ∀x ∃y ∀ z[(z^2 < y +x^2) →(x > z)]

iii) ∃u ∀v ∃w ∀x [ux < vw]

Relevance
• 9 years ago

i) ∃x ∀y ∀z [(x > y^2 + z^2) →(y > z)]

This seems counter-intuitive. If

x > y^2 + z^2

then we could interchange the values of z and y, and it would still be true. But if

y > z is true, then interchanging those values will make it false.

But we're looking for just one value of x for which the statement holds for any y and z.

Remember that a statement of the form

p → q

is always true if p is always false, regardless of whether q is true or false.

In this case, there IS a value of x for which, as long as we stick to the natural numbers,

x > y^2 + z^2

is false for any y and z. That value is x=1. The quantified formula only asserts that there is one such value, so it's true over the natural numbers.

ii) ∀x ∃y ∀z [(z^2 < y +x^2) →(x > z)]

Regardless of what x is, we have to cover all values of z including z=x, and there is no possible value for y among the natural numbers such that

x^2 < y + x^2 is false or

x > x is true.

This formula is not true over the natural numbers.

[It is, however, true over the integers, because then we could choose

y = -x^2

for any x, thus ensuring that

z^2 < y + x^2

is false for any z.]

iii) ∃u ∀v ∃w ∀x [ux < vw]

We can quickly show this doesn't hold:

ux < vw

x < vw/u [because u is a natural number and cannot be zero or negative]

and there is no combination of u, v, and w for which that statement can be true for all x.

This formula is not true over the natural numbers.