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).
 
