Totally ordered set

https://arbital.com/p/totally_ordered_set

by Joe Zeng Jul 5 2016 updated Jul 21 2016

A set where all the elements can be compared as greater than or less than.


[summary: A totally ordered set is a pair $~$(S, \le)$~$ of a set $~$S$~$ and a total order $~$\le$~$ on $~$S$~$, which is a binary relation that satisfies the following properties:

  1. For all $~$a, b \in S$~$, if $~$a \le b$~$ and $~$b \le a$~$, then $~$a = b$~$. (the antisymmetric property)
  2. For all $~$a, b, c \in S$~$, if $~$a \le b$~$ and $~$b \le c$~$, then $~$a \le c$~$. (the transitive property)
  3. For all $~$a, b \in S$~$, either $~$a \le b$~$ or $~$b \le a$~$, or both. (the [total_relation totality] property)]

A totally ordered set is a pair $~$(S, \le)$~$ of a set $~$S$~$ and a total order $~$\le$~$ on $~$S$~$, which is a [-binary_relation] that satisfies the following properties:

  1. For all $~$a, b \in S$~$, if $~$a \le b$~$ and $~$b \le a$~$, then $~$a = b$~$. (the antisymmetric property)
  2. For all $~$a, b, c \in S$~$, if $~$a \le b$~$ and $~$b \le c$~$, then $~$a \le c$~$. (the transitive property)
  3. For all $~$a, b \in S$~$, either $~$a \le b$~$ or $~$b \le a$~$, or both. (the [total_relation totality] property)

A totally ordered set is a special type of partially ordered set that satisfies the total property — in general, posets only satisfy the reflexive property, which is that $~$a \le a$~$ for all $~$a \in S$~$.

Examples of totally ordered sets

The real numbers are a totally ordered set. So are any of the subsets of the real numbers, such as the rational numbers or the integers.

Examples of not totally ordered sets

The complex numbers do not have a canonical total ordering, and especially not a total ordering that preserves all the properties of the ordering of the real numbers, although one can define a total ordering on them quite easily.


Comments

Kevin Clancy

A totally ordered set $~$(S, \\le)$~$ is a set $~$S$~$ with a comparison operator $~$\\le$~$ that is defined for all members of $~$S$~$\.

Correct me if I'm wrong, but isn't it idiosyncratic to define $~$\leq$~$ as a predicate rather than a relation? I know of at least three books that describe it as a relation: The Joy of Sets by Devlin, Principles of Mathematical Analysis by Rudin, and Introduction to Lattice and Order by Davey and Priestly.

Also, isn't $~$\leq$~$ called an order rather than a comparison?

I bring this up because I would like there to be consistency between this page and the Partially ordered set page. I think both pages should follow the conventions of mathematics.

Joe Zeng

The word "binary predicate" I got from Wikipedia's article on ordered fields, but it looks like it redirects to "binary relation" anyway, so I'll change that.

And "comparison operator" is the terminology in computer science (or at least the one commonly used in programming languages); I wasn't aware that the operator was called an "order" in mathematics in general.