# Maximal Elements - Ordered Sets

Problem 1: Let $S$ be an ordered set with a unique maximal element $x$.

Again, I've worked some thoughts to these problems and would like to confirm their validity. I appreciate any feedback.

(1) Prove that if S is finite, then $x$ is the last element of $S$.

For $x$ to be a last element, it must strictly succeed every other element, but I am not sure how to do the proof - I thought of this in a calculus-based context of a local maximum.

(2) When S is infinite, is it true that $x$ is the last element of $S$?

I am wondering if I have to divide this into 3 cases where:

• The infinite set has a first element but no last element.
• The infinite set has a last element but no first element.
• The infinite set has neither a first nor a last element.

Problem 2: Let $S$ be a set with 5 elements.

(1) How many different linear orders are there on $S$?

I claimed that we would have 5! = 120 linear/total orders.

(2) Find the number of distinct partial orders on $S$ that have both first and last elements.

I claimed that we would have: (5 choose 2) * 3! = 60 of these partial orders.

-

Problem 1.

(1) You’re given a finite partial order with a unique maximal element $a$, and you’re asked to prove that this maximal element is actually the maximum: not only is there no element strictly greater than $a$, but $a$ is strictly greater than all of the other elements of $S$. To prove this, suppose that $b\in S$ and $b\not\le a$. Let $B=\{x\in S:b\le x\}$; clearly $b\in S$, so $S\ne\varnothing$. Every non-empty finite set in a partial order has a maximal element, so let $c$ be maximal element of $B$. Now show that $c$ must be a maximal element of $S$ different from $a$, contradicting the uniqueness of $a$ and thereby showing that no such $b$ can exist.

(2) Consider the partial order whose Hasse diagram is sketched below. Note that I’ve turned it sideways to fit better: larger is to the right, not up.

        x---x---x---x---x---x---x---x---x-- ...
/
/                            bigger ----->
a---b


Here $a$ is clearly the minimum element of the partial order, and $b$ is a maximal element. Are there any other maximal elements? Is $b$ maximUM?

Problem 2.

(1) This is fine, assuming that the elements of $S$ are distinguishable. If not, there is only one:

           x---x---x---x---x


(2) You have to work a bit harder for this one. First, note that every one of your $5!=120$ linear orders qualifies, so the answer should be larger than that. (Again I’m assuming, as I think is intended, that the five elements are distinguishable.) There are $5$ ways to choose the minimum, and once that’s chosen there are $4$ ways to choose the maximum, so the two ends can be fixed in $5\cdot4=20$ ways. Now you need to figure out what the three in the middle can look like. Then can be ordered linearly, in which case the whole thing is, and you’re looking at one of the $120$ linear orders. Or the order could look like this:

                  x
|
o
/ \
x   x
\ /
x


For this shape there are $3$ ways to choose the element at $o$, after which there are no further choices, so there are $20\cdot3=60$ orders of this type. Turning this upside down produces another $60$.

There are two more possible shapes; can you find them and count how many ways there are to produce each of them?

-
Is an ordered set one with a partial order or is a total order required? In your example under Problem 1 (2), b is not comparable with many elements-I agree it is maximal. – Ross Millikan Nov 14 '12 at 5:31
@Ross: The first question makes no sense unless partial orders are intended. Or better, it has no point. – Brian M. Scott Nov 14 '12 at 5:35