# Thread: Proof that if a<b, b<c then a<c

1. ## 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

2. Originally Posted by devouredelysium
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.

$\displaystyle a < b$ and $\displaystyle b < c$.

So $\displaystyle a < b < c$.

Therefore $\displaystyle a < c$.

3. 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..

4. if a < b and b < c then a < c.

if a<b, then there exists $\displaystyle k\in\mathbb{N}$ such that b=a+k
also $\displaystyle l\in\mathbb{N}$ such that c=l+b
c=l+k+a
so there is $\displaystyle t\in\mathbb{N}$ $\displaystyle (t=l+k)$
$\displaystyle c=t+a$ so $\displaystyle c>a$
i didnt read what you tried exatly, but seems that its almost the same

5. Originally Posted by devouredelysium
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.

6. Originally Posted by devouredelysium
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 $\displaystyle a < b$and $\displaystyle b < c$, then $\displaystyle a < b < c$; otherwise it would mean $\displaystyle 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 $\displaystyle a < b$ and $\displaystyle b <c$, then $\displaystyle a \geq c$. Say $\displaystyle a = c$, it follows that

$\displaystyle a<b$ implies $\displaystyle c<b$. This, however, contradict to our assumption. Therefore $\displaystyle a \not = c$. This should be more that sufficient to say $\displaystyle a <c$.

7. 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 $\displaystyle (\exists x\,a+x=b)\land(\exists y\,b+y=c)$ is equivalent to $\displaystyle \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 $\displaystyle \exists x\,P(x)$ is already derived and from the assumption $\displaystyle P(x)$ with the free variable $\displaystyle x$ one derives $\displaystyle R$, then $\displaystyle R$ is derived (from the assumption $\displaystyle \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 $\displaystyle \exists x\,a+x=b$ and $\displaystyle \exists y\,b+y=c$, we apply existential elimination twice to get $\displaystyle a+x=b\land b+y=c$ with free variables $\displaystyle x,y$. After that, we introduce, i.e., add, existential quantifiers back.

8. I remember proving this in the following way:
$\displaystyle a<b \Rightarrow a-b<0$
$\displaystyle b<c \Rightarrow b-c<0$
$\displaystyle \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.

9. Originally Posted by emakarov
Yes, there is a way to mix them. The formula $\displaystyle (\exists x\,a+x=b)\land(\exists y\,b+y=c)$ is equivalent to $\displaystyle \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 $\displaystyle \exists x\,P(x)$ is already derived and from the assumption $\displaystyle P(x)$ with the free variable $\displaystyle x$ one derives $\displaystyle R$, then $\displaystyle R$ is derived (from the assumption $\displaystyle \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 $\displaystyle \exists x\,a+x=b$ and $\displaystyle \exists y\,b+y=c$, we apply existential elimination twice to get $\displaystyle a+x=b\land b+y=c$ with free variables $\displaystyle x,y$. After that, we introduce, i.e., add, existential quantifiers back.

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.

10. I'll write the derivation tomorrow, in a few hours.

11. Originally Posted by emakarov
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.

12. 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 $\displaystyle \exists x\,P(x))$ has the following form.
\displaystyle \frac{\exists x\,P(x)\qquad\begin{aligned}[b] &P(x)\\ &\;\;\vdots\\ &\;R \end{aligned}}{R}
Here the assumption $\displaystyle P(x)$ is closed by the last line. It corresponds to regular mathematical practice: if we know $\displaystyle \exists x\,P(x)$, but don't know what exactly $\displaystyle x$ is, we could prove that $\displaystyle P(x)$ implies $\displaystyle R$ for any $\displaystyle x$. Then we would know $\displaystyle R$.

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

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

Code:
$\displaystyle \exists x\,a+x=b$ (1) assumption
$\displaystyle a+x=b$ (2) introducing a temporary assumption from (1)
$\displaystyle \exists y\,b+y=c$ (3) assumption
$\displaystyle b+y=c$ (4) introducing a temporary assumption from (3)
$\displaystyle a+x=b\land b+y=c$ (5) from (2), (4)
$\displaystyle \exists y\,a+x=b\land b+y=c$ (6) from (5)
$\displaystyle \exists x\,\exists y\,a+x=b\land b+y=c$ (7) from (6)
$\displaystyle \exists x\,\exists y\,a+x=b\land b+y=c$ (8) close (4)
$\displaystyle \exists x\,\exists y\,a+x=b\land b+y=c$ (9) close (2)

13. Originally Posted by emakarov

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

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

Code:
$\displaystyle \exists x\,P(x)$
$\displaystyle P(x)$
$\displaystyle \;\;\vdots$
$\displaystyle R$
$\displaystyle R$
Won't it be easier with universal elimination? It requires only 2 lines. What is the reason for choose the above instead?

14. emakarov,

I found the answers to my questions. Thank you for your time.

15. Originally Posted by Plato
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.