proving that if $x\le y$ and $y\le x$ then $x=y$

Question

Here's what the authors of a textbook that I've been following argue:

Let $x,y\in \mathbb{R}$. Assume that $x \le y$ and $y ≤ x$. We claim that $x = y$. If false, then either, $x < y$ or $y < x$ by law of trichotomy. Assume that we have $x < y$. Since $y ≤ x$, either $x = y$ or $y < x$. Neither can be true, since we assumed $x \not= y$ and hence concluded $x < y$ from the first inequality $x ≤ y$. Hence we conclude that the second inequality cannot be true, a contradiction. Thus our assumption that $x \not= y$ is not tenable.

My argument is as follows: We assume that $x \le y$ and $y ≤ x$. Suppose $x\not=y$. Then $x \le y$ and $y ≤ x$ reduces to $x < y$ and $y < x$. But both inequalities $x < y$ and $y < x$ cannot hold together at the same time due to trichotomy. Thus we achieved a contradiction to our hypothesis. Is this argument correct?

I need a clarification on proof done by the authors. They say "Assume that we have $x < y$" and on another line they say "hence concluded $x < y$ from the first inequality $x ≤ y$". Did they deduce it or assume it?

Answer 1

I need a clarification on proof done by the authors. They say "Assume that we have $x < y$" and on another line they say "hence concluded $x < y$ from the first inequality $x ≤ y$". Did they deduce it or assume it?

They deduce it from $x \le y$ and the assumption $x \not = y$

But yes, their proof is quite confusing. I've read it over about $4$ times now, and tried to sketch their lines of reasoning, and concluded that the part

Assume that we have $x <y$'

is better taken out (indeed, the presence of this very sentence seems to be exactly what confused you as well!).

That is, it seems like they used this line to set up a proof by cases (see line 5 in outline below), where they show that both $x<y$ and $y<x$ would lead to a contradiction ... but then changed strategy in the middle of the proof, and ended up showing that since you can conclude (rather than assume) $x < y$ from the first inequality $x \le y$ together with the assumption $x \not = y$, you end up contradicting the second inequality.

To be rather technical and formal ... I think that in the middle of the proof they switched strategies from:

$1. x \le y$ (Premise)

$2. y \le x$ (Premise)

$3. x \not = y$ (Assumption)

$4. x < y \lor y < x$ (by 3 and Trichotomy)

$5. x < y$ (Assumption)

$6. \bot$ (between 2 and 5)

$7. y < x$ (Assumption)

$8. \bot$ (between 1 and 7)

$9. \bot$ (between 4, 5-6, and 7-8)

$10. x = y$ (3-9)

to something like:

$1. x \le y$ (Premise)

$2. y \le x$ (Premise)

$3. x \not = y$ (Assumption)

$4. x < y \ xor \ y < x$ (3 and trichotomy)

$5. y < x \lor x = y$ (from 2)

$6. x < y$ (from 1 and 3)

$7. y \not < x$ (from 4,6)

$8. \neg (y < x \ xor \ x = y)$ (from 3 and 7)

$9. \neg y \le x$ (from 8, 4, and fact that 4 follows from 2)

$10. \bot$ (2 and 9)

$11. x = y$ (3-10)

But even that is not very clean (note the weird thing that happens on line 9 ...) . Indeed, even if we take out the unused line, we obtain:

Let $x,y\in \mathbb{R}$. Assume that $x \le y$ and $y ≤ x$. We claim that $x = y$. If false, then either, $x < y$ or $y < x$ by law of trichotomy. Since $y ≤ x$, either $x = y$ or $y < x$. Neither can be true, since we assumed $x \not= y$ and hence concluded $x < y$ from the first inequality $x ≤ y$. Hence we conclude that the second inequality cannot be true, a contradiction. Thus our assumption that $x \not= y$ is not tenable.

... which follows the second outline ... but is still not very readable.

... NOT a great example of how to write proofs!

I think your proof is far more clear! Good job, and good for you for noticing that something very funky was happening in the provided proof!

Answer 2

They say "Assume that we have $x<y$"

You are taking it out of context. The full statement is:

We claim that $x=y$. If false, then either, $x<y$ or $y<x$ by law of trichotomy. Assume that we have $x<y$.

"If false, then..." implies "If $x\ne y$, then either, $x<y$ or $y<x$ by law of trichotomy. Assume that we have $x<y$."

The book's this statement corresponds to your statement: "Suppose $x≠y$. Then $x≤y$ and $y≤x$ reduces to $x<y$ and $y<x$. But both inequalities $x<y$ and $y<x$ cannot hold together at the same time due to trichotomy."

The law of trichotomy: "Every real number is negative, $0$, or positive." So the book is using "OR" for each case: $x<y$ or $x>y$ separately, while you are using "OR" indirectly, that is by negating "AND".

Did they deduce it or assume it?

They deduced it from the assumption $x\ne y$. See below with my comments inside brackets:

We claim that $x=y$. If false ($\color{blue}{x\ne y}$), then either, $x<y$ or $y<x$ by law of trichotomy. Assume that we have $x<y$. Since $y≤x$ (original statement: $\color{green}{x\le y}$ $\color{magenta}{\text{and}}$ $\color{red}{y\le x}$), either $x=y$ or $y<x$. Neither can be true, since we assumed $\color{blue}{x≠y}$ and hence concluded $x<y$ from the first inequality $x\le y$ ($\color{green}{x≤y}$). Hence we conclude that the second inequality ($\color{red}{y\le x}$) cannot be true (because of $\color{magenta}{\text{and}}$), a contradiction. Thus our assumption that $x≠y$ is not tenable.

Answer 3

Their argument:

Given $x \le y$ and $y \le x$.

Assume $x \ne y$.

$x\le y$ means $x=y$ or $x < y$. We ruled out $x=y$ so that leaves $x < y$. Stick a pin in that.

$y \le x$ means that $y=x$ or $y < x$. Remove the pin and compare with $x < y$. Neither $y =x$ nor $y < x$ is compatible with $x < y$.

So we have a contradiction.

So $x =y$.

Your argument:

Given $x \le y$ and $y \le x$.

Assume $x \ne y$.

$x\ne y$ means $x=y$ or $x < y$. We ruled out $x=y$ so that leaves $x < y$.

$y \le x$ means that $y=x$ or $y < x$. We ruled out $y=x$ so that leaves $y < x$.

$x < y$ and $y<x$ are mutually incompatible.

So we have a contradiction.

So $x =y$

====

Both your arguments are valid.

They took a "$x<y$" to a Contradiction fight and you took a "$x \ne y$" the the same contradiction fight. They were both equally good weapons.

....

But I prefer your method. It's more symmetric which aesthtically pleases me and I find more convincing.

The one thing they did that is both better and worse than what you did, is the really went to the basic axiomatic deductions: They spelled out that $x \le y$ means $x=y$ or $x < y$ and if we had assumed that $x\ne y$ then we deduce $x < y$ whereas you took it as obvious.

It's better in that it is pure axiomatic deduction. It's worse in that it is hard to read as it is easy to get lost in the tedium.

But I like that you used the same argument for $x \le y\implies x < y$ and $y \le x \implies y < x$ whereas I dislike that they used different $x \le y\implies x <y$ and $x<y \land y \le x$ are incompatible arguments.