1
$\begingroup$

I'm reading about partial ordering, I know by definition it means reflexive, antisymmetric, and transitive. But the examples in my textbook that confused me are of the form:

There is a ordering/relation, and the "less than" of this relation is defined as follow [...] Now by adding equality to this ordering it becomes a partial ordering.

But how can I prove that the ordering/relation is reflexive only given its "less than" condition? e.g.

lexi1

My try:

Say this ordering relation is $R$ and it's denoted by $\prec$. For any $a\in R,$ since $a\not\prec a$ because neither $(a_1, a_2,\dots,a_t)\prec$ itself nor $m\lt n$ (since $m=n$). Then I stuck at this step.

--

Am I on the correct path proving reflexive from antisymmetric? Or reflexive is defined on the set, so this property don't have to be proved?

--

another one that similar but I also don't know how to prove:

enter image description here

$\endgroup$
2
$\begingroup$

As you observed, any of these "less than" relations is NOT a partial ordering — exactly because it's not reflexive. They are antisymmetric and transitive, though — which, of course, shouldn't be taken for granted, but should be verified for each example. But then we can define another "less than or equal to" relation, which will be a partial ordering. In other words, each of the examples above talks about two different (but closely related, no pun intended) relations — "less than" and "less than or equal to".

I can agree that this text is a bit sloppy at times not to distinguish them clearly enough. For example, in the end of your first screenshot, the phrase

The verification that this is a partial ordering is left as Exercise 38 …

appears to be talking about the "less than" relation, for which it isn't true — of course, the question is actually about the "less than or equal to" version. (Maybe it is made clear in the exercise?)

In other words, you can think of this as a two-step definition.

  1. First, a certain relation $\prec$ is defined. It's pretty much an ordering, being antisymmetric and transitive. But technically speaking it's not a partial ordering because it's not reflexive.
  2. Then the actual lexicographic ordering $\preccurlyeq$ is defined as follows: $a\preccurlyeq b$ if and only if either $a\prec b$ or $a=b$. Using properties of $\prec$, we can prove that it is a partial ordering. Proving the reflexivity part is vacuous, since it's part of the definition.

P.S. And no, you can't prove reflexive from antisymmetric, as these are two different properties, and neither implies the other.

$\endgroup$
1
  • $\begingroup$ So reflexive-ness of lexicographic ordering is to fit our understanding of the world? So it's in the definition? Math aside, thank you! $\endgroup$ – linear_combinatori_probabi Jul 5 '18 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.