# What does it mean that numbers are “totally ordered”, in the Paxos Made Simple paper?

I was studying Paxos from the paper by Lamport called "Paxos Made Simple".

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

On page 3, it says

Since all numbers are totally ordered, condition P2 guarantees the crucial safety property that only a single value is chosen.

where P2 is the following

If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

What does it mean for numbers to be totally ordered? How is this property essential for condition P2 to guarantee safety?

• When applied to elements of a set, "totally ordered" means that there is an order relation between the elements of that set such that you can always compare 2 elements taken in the set. Integers, or reals are totally ordered sets. Given 2 distinct integers, there is always one that is greater than the other. Such relations are useful when they obey some properties w.r.t. operations on the elements of the set. – babou Mar 28 '14 at 17:13

Totally ordered means that there exists an order relation such that given any two elements, one is greater than the other. In other words, there are no incomparable elements. For example, the real numbers are totally ordered: either $x \le y$ or $y \le x$. Counter-example: set inclusion $\subseteq$ is an order relation, but $\{0\}$ and $\{1\}$ are incomparable.
Suppose that two proposals numbered $n_1$ and $n_2$ are chosen, with values $v_1$ and $v_2$ respectively. The desired safety property is that the values are in fact the same: $v_1 = v_2$. By condition P2, if $n_1 \le n_2$, then proposal $n_2$ is higher-numbered than proposal $n_1$, so its value $v_2$ is equal to $v_1$. Similarly, if $n_2 \le n_1$ then $v_1 = v_2$. The fact that the integers are totally ordered implies that at least one of the propositions $n_1 \le n_2$ and $n_2 \le n_1$ is true, and therefore either way $v_1 = v_2$.