Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

First my apologies if this question has been asked before.

Exposition
I'm new at learning how to prove theorems and among the given exercises from my reference material it is asked to prove the following:
The original question in words:

For every positive $x \in \mathbb{Q}$, there exists positive $y \in \mathbb{Q}$ for which $y \lt x$.

I translated it and got:

$\forall x \in \mathbb{Q}_{\gt0} \ \exists y \in \mathbb{Q}_{\gt0}, \ y \lt x$

Here is my attempted proof.

If $x \in \mathbb{Q}_{\gt0}$ then $\exists y \in \mathbb{Q}_{\gt0}$ such that $y \lt x$. Suppose $\forall y \in \mathbb{Q}_{\gt0}$, $y \geq x$.
So if $y \in \mathbb{Q}_{\gt0}$ then $y \geq x$. By contrapositive if $y \lt x$ then $y \notin \mathbb{Q}_{\gt0}$.
But this doesn't make sense. Hence we were wrong to assume that $\forall y \in \mathbb{Q}_{\gt0}$.

Question
I'm having trouble with the part starting from this doesn't make sense. I looked at the $y \notin \mathbb{Q}_{\gt0}%$ and made a somewhat educated guess regarding the fact that $y \notin \mathbb{Q}_{\gt0}%$ doesn't logically follow from the premise that $y \lt x$. This in the sense that the less than 'operator' can only be defined between two mathematical objects of the same kind.
Is there something i got wrong? Does this make sense? Is the proof complete anyway? What would be the correct proof?

In clear and concise terms, I'm trying to understand if my proof is correct.

Thanks

UPDATE
I re-read the question again from the material and $y$ is supposed to be a positive rational too. Yet i think given replies at the original time of this update still apply.

UPDATE 2
With regards to the answer provided by @crf i think i should provide the proof strategy. By this point if someone could see something wrong in the proof, i guess it came from me making something wrong in my strategy. So here is the proof strategy. All that follows of course is supposed to be part of draft work.

1. First i get the statement into symbolic form in order to 'safely' transform the expression:

$\forall x \in \mathbb{Q}_{\gt0} \ \exists y \in \mathbb{Q}_{\gt0}, \ y \lt x$

2. Transform the obtained statement into conditional form:

We know that $\forall x \in S, \ Q(x)$ is equivalent to $(x \in S) \Rightarrow Q(x)$.

Then we get:
$x \in \mathbb{Q}_{\gt0} \Rightarrow \exists y \in \mathbb{Q}_{\gt0}, \ y \lt x$

Reference: Book of proof by Richard Hammack, pp 54, Fact 2.2 available online here

3. Then we attempt a proof by contradiction for this conditional statement:

As such our hypotheses become:
$$ x \in \mathbb{Q}_{\gt0} \\ \forall y \in \mathbb{Q}_{\gt0} \ (y \geq x) $$

And this is equivalent to :
$$ x \in \mathbb{Q}_{\gt0} \\ y \in \mathbb{Q}_{\gt0} \Rightarrow y \geq x $$

and conclusion: will be a contradiction

4. Transform $\forall y \in \mathbb{Q}_{\gt0} \ (y \geq x)$ to get its contrapositive:

We get as new hypotheses:
$$ x \in \mathbb{Q}_{\gt0} \\ y \lt x \Rightarrow y \notin \mathbb{Q}_{\gt0} $$

That where i got stuck and i started guessing: how does $y \notin \mathbb{Q}_{\gt0}$ follow from $y \lt x$? I couldn't see a rigorous contradiction between that and premises and got got stuck!

Thanks for bearing all this!

share|improve this question
    
What's wrong with writing $x = p/q$ and taking $y = p/(q+1)$, say? –  t.b. Aug 15 '12 at 9:22
8  
@t.b.: Or simpler still: Take $y=x/2$. –  Harald Hanche-Olsen Aug 15 '12 at 9:23
1  
@Harald: hm... :) –  t.b. Aug 15 '12 at 9:25
    
I understand there are various ways, and even simpler ways, of doing this but like i mentioned in the question i'm trying to understand if my proof is correct, not alternatives. While both the suggestions of @t.b. and Harald Hanche-Olsen are correct i'm trying to emphasize more on logical arguments directly from premises than computational 'intuition'. Thx –  nt.bas Aug 15 '12 at 9:31
    
