Is this proof of the totality of this relation correct?

Question

I'm currently writing an original chapter of a textbook I'm republishing and I need to know if this rather pedantic proof of a total ordering on $\mathbb{R}$ is correct. It looks correct, but something is still bothering me about it. I'd be very grateful if I could get a second opinion on it.

I'll post the theorem preceded by the definitions and terminology I'm using.

---

Defintion: Let R be a relation from a set A into A i.e. a subset of A × A. Such a relation is called a binary relation. Let a,b,c $\in$ A. Then: a) R is called reflexive if (a,a) $\in$ R. b) R is called antisymmetric if when (a,b)$\in$ R and (b,a) $\in$ R, then a = b. c) R is called transitive if when (a,b)$\in$ R and (b,c) $\in$ R, then (a,c)$\in$ R. d) R is called symmetric if when (a,b)$\in$ R, then (b,a) $\in$ R e) R has the connex property if for every a,b $\in$ A, either (a,b)$\in$ R or (b,a) $\in$ R. f) R is called trichotomous if exactly one of the following conditions holds: (a,b)$\in$ R, (b,a) $\in$ R or a=b. (In other words, if (a,b)$\in$ R and a$\neq$b, then (b,a) $\notin$R. A relation that satisfies this property is called asymmetric.)

Note: It can confusing for beginners what the difference is between property (b) and property (f). These properties refer to 2 different but related relations on A. (f) is a stronger condition and it requires that condition (a) is false for any relation that (f) is true of. The classic example of a trichotomous relation is the relation “< or >“ on ℝ. Clearly this relation is anti-symmetric-for every a,b$\in$ ℝ, a < b and b < a can only be true if a = b because otherwise, we have a logical contradiction. But clearly, a < a or a >a is also a contradiction for the exact same reason. So $(a,a)\notin R$ and the relation is not reflexive on ℝ! So any asymmetric relation is antisymmetric, but the converse is not true. Now we can define some important kinds of relations in mathematics: Def: Let R be a binary relation on a set A. If R is reflexive, transitive and antisymmetric (properties (a)-(c)), we say R is a partial ordering on A. If A has a partial ordering and in addition has property (e), then we say A is a totally ordered set. If a totally ordered set has a second binary relation R’ on A such that property (f) holds, then we call this relation a strict total ordering on A.

We first need to state precisely what “≥” on ℝ means. Since we’ve avoided an explicit construction of ℝ beyond the brief one from ℚ given by Dresden, we’re going to state certain results proven in a detailed construction axiomatically i.e. by definition. Let’s assume ℝ with the usual arithmetic operators + and × that you remember from high school with the usual properties of commutative, associative and distributive laws of algebra. We also assume the absolute value as defined by Dresden in chapter 3. Def: We define 0$\in\mathbb ℝ $ as the unique real number such that for any a$\in\mathbb ℝ $, a + 0 = a. We define 1 as the unique real number where 1 ≠ 0 and for every a $\in\mathbb ℝ$, 1× a = a.

Def: Let a $\in\mathbb ℝ$. Then the negative of a, denoted –a, is the unique real number such that a + -a = 0.

We now define axiomatically a unique subset of ℝ that will allow us to rigorously define “≥”. It will also eventually permit us to give a more rigorous definition of the absolute value that’s consistent with modern usage.

Def: Let x,y$\in\mathbb ℝ $.Then there exists P$\subset\mathbb ℝ $, denoted P, that satisfies the following 2 axioms:

(i) P is closed under + and × i.e. x,y$\in P$ implies x + y$\in P$ and x × y $\in P$.

(ii) For every real number x$\in \mathbb R$, either x$\in P$, x = 0 or - x$\in P$.

We can now use P, called the positive class of the reals, to rigorously define the relation “≥”. Def: Let x $\in\mathbb R$. Then x ≥ 0 if and only if either x $\in P$ or x = 0. Similarly, we say x$\leq$ 0 if and only if either –x $\in P$ or x =0. Now let a,b,c $\in\mathbb R$. such that c = b − a. Then c ≥ 0 $\longrightarrow $ b – a ≥ 0 $\longrightarrow $ b ≥ a. Similarly, c $\leq $0 $\longrightarrow $ b – a $\leq$ 0 $\longrightarrow $ b $\leq$ a.

Now we’ll prove the relation gives a total ordering.

1) Reflexive: Let x ∈ℝ. Then, x ≥ x $\longrightarrow $ x - x ≥ 0, which is true since x - x =0. Thus, (x,x)∈ℝ×ℝ. 2) Anti-symmetric: Let (x,y)∈ ℝ×ℝ and (y,x)∈ ℝ×ℝ. Then, x≥y and y≥x. If x=y $\longleftrightarrow $ y=x, then it’s trivial. Assume x≠y. Then either x > y or y >x. If x >y, then x−y > 0. If y >x, then y−x >0. These cannot both be true because then because P is closed under addition, (x−y) + (y-x) >0 $\longleftrightarrow $ 0 >0, which is a contradiction. So the only time when this holds is when x and y are the same value. Therefore, x=y and the relation is anti-symmetric. 3) Transitive: Let (x,y)∈ ℝ×ℝ and let (y,z)∈ ℝ×ℝ. Thus, x≥y and y≥z. If x≥y , then either x−y $\in P$ $\longrightarrow $ x−y > 0 or x−y =0. Similarly, if y≥z , then either y−z $\in P$ $\longrightarrow $ y−z > 0 or y-z =0. We now check each possible case. If x−y$\in P$ and y−z =0, then y=z and x−z $\in P$, so x≥z. Similarly, if y−z $\in P$ and x =y , then x−z $\in P$ , so x≥z. Clearly if x= y = z, then x =z and (x,z)∈ ℝ×ℝ. There is just one case left to check: if x >y and y > z. If so, then x –y $\in P$ and y – z $\in P$ . By closure of P, (x –y) + (y – z) = x – z $\in P$ . Thus, x≥z. Therefore, (x,z)∈ ℝ×ℝ in all cases and transitivity is proven.. We lastly have to prove the connex property i.e. that for any x,y ∈ℝ, (x,y) or (y,x) ∈ℝ×ℝ. Let’s prove it by contradiction. Assume neither ordered pair is in the relation. Then x < y and y < x, which is clearly impossible. So at least one of these ordered pairs has to be present. So the relation is comparable and is therefore a total ordering on ℝ! Q.E.D

