Adar Kahiri

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