Hint: "but this doesn't make sense" is not a mathematical statement, and doesn't have a place in a proof. It is an invitation to duck the real issue at stake - mathematics is quite precise about such things and what is required is a mathematical statement of WHY it "doesn't make sense" in the mathematical context of the question. –  Mark Bennet Aug 15 '12 at 9:43

6 Answers 6

up vote 4 down vote accepted

What you've done so far actually has nothing to do with proving your theorem. If you do want such a symbolic lead-in, OK-it's not false, though it's worth noting that such intricate manipulations are ugly compared to a direct and brief argument. In any case, to finish, you must stop playing with symbols and say something mathematical, such as "But wait! $\frac{x}{2}\in Q_{>0}$ is less than $x,$ so by contradiction, my assumption $y<x \rightarrow y\notin Q_{>0}$ is false!" That last sentence is the entire mathematical content of the proof.

share|improve this answer

My first observation is that you’re getting badly bogged down in symbols. For starters, there is absolutely no reason to replace the clear statement of the problem with the symbolic expression $\forall x \in \mathbb{Q}_{\gt0} \ \exists y \in \mathbb{Q}_{\gt0}, \ y \lt x$; that’s just introducing unnecessary obstacles for the reader. The same goes for your argument. Both it and its shortcomings would be much more easily read if you wrote it out in words, like this:

Suppose that that every positive rational $y$ is greater than or equal to $x$. Then if $y>0$ is rational, $y\ge x$. By taking the contrapositive it follows that if $y<x$, then $y$ is not a positive rational.

Without the fancy symbols to get in the way there’s a question that should almost leap out at you: what is $x$? Nowhere have you given any indication. And since you haven’t, what can it possibly mean to suppose that $y\ge x$ for all positive rationals $y$?

Back up now and think again about the actual statement: for each positive $x\in\Bbb Q$ there is a $y\in\Bbb Q$ such that $y<x$. Look at a few examples. If $x=7$, I can take $y=6$, for instance. If $x=6$, I can take $y=5$. If $x=3/2$, I can take $y=1/2$. In fact, no matter what positive rational $x$ may be, $x-1$ is a rational number less than $x$. I’m done: I’ve proved the statement by providing a recipe for finding a suitable $y$ given $x$.

And even then I’m working too hard. Is there any rational number that is less than all positive rational numbers? Sure: $0$, or for that matter any negative rational number. Now I’ve proved an even stronger statement: there is a $y\in\Bbb Q$ such that $y<x$ for each positive $x\in\Bbb Q$. If you insist on looking at quantifiers, this is $$\exists y\in\Bbb Q\forall x\in\Bbb Q_{>0}(y<x)\;.$$

Here’s an exercise for you to try: prove that for each positive $x\in\Bbb Q$ there is a positive $y\in\Bbb Q$ such that $y<x$. HINT: An idea something like my first argument works.


A mathematical proof is a piece of expository prose. Its purpose is to convince the reader that the theorem is true. Obviously it should be mathematically correct and logically sound, but it should also be clear and easy to follow. By all means use symbols when they’re appropriate: the quadratic formula is much easier to follow when expressed symbolically than when written out in words! But don’t fall into the trap of thinking that the more symbolism you use, the more professional your argument looks.

share|improve this answer
    
Thanks.So if i understand your answer well, i should retain: 1/let your reader know what everything stands for in the proof and 2/avoid an unnecessary use of symbols. But i still don't understand why should $x$ stand for anything and this is because: 1/we know $x$ is any positive rational and 2/if we say (assuming this is correct and i understood you well) $y=x-1$, we know that that this proves that there is always something less than $x$ without giving $x$ any value. So what did you mean by what is x? Thanks –  nt.bas Aug 15 '12 at 10:21
    
@nt.bas: Your argument began with (a symbolic version of) the statement Suppose that every positive rational number is greater than or equal to x. This is meaningful only if $x$ has already been defined in some way; otherwise $x$ might be Mars, for all the reader knows. If you really want to try a proof by contradiction, start by assuming that the result is false: Suppose that there is a rational number x such that every positive rational number is greater than or equal to x. Or, with a modest use of symbols, ... –  Brian M. Scott Aug 15 '12 at 10:30
    
@nt.bas You've not specified in your proof what $x$ is. You should have had some kind of statement like, "let $x$ be a positive rational number" before even talking about whether $y\geq x$. –  crf Aug 15 '12 at 10:31
    
