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