0
$\begingroup$

I need to prove the statement:

Let $x \in \mathbb{R}$. Prove that $1 \le x \le 2$ if and only if $1 \le x \le 1+ 1/n$ for some $n \in \mathbb{N}$.

So I start with the forward implication:

If $1 ≤ x ≤ 2$ then there exists $n \in \mathbb{N}$ such that $1 \le x \le 1+ 1/n$ as follows:

let $x \in \mathbb{R}$ be such that $1 ≤ x ≤ 2$ then $1 \le x \le 1 + 1$

so $1 \le x \le 1 + 1/1$ thus $n=1$.

Next when I try to prove the reverse implication:

If there exists an $n \in \mathbb{N}$ such that $1 \le x \le 1+ 1/n$ then $1 \le x \le 2$.

It is here that I am unsure how to proceed because I somehow need to eliminate $n$ and produce the conclusion $1 \le x \le 2$. Also this is an existential implication, which I know to be meaningless. However, I do not see any other way to quantify the if and only if statement. Anyway, proceeding I take the contra-positive of the statement to get:

If $1 > x$ or $x > 2$ then for every $n \in \mathbb{N}$, $1 > x$ or $x > 1 + 1/n$.

Now I know the statements of the form (P or Q) implies R are proven by taking cases: (P implies R) and then (Q implies R). And I also know the to prove a statement of the form (R or S) I simply prove either R or S or use the equivalence (R or S) = (Not R implies S) and then add Not R to my original assumptions. However that is exactly where my confusion starts.

Suppose I decide to prove the statement ($1 > x$ or $x > 2$) implies ($1 > x$).

then case 1: suppose $1 > x$ then $x > 1$ as required. Done. case 2: suppose $x > 2$ ... obviously I will never derive ($1 > x$) so finished by vacous proof? or do I simply prove the other statement in the "or" conclusion? if I do that then won't I have just proven [($1 > x$) implies ($1 > x$)] and ($x > 2$) implies ($x > 1 + 1/n$)? Which is clearly not equivalent to the contrapositive formed earlier.

What if I changed the contrapositive into the form:

If $1 > x$ or $x > 2$ then for every $n \in \mathbb{N}$, $1 ≤ x$ implies $x > 1 + 1/n$.

If I decide on this form then proof by cases this becomes:

Case 1: suppose $1 > x$ and suppose $1 \le x$...this is a contradiction, so vacous proof? Case 2: suppose $x > 2$ and suppose $1 \le x$ ... some proof

So you see, no matter how I proceed I run into trouble. At first I run into trouble because I need to get rid of the $n$, in my second attempt, I get confused on which results are valid since proceeding by cases on the same conclusion seems to lead me to having to prove ($x > 2$) implies ($1 > x$) which is impossible. And in my final attempt I run into difficulty due to incompatible assumptions, and a proof that I am unable to prove.

$\endgroup$
1
$\begingroup$

For the reverse implication you need to use that $\frac1n\leq1$ of all integers $n>0$ (I must assume that in your world $\Bbb N$ does not contain $0$, since then the question would not be well formulated to begin with). This needs to be proved, for instance by showing that $\frac1n>1$ is absurd; I will not go into those details.

So you could proceed as follows (for the "if" direction). Let $x\in\Bbb R$ be given [for the universal quantification] and suppose there exists $n\in \Bbb N$ such that $1\leq x\leq 1+\frac1n$. Take such an $n$ [for the existential quantifier]. Since $\frac1n\leq1$ one has $1+\frac1n\leq2$, and $x\leq 1+\frac1n$ together with $1+\frac1n\leq2$ imply $x\leq2$ by transitivity of "$\leq$". So one has both inequalities in $1\leq x\leq 2$, as desired.


By the way, I don't understand what you mean with "existential implication is meaningless". It happens very often that one wants to prove an implication where the hypothesis contains an existential statement. Then the way to proceed is (as above) to assume some value witnessing the existential statement is given (this is $n$ above); then prove the conclusion using whatever existential statement says for that value (even though you do not know explicitly); this is called existential elimination. You need to arrive at the conclusion, whatever the witness for the existential statement is. So to prove a statement $(\exists x:P(x))\to Q$, you must essentially show $P(x)\to Q$ for any value of$~x$, in other words you must show $\forall x:(P(x)\to Q)$. Indeed $(\exists x:P(x))\to Q$ is logically equivalent to $\forall x:(P(x)\to Q)$.

The conclusion may or may not contain an existential statement; this is unimportant. But if it does, then be aware that an existential statement in the conclusion is completely independent of the one in the hypothesis and might require a different witness from the one being used in the hypothesis.

$\endgroup$
1
  • $\begingroup$ Your right, I was interpreting the statement as [∃x:(P(x)→Q(x))], which is what is meaningless and did not realize it was actually (∃x:P(x)→Q) which is the same as (∃x:P(x))→Q. $\endgroup$
    – skyfire
    Feb 9 '15 at 19:09
0
$\begingroup$

Just pick $n = 1$. This is enough for all $1 \le x \le 2$.

Read carefully what you are trying to prove. For each $x$ you need to find one $n$, nobody says the $n$ can't be the same for all $x$.

$\endgroup$
3
  • $\begingroup$ Yes I agree that it is obvious from the start. However in every txt book on proof writing they explicitly state that if an existential statement is present in the antecedent of an implication that you can only use existential instantiation which says you can only say that there is an "x" such that P(x) is true, and nothing about the value of x. So why does that change in this circumstance? Or maybe you can tell me why that does not apply in this scenario? I suppose really that is the origin of all my confusion. $\endgroup$
    – skyfire
    Apr 14 '14 at 22:20
  • $\begingroup$ actually after reading the reverse implication, it seems that I have an existential implication which is meaningless. However I don't see how else I can quantify the iff statement! where did I go wrong? $\endgroup$
    – skyfire
    Apr 15 '14 at 13:13
  • $\begingroup$ @vonbrand: I think that you should read the question more carefully. It says $1 \le x \le 2$ if and only if there exists $n$... Picking $n=1$ only solves the "only if" direction. If at the end it would have said $1 \le x \le 1+n$ instead, then the statement would have been false, even though for $n=1$ one gets exactly the same thing. $\endgroup$ Feb 8 '15 at 6:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.