[Math] Is a total order compatible with a partial order

discrete mathematicsrelations

I was given the following multipart problem.

Part 1: Consider the poset ({2,4,6,9,12,18,27,36,48,60,72},|), with the indicated integers and the divides relation. Find the following, if they exist; if they don’t exist, explain why they don’t.

Maximal and minimal elements? Max: 27, 48, 60, 72. Min: 2,9.

Least upper bound of {2,12}? 12.

Greatest lower bound of {60,72}? 12.

I drew out a Hasse diagram and think I solved those 3 questions correctly, although I would appreciate if someone could confirm.

Then comes the next part:

Suppose we impose the following total order on the set: 2,4,18,6,27,12,36,9,72,60,48. Is this compatible with the partial ordering of the divides relation? Why or why not?

I just don't even get what this is asking at all. I understand what a poset and total ordering are, but what does is it mean "is it compatible?". The only thing I can think of is that it's not actually a total order. Given the Hasse diagram, the order given doesn't seem to work. Any help would be appreciated, thanks.

Best Answer

This answer basically just confirms what it appears from the comments that you’ve already understood.

Let $\langle P,\le\rangle$ be a partial order, and let $\preceq$ be a linear (total) order on $P$. The order $\preceq$ is compatible with the partial order $\le$ if the following condition is satisfied:

for all $x,y\in P$, if $x\le y$, then $x\preceq y$.

In other words, $\le$ and $\preceq$ never assign opposite orders to any pair of elements of $P$; either they assign the same order, or $\le$ doesn’t assign any order to that pair.

In your problem, $\preceq$ is given by

$$2\prec4\prec18\prec6\prec27\prec12\prec36\prec9\prec72\prec60\prec48\;.$$

As you noted in the comments, this disagrees with the order $\le$ on the pairs $\{6,18\}$, $\{9,18\}$, and $\{9,27\}$, so it’s not compatible with the partial order $\le$.

Related Solutions

[Math] Partial Order Relations and Total Order Relations

Counting the partial order relations is a bit messy. Perhaps the most straightforward way is to organize them by their ‘shapes’. In the following diagrams the order is from bottom to top.

They can be linear:
```
 *  
 |  
 *  
 |  
 *
```
They have a minimum element but no maximum:
```
 *   *  
  \ /  
   *  
```
They can have a maximum but no minimum:
```
   *  
  / \  
 *   *
```
They can have two related elements and one unrelated element:
```
 *  
 |   *  
 *
```
They can have three unrelated elements:
```
 *   *   *
```

You’ve already counted the partial orders that are linear: there are indeed $3!=6$ of them. Now you just have to count the partial orders of types (2)-(5) above. To get you started, in type (2) any one of the three elements of $A$ can be the minimum element. Once you’ve chosen that, however, the partial order is completely determined:

    1   2                  2   1  
     \ /        and         \ /  
      3                      3

are the same partial order, just drawn differently. Thus, there are $3$ partial orders of type (2) on $A$.

[Math] Establishing A Covering Relation

So, the key for understand why it is a proper subset is the symbol $\prec$ compared to the symbol $\preceq$. If $(P,\preceq)$ is a poset, then $x\prec y$ means "$x\preceq y$ and $x\neq y$."

Now, in the specific poset, $(P,\preceq) = (S,\subseteq)$, where $S$ is the set of all subsets of $\{a,b,c\}$. $S$ is a set with $8$ elements. We can list $S$ explicitly: $$S=\{\emptyset,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}$$.

It might be easier if you don't use $A,B,C$ for elements of $S$, since it might confuse the question between the lower case letters, $a,b,c$. Instead, let's use $X$, $Y$, and $Z$ for elements of $S$.

So $Y$ covers $X$ if (1) $X\prec Y$, and (2) there is no $Z\in S$ such that $X\prec Z\prec Y$.

(1) means $X\preceq Y$ and $X\neq Y$, But $\preceq$ in this poset is just $\subseteq$. So $X\preceq Y$ means $X\subseteq Y$. So necessarily, if $Y$ covers $X$, then $X$ is a subset of $Y$ and $X\neq Y$. But that is just the the definition of "$X$ is a proper subset of $Y$."

$Y=\{a,b,c\}$ is not a cover for $X=\{a\}$ because $Z=\{a,b\}$ has the property $X\prec Z\prec Y$, which violates the definition of "$Y$ is a cover for $X$."

Best Answer

Related Solutions

[Math] Partial Order Relations and Total Order Relations

[Math] Establishing A Covering Relation

Related Question