A different definition of partial ordering

407 Views Asked by At

So far from what I've found on the internet, every definition of a non-strict partially ordered set uses these axioms:

$1.$ reflexivity

$2.$ antisymmetry

$3.$ transitivity

But in a textbook from my university, there is another definition which uses these axioms:

$1.$ asymmetry

$2.$ transitivity

The textbook also states that the strict order is a partial order that is trichotomous.

How do these two definitions correlate? Why are they not equal (since the first definition requires reflexivity and the second one forbids it by asymmetry)? What is the motivation behind the second definition?

edit: I apologize for inconvinience. The book doesn't really uses terms non-strict and strict, but rather partial order and order. It's not written in English and I thought there were only two widely used types of orders, namely a strict order and a non-strict order. So perhaps I only confused terminology.

1

There are 1 best solutions below

10
On BEST ANSWER

A relation is asymmetric if and only if it is anti-symmetric and irreflexive.

So, the second definition can be rewritten as:

  1. Irreflexive

  2. Anti-symmetric

  3. Transitive

And now the relation between the two definitions is a little more clear: they are both transitive and anti-symmetric, but the strict one is irreflexive, and the non-strict one is reflexive.

Note that a 'non-strict' partial order is not the same as a relation that is anti-symmetric, transitive, but not strict, for it could be anti-symmetric, transitive, but neither reflexive nor irreflexive ... I also wish there was a term for relations that are anti-symmetric and transitive (and I believe 'order' fits the bill just right) ... but I get the impression that we don't consider such 'in-between orders' because they are mathematically not that interesting ... see also:

Orders, Partial Orders, Strict Partial Orders, Total Orders, Strict Total Orders, and Strict Orders

As far as the connection with trichotomy goes: There I do not understand the textbook. Trichotomy for any relation $R$ is that for any two objects $x$ and $y$: $xRy$ or $yRx$ or $x=y$. Put differently: if $x \not = y$, then either $xRy$ or $yRx$, which is also known as a 'connex' relationship: every two different elements are 'connected'. Thus, for example, $\subseteq$ is not connex, as $\{ 1 \}$ and $\{ 2 \}$ do not stand in the $\subseteq$ relation in any way, but $\le$ is connex ... which is also why we call it a 'total' order (a relation is 'total' when for any $x$ and $y$, either $xRy$ or $yRx$ ... note that connex/trichotomy plus reflexive implies total).

But $\le$ is clearly not strict. That is, $\le$ is a partial order that is connex (i.e for which trichotomy holds), but it is not a strict partial order.

So, frankly, I disagree with the book on that one: the difference between 'non-strict' and 'strict' is not 'connex' or trichotomy (that is the difference between partial and total). Rather, the difference between 'strict' and 'non-strict' is the difference between reflexive and irreflexive.