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

(b)
.

(c)
.

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

(a) | (b) | (c) | |

+ | + | + | |

+ | + | + | |

+ | + | + | |

+ | + | + | |

+ | + | + | |

+ | + | ||

+ | |||

+ | + | + | |

+ | + |

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
.