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

(a) Prove that \(C\) is symmetric if and only if \(C = D\) (b) Show that if \(C\) is an order relation, then \(D\) is an order relation. (c) Prove that if an ordered set \(A\) has the greatest lower bound (GLB) property, then it has the least upper bound (LUB) property.

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.