Linear Order relations
Im having a slight issue grasping the concept of Linear Orders among relations.
It was made apparent to me that linear orders must first be partial orders(reflexive, anti-symmetric and transitive) and in addition, for all (a,b)∈A (for example). either (a,b)∈R OR (b,a)∈R but not both. e.g. (1,3)∈R and (3,1)∉R
However, my issue is, i feel that this would always be the case as a partial order is antisymmetric anyway
Where am I going wrong here?
$\endgroup$ 11 Answer
$\begingroup$That last property isn’t antisymmetry. Antisymmetry says that if $\langle a,b\rangle$ and $\langle b,a\rangle$ are both in $R$, then $a=b$; that last property implies that $R$ doesn’t contain both $\langle a,b\rangle$ and $\langle b,a\rangle$ in the first place i.e., that $R$ is asymmetric.
Note that a reflexive relation cannot be asymmetric unless the underlying set is empty: pick any $a$, and you have both $\langle a,a\rangle$ and its (indistinguishable!) reversal $\langle a,a\rangle$ in the relation, exactly what asymmetry explicitly rules out. In particular, a partial order on a non-empty set cannot be asymmetric. What it does have is comparability: for any $a$ and $b$, either $\langle a,b\rangle\in R$ or $\langle b,a\rangle\in R$. Then antisymmetry tells you that if both of these occur, it must be the case that $a=b$. In other words, it says that you cannot have both $\langle a,b\rangle\in R$ and $\langle b,a\rangle\in R$ when $a$ and $b$ are distinct.
There is also a notion of a strict linear order: this is a relation $R$ that is transitive and totally irreflexive (meaning that $\langle a,a\rangle$ is never in $R$) and has the property that for any distinct elements $a$ and $b$ of the underlying set exactly one of $\langle a,b\rangle$ and $\langle b,a\rangle$ is in $R$. The relation $<$ is a familiar example of a strict linear order; $\le$, on the other hand, is an example of a linear order in the usual non-strict sense, i.e., the kind that is a special case of partial relations.
$\endgroup$
