1
$\begingroup$

My textbook contains the following exercise:

Let $(A,\leq)$ be a partially ordered set. Prove that if each finite non-empty subset of $A$ has a greatest element, then $(A,\leq)$ is totally ordered.

I'm struggling to prove this.
I began by just considering some subset of $A$ containing two elements. I denote this subset of $A$ as $B_1$: $B_1 \subseteq A$. I denote the two elements in $B_1$ as $x_1$ and $x_2$: $B_1$={$x_1, x_2$}. Assuming the antecedent of the above conditional sentence, it's true that $x_1$ or $x_2$ is the $maxB_1$. Then $x_2 \ge x_1$ or $x_1 \ge x_2$. Now, suppose $x_1=x_2$. Then, it's clear that $B_1$ is totally ordered. Then, it remains to show that in the cases $x_1 \lt x_2$ and $x_2 \lt x_1$, $x_1$ and $x_2$ are $\le$-comparable. (Establishing this fact essentially establishes the rest of the proof, well, at least to my thinking.) It is at this point that I'm stuck.

$\endgroup$
1
$\begingroup$

HINT: Turn your argument around. Suppose that $A$ is not totally ordered. Then there are $x_1,x_2\in A$ such that $x_1\not\le x_2$ and $x_2\not\le x_1$. What can you say about the set $\{x_1,x_2\}$?

$\endgroup$
  • $\begingroup$ Wow . . .I feel very much like an imbecile. I still don't see it. $\endgroup$ – Jordan Miller Aug 18 '15 at 17:54
  • $\begingroup$ @Jordan: Does that two-element set have a greatest element? $\endgroup$ – Brian M. Scott Aug 18 '15 at 17:57
  • 1
    $\begingroup$ @Jordan: If $x_1$ were the largest element of the set, then by definition we’d have $x_2\le x_1$, which is not the case. Similarly, if $x_2$ were the largest element, we’d have $x_1\le x_2$, which is not the case, Thus, neither $x_1$ nor $x_2$ can be the largest element of the set, and since they’re its only elements, it has no largest element. Does that help? $\endgroup$ – Brian M. Scott Aug 18 '15 at 18:11
  • 1
    $\begingroup$ @Jordan: Yes, $\le$ refers to the specific partial order on the set $A$ mentioned in the notation $\langle A,\le\rangle$ presenting $A$ as a partially ordered set. $\endgroup$ – Brian M. Scott Aug 18 '15 at 18:21
  • 1
    $\begingroup$ @Jordan: That’s correct. Perhaps it would have been clearer had the partial order been defined as $\langle A,\preceq\rangle$, and the symbol $\preceq$ then been used throughout; you’d have been less inclined to suppose that it referred to some previously known order relation. $\endgroup$ – Brian M. Scott Aug 18 '15 at 18:24
1
$\begingroup$

The only difference between a partial order and a total order is that in a total order any two elements can be compared. But if every set of two elements has a maximum, by definition of maximum it means those two elements can be compared.

$\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.