Introductory Proofs Writing Class - Prove $(\forall x\in\mathbb Z)(\exists y\in\mathbb Z)(2x<y)$

Question

Prove the following statement is true:

$$(\forall x\in\mathbb Z)(\exists y\in\mathbb Z)(2x<y)$$

It's quite obvious by thinking about it that the statement is true, but I can not figure out a way to write a proof for it. Any help?

Answer 1

Pick any $x \in \mathbb{Z}$ and consider $2x$, which is also an integer.

Your job now is to find an integer $y$ for which $2x < y$; in this case, $y = 2x+1$ will work, since (noting the integers are closed under addition) this $y \in \mathbb{Z}$, and clearly $2x < 2x + 1$.

Note how the structure of a "for all - there exists" proof arises: We began by picking an arbitrary number, $x$, that satisfies the given condition (i.e., that it is an integer), and we continued by demonstrating the existence component by producing an example $y$ value, which depends on $x$, and which satisfies its own constraints (i.e., that it is an integer that is greater than $2x$).

Answer 2

Nobody ever really explains this, but the idea is to replace $y$ with an expression dependent only on $x$. Furthermore, you need to do so cleverly, so that the statement you obtained in this way is easy to prove. For example:

To show: $(\forall x\in\mathbb Z)(\exists y\in\mathbb Z)(2x<y)$

To show: $(\forall x\in\mathbb Z)(2x<2x+1)$

To show: $(\forall x\in\mathbb Z)(0<1)$

To show: $0<1$

To show: $\mathrm{true}$

Hence $(\forall x\in\mathbb Z)(\exists y\in\mathbb Z)(2x<y)$ is true.

You can improve readability by using more words and dropping universal quantifiers whenever you get the chance by using words like "assume" and "let." For example:

We want to show that $$(\forall x\in\mathbb Z)(\exists y\in\mathbb Z)(2x<y).$$ Choosing $y:=2x+1$, we see that it suffices to show that $$(\forall x\in\mathbb Z)(2x<2x+1).$$ So consider $x \in \mathbb{Z}$. It suffices to show that $2x<2x+1$. But this is equivalent to $0<1,$ which is true. This completes the proof.

As a general rule, you can use variables that occur to the left of the existential quantifier that you're trying to knock out. For instance, to prove $$(\forall w \in W)(\exists x \in X)(\forall y \in Y)(\exists z \in Z)P(w,x,y,z)$$

you

• replace $x$ with an expression dependent only on $w$, and then
• replace $z$ with an expression dependent only on $w$ and $y$.

Note that the order matters; you have to go left-to-right for it to make complete sense.

Answer 3

By contradiction. Sample style: $$(\;\neg (\forall x\in \Bbb Z\; \exists y\in \Bbb Z\;(2x<y))\;)\implies$$ $$\implies \exists x\in \Bbb Z\;\forall y\in \Bbb Z\;(2x\geq y)\implies$$ $$\implies \exists x\in \Bbb Z\; (y=|2x|+1\in \Bbb Z\land |2x|\geq 2x\geq y=|2x|+1)\implies $$ $$\implies 0\geq 1.$$