# Prove or Disprove: $\exists y ∈ \mathbb{N}$ such that $\forall x ∈ \mathbb{N}, 2x ≤ y + 1$

Here's what I have done:

I think it's false, so I set out to prove the negation. Which is: $$\forall y \in \mathbb{N}, \exists x \in \mathbb{N}; 2x > y + 1$$ I then let $y$ be an arbitrary natural number. After this, I do not know how to proceed.

-
$\Bbb{N}$ is unbounded..... – user38268 Sep 20 '12 at 6:07

Suppose that I tell you that I’m thinking of some $y\in\Bbb N$, but I don’t tell you what it is. Could you give me a recipe for calculating an $x$ such that $x>y+1$? Sure: just set $x=y+2$. You don’t need an $x>y$: you just need an $x$ such that $2x>y+1$, and that ought to be even easier to specify by a recipe. I’ve included a couple of possible recipes below, spoiler-protected; mouse-over to see them.

The smallest $x$ that works is the smallest natural number $n>\frac{y+1}2$; that’s $\frac{y}2+1$ if $y$ is even and $\frac{y+1}2+1$ if $y$ is odd. But working that out is a waste of energy, at least as far as the immediate problem is concerned, because if $x>y+1$, then certainly $2x\ge x>y+1$. Thus, you might as well use the same recipe that I gave for the simpler problem: set $x=y+2$. That certainly ensures that $2x=2y+4=2(y+1)+2>y+1$!

-
Ok, so now I have 2(y+1) = y + 1. So that confirms the negation, right? Because I have shown a value of x that makes the statement 2x > y + 1 true no matter what value of Y I plug in. What does this mean then? If the negation is true, does that mean that the original statement is false? So I have disproven the original statement? – William Sep 20 '12 at 6:15
@Willy: You have indeed. – Brian M. Scott Sep 20 '12 at 6:16
If $x \in \mathbb{N}$ then $2x \in \mathbb{N}$, for any large $2x$ we can always find $y$ that is greater than $2x$ (since $\mathbb{N}$ is unbounded), am I correct? – Vikram Sep 20 '12 at 6:55
@Vikram: Sure: $2x+1$ works. – Brian M. Scott Sep 20 '12 at 6:58

For any $y\in \mathbb{N}$, $2(y+1)\gt y+1$.

-

Hint $\rm\ 2\,\Bbb N\, =$ even naturals, so if they are bounded above then there are only finitely many evens, hence only finitely many odds $\rm\,1 + 2\,\Bbb N,\:$ hence only finitely many naturals, contradiction.

Alternatively, finitely many odds implies finitely many primes, contra Euclid's classical proof.

-