Proof involving quantifiers

Question

Prove or disprove: $(\forall x \in \mathbb Z) (\exists y \in \mathbb Z)(\forall z \in \mathbb N)(x + y \lt z)$

I am unsure on how to 'read' this statement. I would say take y = (z - x) - 1, then x + (z-x) - 1 < z, thus z < z + 1. But I don't feel comfortable with that 'proof'. Reading the statement I feel like y can only depend on x whilst I am making y depend on x and z.

Does anyone have tips on how to correctly 'read' statements like these? Thank you.

Answer 1

First consider the meaning of $(\forall z\in\Bbb N)(x+y<z)$: this says that $x+y<0$ and $x+y<1$ and $x+y<2$ and so on. Since each of these inequalities implies the next, we can say the same thing by saying just that $x+y<0$. Thus, we can rewrite the original simply as

$$(\forall x\in\Bbb Z)(\exists y\in\Bbb Z)(x+y<0)\;.\tag{1}$$

(If for you $\Bbb N$ does not include $0$, replace $0$ by $1$.) In words $(1)$ says that no matter what integer $x$ you choose, I can find an integer $y$ such that $x+y$ is negative. Can you find a simple function of $x$ that will produce such a $y$?

Answer 2

Your feeling is right, $y$ should not depend on $z$. The statement says that

For every integer $x$ there is an integer $y$ such that (for every natural number $z$ it holds that $x+y < z$).

You can think of statements involving quantifiers this way. Imagine you play a game with me. While reading the statement from left to right, we will do the following:

• Each time we encounter a universal quantifier (e.g. $``\forall x \in X"$) I will give you a value for that variable (which I will be free to choose however I like as far as it lies within the set $X$).
• Each time we encounter an existential quantifier (e.g. $``\exists x \in X"$) you are to give me a value for that variable (which you will be free to choose however you like as far as it lies within the set $X$).
• After we have done the above for every qualifier, we will substitute the chosen values to the rest of the statement. If the outcome is true, you win. If it isn't, you loose. Note that we are not allowed to change the values we initially chose for each variable.

If there is a way for you to win this game, no matter what choices I make, then the original statement is true. Else, the statement is false.

An example, using the statement you provided:

1. Say I choose $x=2$, you choose $y=3$, and I choose $z=10$. Then you win since $2+3<10$.
2. Say I choose $x=2$, you choose $y=3$, and I choose $z=4$. Then you loose since it doesn't hold that $2+3<4$.

The question is, given my $x$ can you choose your $y$ so that for every possible $z$ that I will give you in the third step of our game, you will be victorious? If and only if you can always do that, then the statement is true.

Answer 3

$(\forall x\in \mathbb Z)(\exists y\in \mathbb Z)(\forall z\in \mathbb N)(x+y<z)$

Translation: "For every integer there is an integer such that their sum is less than every natural number."

Since $0$ is the least natural number (for $\mathbb N\mathop{:=}^\text{def}\{0,1,\ldots\}$) then we equivalently need to show $(\forall x\in \mathbb Z)(\exists y\in \mathbb Z)(y<-x)$ or that "for every integer there exists an integer that is less than its negative."

As there is no least integer this follows immediately.