---

Edit: I've gone back and cleared up all the MathJax text as best I can. I'm gonna check it carefully against the original Microsoft Word document, but it looks correct. I'll be very grateful to whoever responds.

Answer 1

This is a comment.

I prefer definitions to use "iff" , not "if" because in almost all cases in almost all books, that is what is actually meant. I think you should include quantifiers. I think you should delete the word "called". E.g.

$R$ is reflexive iff $\forall a\in A\,(\, (a,a)\in R)$

or: $R$ is reflexive iff $(a,a)\in R$ for all $a\in A.$

I think you should not label the properties as a), b),c), etc., because you are also using these letters for members of $A,$ which makes it harder to read and to digest.

I think Symmetric and Anti-Symmetric should be listed consecutively.

Two simple examples of a transitive $R$ (property c)) without Trichotomy (property f)) are (1): $R=A\times A$ when $A$ has more than 1 member, and (2): $R=\emptyset \ne A.$

Many books say a relation "satisfies Trichotomy" so perhaps you should mention that this means the same as "Trichotomous".

Answer 2

Just a few comments.

1) It would be clearer just to define directly "$x\geq y$ iff $x=y$ or $x-y \in P$ " (and avoid $c\geq 0 \rightarrow a-b\geq 0 \rightarrow a \geq b$ since I don't understand what these arrows mean )

2) A weird thing is that the order depends on $P$. The set $P$ satisfying the listed properties is unfortunately not unique (just apply to it a element of the infamous group $Gal(R/Q)$)

3) It seems you don't use the fact that $P$ is closed under multiplication. Why require it in that case ?

Answer 3

On the very first line of the proof you write

1) Reflexive: Let x ∈ℝ. Then, x ≥ x ⟶ x - x ≥ 0, which is true since x - x =0. Thus, (x,x)∈ℝ×ℝ.

The "(x,x)∈ℝ×ℝ" says nothing and should be removed. The proof of reflexivity is automatic by definition, but if you insist on proving it it should look like

For any $x \in ℝ$, blah, blah, blah, so therefore $x \ge x$. PERIOD!

Elsewhere in your proof you claim again that coordinate pairs belong to ℝ×ℝ, without adding anything that isn't already known.

Here is 'canonical' transitivity argument:

$\tag1 a \le b \implies a + u = b, \; u \ge 0$ $\tag2 b \le c \implies b + v = c, \; v \ge 0$

Adding $v$ to both sides of the (1),

$\tag 3 (a + u) + v = b + v =^{by \; (2)} c$

or

$\tag 4 a + (u + v) = c$

Since $u + v \ge 0$ we have $a \le c$.

The antisymmetry is handled the same way - set up $\text{(1)}$ and $\text{(2)}$ and 'turn the algebra crank'.

For the connex property, you know that for ever $u \in \mathbb R$, if $u \ne 0$, either $u \in P$ or $-u \in P$. So set $u = y -x$ and see what happens.

Answer 4

I went through your proof. I think the proof of connex property is at least not complete (especially if you want it to be completely elementary). Why does it follow that if neither $x\geq y$ and $y\geq x$ then $x<y$ and $y<x$? I don't see $<$ defined anywhere. You can add this definition and show that this is true, but I would say to be complete you need to explain this.

In general I would say the proof is needlessly complicated and tedious because of how you defined $P$. Is there a reason you define $P$ like that? If you add $0$ in $P$, it simplifies the proof a lot and makes it much more readable. I would do the following: First of all define $P$:

1. $0\in P$
2. $P$ is closed under addition
3. for any $a\neq 0$: $a\in P$ XOR $-a\in P$.

Then define $x\geq y$ if and only if $x-y\in P$.

Observation: $-(x-y)=y-x$. This follows from the uniqueness of $-a$ and by the fact that $x-y+(y-x)=0$.

Reflexivity: Since $x-x=0$ and $0\in P$ we have $x\geq x$.

Antisymmetry: If $x\geq y$ and $y\geq x$ then by the observation above $x-y, -(x-y)\in P$ so $x-y=0$, and therefore $-y=-x$ which implies that $x=y$ (to show this observe that $x-x=0$ therefore $x-x--x=--x$ therefore $x=--x$).

Transitivity: If $x-y\in P$ and $y-z\in P$ the $x-y+y-z\in P$ i.e. $x-z\in P$.

Connex: Since $x-y=-(y-x)$ by definition of $P$ if follows that $x-y\in P$ or $y-x\in P$.

PS: As others mentioned you should also change this $(x,y)\in \mathbb{R}\times\mathbb{R}$ to $(x,y)\in\geq$.