Section 3.2: Problem 3 Solution
Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.
James R. Munkres
Let be a model of (or equivalently a model of ). For and in define the equivalence relation: Let be the equivalence class to which belongs. Order equivalence classes by Show that this is a well-defined ordering on the set of equivalence classes.
First, we argue that is an equivalence relation. The reflectiveness and symmetry of the relation follows immediately from the definition. Regarding the transitivity, we can use the axioms, in particular, S2, to see that if then iff , and iff , from which the transitivity of follows.
Now, we show that is well-defined. Suppose that . We need to show that if then , and if , then . If , then ( is an equivalence relation), and either or , in which case , or , in which case if we assume or , then for some (by S2), contradicting the assumption that . In either case, and , implying . Similarly, we consider the case to show .
Finally, we ensure that the ordering properties hold for .
- Trichotomy. For every and , either ( ) or , hence, , and either ( ) or ( ).
- Antisymmetry. For every and , if and ( ) then not ( ). Alternatively, or ( ) iff ( ) or (hence, ) and ( ).
- Transitivity. For every , and , if and ( ) and and ( ), then and ( ). Here, we have , as otherwise, , and , implying for some , , and (by L1).