3
$\begingroup$

I am presently attempting Exercise 2 in Kaplansky, Set Theory and Metric Spaces

Exercise 2: Let $L$ be a partially ordered set in which every subset has a top and bottom element. Prove that $L$ is a finite chain.

Proof: Denote a subset of $L$ by $S$. If $S$ has a top and bottom element, then $\sup S$ and $\inf S$ exist and are elements of $S$. Denote them $a$ and $A$ respectively. Since $a,A \in S$ then $S$ is finite. This means that all the elements in $S$ can be ordered from smallest to largest, thus we have: $S= \{ a, ..., A \}$. Based upon this ordering, given any two elements, $b,c \in S$ one may determine that $b \le c$ or $c \le b$. Since all the subsets of L are a chain, this implies that L must also be a chain.

My Question: I am uncertain on whether the step in bold is valid. I believe it is based upon the transitivity condition in the definition for a partially ordered set, though I would appreciate some feedback on the matter.

$\endgroup$
  • $\begingroup$ I don't see a reason given why $S$ is finite. $\endgroup$ – Jonas Meyer Jun 6 '13 at 5:19
  • $\begingroup$ @user14111 Since the proof is that L is a chain, doesn't the upper and lower bounds of the empty set consist of the elements of L and thus would also have a top and bottom element? $\endgroup$ – GovEcon Jun 6 '13 at 5:23
  • 1
    $\begingroup$ @Jordan: I don't understand your comment, but the answer is no. A top element of a subset would have to be an element of the subset, by the usual conventions of language. The empty set has no elements, so it cannot have a top or bottom element. $\endgroup$ – Jonas Meyer Jun 6 '13 at 5:26
5
$\begingroup$

Given any two elements $x,y\in L,$ we know that $\{x,y\}$ has a top element and a bottom element. This shows that comparability holds on $L$, so since $L$ is a poset, then $L$ is a linearly ordered set.

Now, suppose that $L$ is not finite. Let $x_0$ be the top element of $L$, and for any nonnegative integer $n,$ let $x_{n+1}$ be the top element of $L\setminus\{x_0,...,x_n\}.$ Show that $\{x_n:n\text{ a nonnegative integer}\}$ is a subset of $L$ without a bottom element--the desired contradiction (you'll need the assumption that $L$ isn't finite).

P.S. (Added later): The actual claim should read "...every non-empty subset has...," for obvious reasons. In fact, we can adjust the claim as follows:

Let $L$ be a partially ordered set. Then $L$ is a finite chain if and only if every non-empty subset of $L$ has a top element and a bottom element.

The forward direction can be proved by induction, though this may vary in difficulty, depending on which definition of "finite" is being used.

$\endgroup$
1
$\begingroup$

No, it is not valid. There are partially ordered sets, finite or infinite, that are not chains. (E.g., consider a power set of a set with at least $2$ elements, ordered by inclusion.) You have to use the hypothesis to show that $L$ is a chain. I recommend contraposition. You can show that if there are $2$ incomparable elements, then there exists a nonempty subset without a top and bottom.

You also gave no valid reason why $L$ is finite.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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