Prove or Disprove: ∃x ∈ N such that ∀y ∈ N, 2x ≤y + 1

The first thing that I tried to do is: let y be an arbitrary natural number. I then tried to choose a value for x, but I cannot think of a value in which 2x ≤ y + 1..

So I then tried to prove the negation: ∀x ∈ N, ∃y ∈ N, 2x > y + 1

So I then let x be an arbitrary natural number and tried to set a value for y .... but the smallest value that y can be is x, correct? Because anything less than x and y would not be a natural number all of the time. So I do not know how to solve this, because I can't think of anything that works.

-
The set $\{y+1 \colon y \in N\}$ is the set of all numbers in $N$ that are successors of the natural numbers in $N$. Let $y_0$ denote the smallest natural number. Then, the question asks whether there is an $x \in N$ such that $2x \leq y_0 + 1$ – Dilip Sarwate Sep 20 '12 at 18:04

Translate the statement into simple English:

Is there a natural number (call it $x$), such that for every other natural number $y$, the number $y + 1$ is at least twice as large as $x$?

And try rephrasing/simplifying that statement:

Is there a natural number $x$ which is less than or equal to $(y+1)/2$, for every natural number $y$?

(The translation into simple English is meant to help you with the quantifiers, here — for the algebra of dividing by two, using math rather than English will probably be less cumbersome.)

Because we're talking about a number which is smaller than or equal to some expression $f(y)$, where $f(y)$ grows with $y$, your best approach is to consider the smallest allowed $y$, and see if any values of $x$ work.

-
Ok, so this makes sense. If x = 1 then 2x ≤ y + 1. But I was under the impression that I couldn't say x = 1, I had to have x = a variable. Is this not true? For example, in the other proofs that I have done, I would set x = y + 1 or something like that. – William Sep 20 '12 at 16:07
What does it mean for $x$ to be "a variable", when you're using existential quantifiers? All $x$ stands for here is some number (or more than one) which haven't been explicitly named, which is often what variables are used for in math. If I tell you $x^2 = 4$ and $x > 0$, this means that $x$ is the name of a number which has these properties, and in this case I've given you enough information to find out its value. In your case, someone has given you some constraints on the variable $x$, and they ask whether there are any solutions: any values that $x$ could have under those restrictions. – Niel de Beaudrap Sep 20 '12 at 16:15

Hint: Let $x$ be the smallest natural number ($0$ or $1$, depending on the convention being used).

-