Results 1 to 15 of 15

Math Help - Proof that if a<b, b<c then a<c

  1. #1
    Junior Member
    Joined
    Oct 2009
    Posts
    31

    Proof that if a<b, b<c then a<c

    Hello

    I've been trying to prove this, but I don't even know how to start.

    Assuming, a, b, c € N, I wanted to prove that if
    a < b and b < c then a < c.

    I know that
    a < b is the same as saying
    there is a X for which a + x = b

    Now, I've tried doing the same for b < c
    there is a Y for which b + y = c

    Now, is there anyway to "mix them" together? What bothers me is that I don't even know if it possible, as both equations are "inside" the existencial quantifier. Or are they not? If I could make the second equation

    there is Y for which b = y - c


    and could mix it into something like

    there is X, Y such that a + x = -y + c


    then it would be easy to prove this.

    Any help is appreciated
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,672
    Thanks
    1490
    Quote Originally Posted by devouredelysium View Post
    Hello

    I've been trying to prove this, but I don't even know how to start.

    Assuming, a, b, c € N, I wanted to prove that if
    a < b and b < c then a < c.

    I know that
    a < b is the same as saying
    there is a X for which a + x = b

    Now, I've tried doing the same for b < c
    there is a Y for which b + y = c

    Now, is there anyway to "mix them" together? What bothers me is that I don't even know if it possible, as both equations are "inside" the existencial quantifier. Or are they not? If I could make the second equation

    there is Y for which b = y - c


    and could mix it into something like

    there is X, Y such that a + x = -y + c


    then it would be easy to prove this.

    Any help is appreciated
    What you have stated is self-evident.

    a < b and b < c.

    So a < b < c.

    Therefore a < c.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    31
    It is also self evident that 1+1 != 0, and still there are rigorous ways of proving it. I am looking for a way to prove that a < b, b < c => a < c. Saying that it is self-evident does not help in any way, I'd say..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2009
    Posts
    24
    if a < b and b < c then a < c.

    if a<b, then there exists k\in\mathbb{N} such that b=a+k
    also l\in\mathbb{N} such that c=l+b
    c=l+k+a
    so there is t\in\mathbb{N} (t=l+k)
    c=t+a so c>a
    i didnt read what you tried exatly, but seems that its almost the same
    Last edited by Julius; March 7th 2010 at 04:58 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,794
    Thanks
    1689
    Awards
    1
    Quote Originally Posted by devouredelysium View Post
    It is also self evident that 1+1 != 0, and still there are rigorous ways of proving it. I am looking for a way to prove that a < b, b < c => a < c. Saying that it is self-evident does not help in any way, I'd say..
    What is also self-evident, is that unless you post your entire axiom set we have no way to help.
    If you require rigor, we need exact axioms and definitions.
    This material can be and has been developed in many different ways.

    Here is a simple one. Define a<b to mean b-a>0.
    Then a<b & b<c means b-a>0 & c-b>0.
    Adding we get c-a>0 or a<c.

    But that probably does you no good since it probably differs from the way your text material treats this topic.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by devouredelysium View Post
    It is also self evident that 1+1 != 0, and still there are rigorous ways of proving it. I am looking for a way to prove that a < b, b < c => a < c. Saying that it is self-evident does not help in any way, I'd say..
    I am quite surprised that transitive property of real numbers would require proving.

    If a < b and b < c, then a < b < c; otherwise it would mean b \not = b, which would be a contradiction to the hypothesis. If this does not satisfy you. We can try again. say

    Assume to the contrary that a < b and b <c, then a \geq c. Say a = c, it follows that

    a<b implies c<b. This, however, contradict to our assumption. Therefore a \not = c. This should be more that sufficient to say a <c.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    Now, is there anyway to "mix them" together? What bothers me is that I don't even know if it possible, as both equations are "inside" the existencial quantifier. Or are they not?
    Yes, there is a way to mix them. The formula (\exists x\,a+x=b)\land(\exists y\,b+y=c) is equivalent to \exists x\exists y\,a+x=b\land b+y=c, both in the sense that they are true in the same models and in the sense that each one is derivable from the other. In fact, the latter formula is a prenex normal form of the former.

    When we are talking about derivability, there is something similar to "existential elimination rule". It says that if \exists x\,P(x) is already derived and from the assumption P(x) with the free variable x one derives R, then R is derived (from the assumption \exists x\,P(x)). In fact, this is nothing but formalization of a common way we deal with an assumption that asserts existence of something. So, having \exists x\,a+x=b and \exists y\,b+y=c, we apply existential elimination twice to get a+x=b\land b+y=c with free variables x,y. After that, we introduce, i.e., add, existential quantifiers back.

    If your doubts are about something else, feel free to clarify.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Mar 2009
    Posts
    378
    I remember proving this in the following way:
    a<b \Rightarrow a-b<0
    b<c \Rightarrow b-c<0
    \Rightarrow (a - b) + (b - c) < 0 \Rightarrow a - c < 0 \Rightarrow a<c.
    Which was mentioned already, but this was using the definitions I had in my book.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by emakarov View Post
    Yes, there is a way to mix them. The formula (\exists x\,a+x=b)\land(\exists y\,b+y=c) is equivalent to \exists x\exists y\,a+x=b\land b+y=c, both in the sense that they are true in the same models and in the sense that each one is derivable from the other. In fact, the latter formula is a prenex normal form of the former.

    When we are talking about derivability, there is something similar to "existential elimination rule". It says that if \exists x\,P(x) is already derived and from the assumption P(x) with the free variable x one derives R, then R is derived (from the assumption \exists x\,P(x)). In fact, this is nothing but formalization of a common way we deal with an assumption that asserts existence of something. So, having \exists x\,a+x=b and \exists y\,b+y=c, we apply existential elimination twice to get a+x=b\land b+y=c with free variables x,y. After that, we introduce, i.e., add, existential quantifiers back.

    If your doubts are about something else, feel free to clarify.
    Very interesting emakarove,

    Could you write the proof line by line?

    With line 1 and 2 the assumptions,
    line 3 hypothesis, and line 4 etc all to the last line a conclusion,
    with the right hand side the rules such as CP, MP, RAA, EI, EE, etc.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    I'll write the derivation tomorrow, in a few hours.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by emakarov View Post
    I'll write the derivation tomorrow, in a few hours.
    No hurry. Your business first. I am just curious because I have never seen it done in math yet. From what you showed, it seems that formal logic is such a powerful tool.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    One of the most natural ways to record derivations formally is called, well, Natural Deduction. Each inference rule is written as a line with assumptions written above and one conclusion below the line. Also, there are scoping rules: some assumptions are available up to some point, after which the are closed. E.g., in proving A -> B, we assume A and may use it to derive B. Then A is closed and we obtain A -> B. After that, A can no longer be used.

    Existential elimination rule (using an assumption of the form \exists x\,P(x)) has the following form.
    \frac{\exists x\,P(x)\qquad\begin{aligned}[b]<br />
&P(x)\\<br />
&\;\;\vdots\\<br />
&\;R<br />
\end{aligned}}{R}
    Here the assumption P(x) is closed by the last line. It corresponds to regular mathematical practice: if we know \exists x\,P(x), but don't know what exactly x is, we could prove that P(x) implies R for any x. Then we would know R.

    In text form, it is convenient to write derivations showing scoping explicitly. The existential elimination rule is written as follows.
    Code:
    
    
    
    
    
    \exists x\,P(x)
      
    
    
    
    
    P(x)
      
    
    
    
    
    \;\;\vdots
      
    
    
    
    
    R
    
    
    
    
    
    R
    This means that, having \exists x\,P(x), we temporarily introduce an assumption P(x), deduce R from it, and then close P(x). The result is a derivation of R from \exists x\,P(x).

    Using this, the proof about < can be written as follows.

    Code:
    
    
    
    
    
    \exists x\,a+x=b (1) assumption
      
    
    
    
    
    a+x=b (2) introducing a temporary assumption from (1)
      
    
    
    
    
    \exists y\,b+y=c (3) assumption
        
    
    
    
    
    b+y=c (4) introducing a temporary assumption from (3)
        
    
    
    
    
    a+x=b\land b+y=c (5) from (2), (4)
        
    
    
    
    
    \exists y\,a+x=b\land b+y=c (6) from (5)
        
    
    
    
    
    \exists x\,\exists y\,a+x=b\land b+y=c (7) from (6)
      
    
    
    
    
    \exists x\,\exists y\,a+x=b\land b+y=c (8) close (4)
    
    
    
    
    
    \exists x\,\exists y\,a+x=b\land b+y=c (9) close (2)
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Banned
    Joined
    Sep 2009
    Posts
    502
    Quote Originally Posted by emakarov View Post

    Code:
    
    
    
    
    
    \exists x\,a+x=b (1) assumption
      
    
    
    
    
    a+x=b (2) introducing a temporary assumption from (1)
      
    
    
    
    
    \exists y\,b+y=c (3) assumption
        
    
    
    
    
    b+y=c (4) introducing a temporary assumption from (3)
        
    
    
    
    
    a+x=b\land b+y=c (5) from (2), (4)
        
    
    
    
    
    \exists y\,a+x=b\land b+y=c (6) from (5)
        
    
    
    
    
    \exists x\,\exists y\,a+x=b\land b+y=c (7) from (6)
      
    
    
    
    
    \exists x\,\exists y\,a+x=b\land b+y=c (8) close (4)
    
    
    
    
    
    \exists x\,\exists y\,a+x=b\land b+y=c (9) close (2)
    Will it be incorrect to write:
    \forall x\,a+x=b (1) assumption
    a+\beta=b (2) universal elimination of (1)
    \forall y\,b+\beta=c (3) assumption
    b+y=c (4) universal elimination of (3)

    and replace \beta with x when introducing existential quantifier later?
    ?

    Code:
    
    
    
    
    
    \exists x\,P(x)
      
    
    
    
    
    P(x)
      
    
    
    
    
    \;\;\vdots
      
    
    
    
    
    R
    
    
    
    
    
    R
    Won't it be easier with universal elimination? It requires only 2 lines. What is the reason for choose the above instead?
    Last edited by novice; March 6th 2010 at 06:07 AM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Banned
    Joined
    Sep 2009
    Posts
    502
    emakarov,

    I found the answers to my questions. Thank you for your time.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,987
    Thanks
    1650
    Quote Originally Posted by Plato View Post
    What is also self-evident, is that unless you post your entire axiom set we have no way to help.
    If you require rigor, we need exact axioms and definitions.
    He did. He did. He stated that he was working in the natural number system.

    This material can be and has been developed in many different ways.

    Here is a simple one. Define a<b to mean b-a>0.
    Then a<b & b<c means b-a>0 & c-b>0.
    Adding we get c-a>0 or a<c.

    But that probably does you no good since it probably differs from the way your text material treats this topic.
    I would not consider that a good proof because, generally "b- a" is not defined in the natural number system. Julius's proof avoids that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum