Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  Cameron Buie Nov 28 '12 at 0:51
    
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? –  verovdp Nov 28 '12 at 1:20
    
Aha! I see. That makes much more sense. –  Cameron Buie Nov 28 '12 at 1:22
1  
The right term here is linear extension –  Jair Taylor Nov 28 '12 at 1:31
    
I have not come across that term yet before, I'll have to investigate. Thanks for bringing it up! –  verovdp Nov 28 '12 at 1:49

4 Answers 4

up vote 1 down vote accepted

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

share|improve this answer
    
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? –  verovdp Nov 28 '12 at 1:52
    
Absolutely right. –  Cameron Buie Nov 28 '12 at 2:19

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$.

share|improve this answer

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$.

share|improve this answer
    
Check the most recent edit. –  Asaf Karagila Nov 28 '12 at 2:24
1  
Hey, Asaf. +1 in the name of sportsmanship, (and for quality of post, of course!) –  amWhy Dec 1 '12 at 0:58

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\}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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