Munkres - Relations

Adar Kahiri
June 2020

Problem 14: If \(C\) is a relation on set \(A\), define a new relation \(D\) on \(A\) by letting \((b, a) \in D\) if \((a, b) \in C\).


Starting with (a), If \(D = C\), then, since \((b, a) \in D \iff (a, b) \in C\), \((b, a) \in C \iff (a, b) \in C\). This is the definition of symmetry. Conversely, if \(C\) is symmetric, then, \((a, b) \in C \implies (b, a) \in D\), and, by symmetry, \((b, a) \in C \implies (a, b) \in D\), meaning \(D=C\).


For (b), all we need to do is ensure that \(D\) satisfies the conditions of an order relation:


For (c), consider an ordered set \(A\) and a subset \(A_0\) that is bounded above. Let the set of all of its upper bounds be \(S\). \(S\) is clearly bounded below by \(A_0\). The greatest lower bound property ensures that there is an element \(b \in A_0\) such that \(b \leq x \ \forall \ x \in S\). Furthermore, the greatest lower bound property ensures that \(b\) is the largest element in \(A_0\) (and subsequently, if in \(S\), the smallest element in \(S\)). Since \(x \leq b \ \forall \ x \in A_0\), \(b\) is an upper bound of \(A_0\). Since it is, by definition, in \(S\), and the smallest element in \(S\), \(S\) has a least upper bound.