1
$\begingroup$

I'm working on a thought problem for an introductory discrete math course and seem to be stuck on how to solve this problem. If we have a poset:

$\bigl\langle\{2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72\},\: |\:\bigr\rangle,$

and impose a total order on the set such that the elements from least to greatest are: $2, 4, 18, 6, 27, 12, 36, 9, 72, 60, 48$,

is the total order compatible with the partial ordering of the divides relation? I know that if the elements in the poset are arranged in increasing order that it works, but I am not sure with this particular ordering. Can anyone help?

  • 0
    I have not come across that term yet before, I'll have to investigate. Thanks for bringing it up!2012-11-28

4 Answers 4

0

It might suit your purpose to exhibit two sets, one where divides and less than or equal are compatible and another where they are not. If each element greater than the smallest is a multiple of the next smaller, the orders will be the same. An example would be $\{1,2,6,18,90,360\}$.

4

Assuming the edits are correct, then

$\bigl\langle\{2, 4, 18, 6, 27, 12, 36, 9, 72, 60, 48\},\: |\:\bigr\rangle = \bigl\langle\{2, 4, 6, 9, 12, 18, 27, 36, 48, 60, 72\},\: |\:\bigr\rangle, $

That is, a set is a set is a set...Within the set, the arrangement of or the order in which the elements in the set appear doesn't matter. So if you're more comfortable with increasing magnitude, that's fine.

The partial order defined by "|" is imposed on the set, as in "$a$ is related to $b$ if $a$ divides $b$," but it doesn't require that the elements be listed in any particular order.
Just don't confuse the "less than" relation with the "|" relation!

Order does matter when listing ordered pairs of elements related by some partial order relation $\mathcal{R}$. For example, if $(a, b)$ denotes a pair of elements such that $a|b$, then $(2, 6) \in \mathcal{R}$, but $(6, 2) \notin \mathcal{R}.$



Update: No, the total order thus imposed is not compatible with the partial order "|". Just one counterexample suffices: $6|18$, but under the total order, $18$ is "less than" $6$.

1

You are given a set, and two orders. One is a partial order, $x|y$ and another is a linear order, $\preceq$. You are asked whether or not they are compatible, or rather does the linear order extends the partial order.

To show that they do you need to show that if $x|y$ then $x\preceq y$. In order to show they are incompatible you need to find a counterexample that $x|y$ but $y\prec x$. If no such counterexample is found, then you should begin to attempt and write a proof.

Just go through the list and look whether there is a number $x$ that one of its divisors appear after $x$.

  • 1
    Hey, Asaf. +1 in the name of sportsmanship, (and for quality of post, of course!)2012-12-01
1

It is not compatible. For example, $9|36$, but in the total order, $36$ is less than $9$.

  • 0
    Absolutely right.2012-11-28