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.

The question I am looking at is, "Answer these questions for the poset $(\{3,5,9,15, 24,45\},|)$."

a) Find the maximal elements.

b)Find the minimal elements.

c) Is there a greatest element?

d) Is there a least element?

e) Find all upper bounds of $\{3,5\}$.

f) Find the least upper bound of$\{3,5\}$, if it exists.

g) Find all lower bounds of $\{15,45\}$.

h)Find the greatest lower bound of $\{15,45\}$, if it exists.

I have answers, I just want to make certain that I answered them properly, used the proper reasoning to answer them, and used the terminology correctly.

For a): For elements in the poset to be a maximal element, it has to be divisible by all the elements it is comparable to. The elements 24 and 45 are maximal, because they are divisible by every element they are comparable to. The reason why neither maximal element is comparable to the other is because $24|45$ and $45|24$ are both false statements.

For b): For elements in the poset to be minimal, is for them to be able to divide all other elements, in the relation, they are comparable to. $3|5$ and $5|3$ are both false statements, meaning they are incomparable elements, and since they divide every element they are comparable, they are minimal elements of the poset.

For c): No, because 24 and 45 are incomparable elements, meaning one doesn't precede the other.

For d): No, because 3 and 5 are incomparable elements, meaning one doesn't precede the other.

For e): To find the upper-bound of the set $\{3,5\}$, with respect to the poset, is to find all of the elements that both 3 and 5 divide. These elements are 15 and 35.

For f): To find the least upper-bound of the set $\{3,5\}$, is to consider the upper-bounds, and find the one that divides the others. $15|45$, so 15 is the least upper-bound.

For g): To find the lower bounds of the set $\{15,45\}$, with respect to the poset, is to find the eleents that divide into 15 and 45. These elements are 3,5, and 15.

For h): To find the greater lower bound of the set $\{15,45\}$, is to consider the lower bounds, and see which one is divisible by them all. $3|15$ and $5|15$, therefore 15 is the greatest lower bound.

I have a few other questions. If you have more than one extremal element, is it possible to have a greatest or least element? For parts a through d, I used this comparability argument; but now I don't feel so confident that it was the proper argument to use. If the comparability argument is correct, could someone explain to me why?--I answered this question yesterday, yesterday was so long ago.

share|improve this question
    
Did you write down the poset's elements ordered, or if not what's the order on that set? –  DonAntonio Nov 18 '12 at 15:01
    
@DonAntonio The order on the relation is divisibility $|$. –  Mack Nov 18 '12 at 15:02
    
Ok...so then why didn't you write? –  DonAntonio Nov 18 '12 at 15:09
1  
@DonAntonio: The poset is defined here using the ordered pair ("set in question", order on the relation) - it's easy to miss the "|" symbol following the set in question. Perhaps EMACK, it would help draw attention to the order by stating, in words, "Note that the order is given by $a\sim b$ iff $a|b$" –  amWhy Nov 18 '12 at 15:15
1  
+1 EMACK....... –  amWhy Nov 18 '12 at 21:55
show 3 more comments

2 Answers 2

up vote 5 down vote accepted

First: let's review definitions, keeping in mind that "$\leq$" simply represents "any" partial order on a given set $P$. (In your case, the order relation of "$\mid$" replaces the relation $\leq$, and "is a multiple of" replaces $\geq$.) Can you figure out what these definitions tell you in terms of your given relation?

Given a set $P$ and an order relation $\leq$:


Greatest element and least element:
An element $x$ in a partially ordered set $P$ is a greatest element if for every element $a \in P, a \leq x.$ An element $y\in P$ is a least element if for every element $a \in P, a \geq y$.

  • That is, in your case, $x\in P$ is a greatest element if for every $a$ in $P$, $a\mid x$. And $y\in P$ is a least element if for every $a\in P,\;y\mid a$.
  • So in your example above, there is neither a greatest nor a least element in the set, given the relation "|".

A poset can only have one greatest or least element.


