[Math] Answering Questions For A Poset.

discrete mathematicselementary-set-theoryrelations

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.

Best Answer

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.
Related Question