... suppose that there is an $x\in\Bbb Q_{>0}$ such that $x\le y$ for every $y\in\Bbb Q$. That would be perfectly legitimate: now when you say that every positive rational is greater than or equal to $x$, you’re talking about a specific $x$, albeit one whose numerical identity isn’t known. It would also be very clear that this $x$ would be the smallest rational number, which would immediately point the way to the next step: get a contradiction by showing that there is no smallest rational number. –  Brian M. Scott Aug 15 '12 at 10:31
    
I think my problem as rightfully mentioned by Brian M. Scott is i used to much symbols. The thing i gave was a raw translation of my draft work but if you look closely i did mention $x$ belonged to the rational positive integers, without the assuming part. Now suppose i had mentioned (even when i possibly didn't) and i didn't say this doesn't make sense, would the proof be correct?... –  nt.bas Aug 15 '12 at 10:42

So you want to prove that there always exists a rational $y$ in the interval $[0,x]$. We can do one better and prove the existence of rationals in any open interval $(a,b)$, for any real $a$ and $b$. This uses the Archimedean property of real numbers - that $\forall x,y \in R (x>0); \exists n \in N| nx > y$. So, suppose such a rational, $r$ exists. We have that: $$a<r<b$$ Let $p=[a]$ (the integral part of $a$). Since R is Archimedean, there exist natural $n$ and $m$ such that $n(b-a)>1$ and $m\left( \frac{1}{n} \right)>a-p$. Let us fix the $least$ such $m$, so that we have: $$\frac{m}{n}>a-p \quad but \quad \frac{m-1}{n} \le a-p$$ We therefore arrive at $$a<p+\frac{m}{n}\le a+\frac{1}{n} \le a+(b-a)=b$$

Therefore $p+\frac{m}{n}$ is our desired rational.

share|improve this answer

Okay I see generally what your strategy is. You wanted to assume the negation of your symbolic translation $∀x∈ℚ_{>0} ∃y∈ℚ_{>0}, y<x$, and then derive a contradiction. One smaller issue—your translation into symbols is incorrect. The original statement says nothing about $y$ being positive. So your translation should have read $∀x∈ℚ_{>0} ∃y∈ℚ, y<x$. But there's a larger issue: you didn't quite get the negation right. Your assumption,

$∀y∈ℚ_{>0}, y≥x$

is not the negation of your sentence. The correct negation is

$\exists x\in \mathbb{Q}∀y∈ℚ_{>0}, y≥x$

Your hypothesis for the contradiction argument doesn't specify anything about $x$—do you mean for all $x$? For 2 values of $x$? Is $x$ a number? The existence quantifier is crucial—without it you don't really have an argument at all. But as Brian points out, my feeling is that all the symbolic manipulation obscures the logic and intuition, so I'm going to translate your argument back into English where it belongs, with to correct first step.

So what you really wanted to do was assume that there exists a positive rational number, which we'll call $x$, with the property that for every rational number $y$, $y\geq x$. This is the correct negation of the original statement, and now that you have a properly quantified sentence, I'm sure there are a number of explicit contradictions that you can derive. One nice thing is that, since every single $y\in\mathbb{Q}$ has to have this property under our hypothesis, all you have to do to find a contradiction is find just one counterexample. Can you find a rational number which is strictly less than every positive rational number?

share|improve this answer
    
I have added the proof strategy i used because i believe it is the root of my troubles. And if you look at the first update, $y$ is to be positive. Thanks!!! –  nt.bas Aug 15 '12 at 11:37

$x/2$ is rational and less than $x$, and it is positive if $x$ is positive.

share|improve this answer

Maybe I am a bit sloppy, and forgive me if I am, but couldn't you just say the following:

I have two fractions, namely fraction $x$ and fraction $y$.

Suppose $x=\frac{1}{d}$.

Note that any fraction can be rewritten into something of this form. Any fraction of the form $\frac{a}{b}$ can be rewritten into $\frac{1}{b/a}$ such that $d=\frac{b}{a}$.

By picking $y=\frac{1}{d+1}$ I will always be able to have a fraction $y$ that is always smaller than $x$. Hence the statement is correct.

share|improve this answer
    
Yes, you are right. but a young fella like me, new to all this beautiful theorem proving stuff, doesn't understand the importance of hanging on the fact than getting bogged down to unnecessary symbolic manipulations. If you look at the answers provided and comments, others have mentioned this notably Harald Hanche-Olsen. Otherwise thanks for helping me understand this even better! And of course, welcome to MSE!! :-) –  nt.bas Aug 15 '12 at 15:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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