Maximal elements and minimal elements:
An element $x \in P$ is a maximal element if there is no element $a \in P$ such that $a > x$. Similarly, an element $y \in P$ is a minimal element if there is no element $a \in P$ such that $a < y$. If a poset has a greatest element, it must be the unique maximal element, but otherwise there can be more than one maximal element, and similarly for least elements and minimal elements.

  • This addresses your first question: "If you have more than one extremal element, is it possible to have a greatest or least element?" No. If an element $x$ is the greatest element of the set $P$, meaning that every element in $P$, including $x$, divides $x$, it is the unique maximal element. Likewise for a least element: in your case, that would mean if there were any element, like, e.g., $1$ in the set that it divides every element, including itself, of the set $P$, then it would be the unique minimal element. So if you have more than one maximal (minimal) element in the set, there cannot be a greatest (least) element in the set.
  • In terms of comparability. You are on target with your take on whether or not elements are comparable under a particular ordering relation comparability, and how that impacts the determination of extrema.

Upper and lower bounds:
For a subset $A \subset P$, an element $x \in P$ is an upper bound of $A$ if $a \leq x$, for each element $a \in A$. In particular, $x$ need not be in $A$ to be an upper bound of $A$. Similarly, an element $x \in P$ is a lower bound of $A$ if $a \geq x$, for each element $a \in A$. A greatest element of $P$ is an upper bound of $P$ itself, and a least element is a lower bound of $P$.

  • Given your edit, and the corresponding answers, it seems you have a good grasp of this.

Comparability
Any two elements $x$ and $y$ of a set $P$ that is partially ordered by a binary relation $\leq$ are comparable when either $x \leq y$ or $y \leq x$. If it is not the case that $x$ and $y$ are comparable, then they are called incomparable. A totally ordered set is exactly a partially ordered set in which every pair of elements is comparable.

  • In your partially ordered set call it $P$, under "|", for any $x, y\in P$, $x$ and $y$ are comparable if and only if either $x|y$ or $y|x$, as you seem to understand.

share|improve this answer
    
To answer your question, "Can you figure out what these definitions tell you in terms of your given relation?": If $a$ and $b$ are in the poset, and $a|b$, then $a$ precedes $b$; but if $a$ is a multiple of $b$, then b precedes a. "Note what this entails in terms of comparability." x can only be a maximal with respect to the elements it is comparable to? Similarly, x can only be a minimal with respect to the elements it is comparable to? –  Mack Nov 18 '12 at 18:41
1  
Yes, your first answer in your comment is correct. A maximal element (as a minimal element) is maximal (minimal) in $P$. It can be an upper bound (lower bound) of a subset of $P$, all of whose elements are those with which it is comparable. –  amWhy Nov 18 '12 at 19:07
    
EMACK: Yes, I think you are correct in terms of what you've arrived at, (your answers), given the updated post! You seem to have an understanding of the concepts in question. –  amWhy Nov 18 '12 at 19:56
1  
EMACK: nice work, all in all! –  amWhy Nov 18 '12 at 21:24
add comment

The general issues have been covered by amWhy, but I still want to comment on some of your answers.

(a) Neither $24$ nor $45$ is even in the set, so neither can be maximal. The maximal elements are $27,48,60$, and $72$: none of them divides any member of the set except itself. The other elements all divide $72$ and therefore are not maximal.

(b) Again, neither $3$ nor $5$ is even in the partial order, so neither can be minimal. $2$ is minimal: no element of the set is a proper divisor of $2$. $2$ is a proper divisor of $4,6,12,18,36,48,60$, and $72$, so none of those elements can be minimal. $9$ has no proper divisor in the set, however, so $9$ is minimal. Finally, $9\mid 27$, so $27$ is not minimal.

(c) Again, $24$ and $45$ are irrelevant, since they’re not in the partial order. This question is really asking whether the set $\{2,4,6,9,12,18,27,36,48,60,72\}$ contains any element that is divisible by all of the elements in the set. Clearly $72$ is the only possibility, and it isn’t divisible by $27$, so there is no such element, and this poset does not have a greatest element.

(d) It doesn’t have a least element, either, but not for the reason that you give; can you give a correct reason now, based on what I did for (c)?

(e) The set in question is $\{2,9\}$, not $\{3,5\}$, but what you’ve said indicates that you have the right idea: you want the common multiples of $2$ and $9$ that are in the partial order. Those are $18,36$, and $72$.

share|improve this answer
    
I am so sorry: I copied and pasted the wrong question from my text-book. –  Mack Nov 18 '12 at 18:48
    
@EMACK: I wondered if that was what had happened, since your choices were so consistent and so consistently different from the ones available in the problem that you stated. –  Brian M. Scott Nov 18 '12 at 18:51
add comment

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.