## Relations

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:

- If \((x, x) \not\in C\), then \((x, x) \not\in D\)
- Since, for any given \(x, y\) where \(x \neq y\), either \(xCy\) or \(yCx\) must be true, the same must be true for \(D\) (if \(xCy\), then \(yDx\), and vice versa).
- Transitivity states that if \(xCy\) and \(yCz\), then \(xCz\). Thus, if \(yDx\) and \(zDy\), then \(zDx\).

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.