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]

1 Answer

  • 9 years ago
    Favorite Answer

    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.

Still have questions? Get your answers by asking now.