Basic confusion about a linear order.

[gottfried]

According to wikipedia a total order ≤ on a set X is one such that
If a ≤ b and b ≤ a then a = b (antisymmetry);
If a ≤ b and b ≤ c then a ≤ c (transitivity);
a ≤ b or b ≤ a (totality).

I'm wondering why antisymmetry is a condition since, as far as I can see, totality discounts antisymmetry. So suppose I'm trying to prove that R is a total order would it be sufficient to prove only transitivity and totality?

 

[micromass]

Consider the set $X=\{1,2\}$. Define the order relation $1<2$ and $2<1$. This is transitive and total, but not anti-symmetric. So anti-symmetry is not a void condition.

 

[gottfried]

Why is that total?

 

[micromass]

Total means that for each two elements $a$ and $b$, we have $a\leq b$ or $b\leq a$.

There are four choices here:
Either $a=1$ and $b=1$, then $1\leq 1$ holds since $1=1$.
or $a=2$ and $b=2$, then $2\leq 2$ holds since $2=2$.
or $a=1$ and $b=2$, then $1\leq 2$ holds since $1<2$ ($2\leq 1$ holds as well, but that's not needed)
or $a=2$ and $b=1$, then $1\leq 2$ holds since $1<2$ ($2\leq 1$ holds as well, but that's not needed)

 

[gottfried]

I see. I was under the impression total meant one or the other rather than atleast one or the other.

 

[micromass]

I see. I was under the impression total meant one or the other rather than atleast one or the other.

Aaah, that explains it!

This is very important. If you see the word "or" in a mathematics text than that almost always means at least one or the other. This is contrast with our daily life where "or" means that both can't occur. Keep this in mind when reading a math text or article!

The "or" from our daily life is occasionaly written as xor and means the exclusive or.

 

[gottfried]

Cool, that is a very good thing to know.