This is a problem from the text An Introduction to Higher Mathematics (Exercises 1.4):

2 Using the integers as the universe of discourse, describe why the following are valid:

d) $~~\exists x>1 \forall y \exists z ~ ((y=xz) \lor (y=xz+1))$

I'm reading the sentence like: "There exists an $x$ greater than $1$ for all $y$, and for all $y$ there exists a $z$ such that $y=xz$ or $y=xz+1$."

In more normal English, I read: "y equals some number greater than 1 (x) times some relation of y (z), or that product plus 1."

As you can tell from my readings, I see that x is a fixed number and z can be a fixed number or some relation of y (like 2y). But I don't understand why the sentence is valid, and I can't understand what the sentence is trying to say in general, as I assume it's not just an arbitrary statement.

The only test that I can find that seems to work is $Let~x=2~and~z=y/x$, in which case the first operand expression always comes out true, and the latter seems trivial. Also, I'm not even sure if/how division is defined in the domain of integers.

Thanks for any help.

  • $\begingroup$ If $y$ is not prime it is the product of two factors $xz$, if it is prime it is odd, so you can find an even number $2z$ or $x2$ (and many others) such that the successive number is $y$. $\endgroup$
    – N74
    Commented Jun 24, 2017 at 6:17
  • $\begingroup$ I would read this (in a non-native speaker's English): There exists an integer $x>1$ such that given any integer $y$ we can find an integer $z$ such that either $y=xz$ or $y=xz+1$ holds. The question about having division of integers defined does not arise at all. As Yngwie Malmsteen said, $x=2$ works, so the sentence is true. $\endgroup$ Commented Jun 24, 2017 at 6:52
  • $\begingroup$ It's true, but I wouldn't call it valid ... in logic we typically say that a sentence is a valid sentence when it is true for all interpretations, i.e when it is a logical tautology. $\endgroup$
    – Bram28
    Commented Jun 24, 2017 at 15:55

1 Answer 1


Yes it is valid. If $x=2$, then $y$ being an integer implies that either $y$ is even or $y$ is odd, i.e. that either $y = xz$ for some integer $z$ or $y = xz+1$ for some integer $z$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .