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 reformatted your post, but now, looking at the question immediately following your given poset, I'm not sure if I correctly interpreted what you were trying to say. Check to make sure.2012-11-28
  • 0
    Alright so I understand that the arrangement of the elements themselves do not matter much. But I suppose I should rephrase what I am trying to figure out is that given the poset ⟨{2,4,6,9,12,18,27,36,48,60,72},|⟩ is the total ordering imposed: 2,4,18,6,27,12,36,9,72,60,48 compatible with the partial ordering of the divides relation. Would I be thinking in the right direction if I said that the total order is compatible?2012-11-28
  • 0
    Aha! I see. That makes much more sense.2012-11-28
  • 1
    The right term here is [linear extension](http://en.wikipedia.org/wiki/Linear_extension)2012-11-28
  • 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$.

  • 0
    Check the most recent edit.2012-11-28
  • 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
    In that case then, another example from this would also be that since 6|18 but 18 is less than 6 in the order, this also makes it not compatible, am I correct?2012-11-28
  • 0
    Absolutely right.2012-11-28