Section 2.2: Problem 2 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
Show that no one of the following sentences is logically implied by the other two. (This is done by giving a structure in which the sentence in question is false, while the other two are true.)
(a) . Recall that by our convention is .
(a) describes transitivity (it requires exactly in those cases when and ). (b) describes antisymmetry (it requires exactly in those cases when and ). (c) describes the case when if for each element there is a “greater” one ( ) then there is a maximal element ( ).
We consider the minimal language required in our case, , and structures such that . We still need to specify the relation on . There are 16 possibilities, 10 being essentially different (there are no automorphisms between any two of them).
Therefore, we already have two examples needed: the relation (which can be also described simply as ) is transitive antisymmetric, and for each there is such that , but there is no maximal element; and the relation (which can be also described as the complete one when for every and , ) is transitive with a maximal element (in fact, two maximal elements) but not antisymmetric ( and but ).
We still need an example of the structure and relation on such that is not transitive, but it is antisymmetric and either not every element has a greater element or there is a maximal element. For this, we obviously need at least three elements. Indeed, if is not transitive, then for some , and , and but not , therefore, . But if , then is not antisymmetric. But the relation on already satisfies (b) and (c) but not (a), as it is not transitive ( and but not ), but it is antisymmetric (there are no different and such that and , in fact, there are no such and at all) and also not for every there is such that (there is no for ), i.e. and .