Prove that a partially ordered set is totally ordered if, and only if, it is a chain.
Suppose is a partially ordered set with respect to a relation . By definition of total order, is totally ordered if, and only if, any two elements of are comparable. By definition of chain, this is true if, and only if, is a chain.
Suppose that is a totally ordered set. Use mathematical induction to prove that for any integer , every subset of with elements has both a least element and a greatest element.
Proof (by mathematical induction): Let be a set that is totally ordered with respect to a relation , and let the property be the sentence "Every subset of with elements has both a least element and a greatest element."
Show that is true:
If , then is true by default. So assume that has at least one element, and suppose is a subset of with one element. Because is reflexive, So, by definition of least element and greatest element, is both a least element and a greatest element of , and thus the property is true for .
Show that for every integer , if is true, then is true:
Inductive Hypothesis: Let be any integer with , and suppose that any subset of with elements has both a least element and a greatest element.
We must show that any subset of with elements has both a least element and a greatest element. If has fewer than elements, then the statement is true by default. So assume that has at least elements and that is a subset of with elements. By inductive hypothesis, has both a least element and a greatest element . Now because is totally ordered, and are comparable. If , then, by transitivity of is the least element of ; otherwise, remains the least element of . And if , then, by transitivity of is the greatest element of ; otherwise, remains the greatest element of . Thus has both a greatest element and a least element [as was to be shown].