# Naive Set Theory: Relations

## Bounds

For the following sections, let $<$ be a total order on a set $A$, and let $A'$ be a subset of $A$.

### Extrema

An element $b \in A'$ is the maximum of $A'$ if $b \geq a$ for all $a \in A'$. The maximum is also known as the largest element or the greatest element. Conversely, $b$ is the minimum of $A'$ if $b \leq a$ for all $a \in A'$. The minimum is also known as the smallest element or least element.

### Bounds

If there is an element $b \in A$ such that $b \geq a$ for all $a \in A'$, then $b$ is an upper bound for $A'$, and $A'$ is said to be bounded above. Likewise, if there is an element $b \in A$ such that $b \leq a$ for all $a \in A'$, then $b$ is a lower bound for $A'$, and $A'$ is said to be bounded below.

### Infima and Suprema

Let $B$ be the set of all upper bounds for $A'$. If $B$ has a smallest element $b$, then $b$ is the least upper bound, also called the supremum, of $A'$. Conversely, let $B$ be the set of all lower bounds for $A'$. If $B$ has a smallest element $b$, then $b$ is the greatest lower bound, also called the infimum, of $A'$.

### Least Upper Bound Property

$A$ has the least upper bound property if every nonempty subset $A' \subseteq A$ that is bounded above has a least upper bound. Conversely, $A'$ has the greatest lower bound property if every nonempty subset $A' \subseteq A$ that is bounded below has a greatest lower bound.

## Problems

1. Let $A = \{a,b,c,d,e\}$ where $a<b<c<d<e$.

1. Find the supremum and infimum of $A$.

2. Let $A_0 = \{b,c,d\}$. Find the set of all upper and lower bounds for $A_0$, as well as its supremum and infimum.

3. Let $A_1 = \{ c \}$. Find the set of all upper and lower bounds for $A_1$, as well as its supremum and infimum.

4. Let $A_2 = \{ a, b, d \}$. Find the set of all upper and lower bounds for $A_2$, as well as its supremum and infimum.

1. $\text{sup}(A) = e$, $\text{inf}(A) = a$.

2. The set of all upper bounds for $A_0$ is $\{d, e\}$, and $\text{sup}(A_0)=d$. The set of all lower bounds for $A_0$ is $\{a,b\}$, and $\text{inf}(A_0)=b$.

3. The set of all upper bounds for $A_1$ is $\{c, d, e\}$, and $\text{sup}(A_1)=c$. The set of all lower bounds for $A_1$ is $\{a,b,c\}$, and $\text{inf}(A_1)=c$.

4. The set of all upper bounds for $A_2$ is $\{d, e\}$, and $\text{sup}(A_2)=d$. The set of all lower bounds for $A_2$ is $\{a\}$, and $\text{inf}(A_2)=a$.

2. LUBP $\Longleftrightarrow$ GLBP: Prove that a set has the least upper bound property if and only if it has the greatest lower bound property.

$\implies$: Let $A$ be a set with the least upper bound property, and let $A_0 \subseteq A$ such that $A_0$ has a lower bound. Let $B$ be the set of all lower bounds of $A_0$. Pick an element $a \in A_0$. By definition of lower bound, $b \leq a$ for all $b \in B$. Therefore $B$ has an upper bound, namely $a$. Let $C$ denote the set of all upper bounds for $B$. Because $A$ has the least upper bound property, $C$ has a smallest element, call it $b_0$. Then $b_0 \leq c$ for all $c \in C$. However, because every element in $A_0$ is an upper bound for $B$, it follows that $A \subseteq C$.  Therefore $b_0 \leq a$ for all $a \in A_0$. This means that $b_0$ is a lower bound for $A_0$, which means that $b_0 \in B$. Because $b_0 \geq b$ for all $b \in B$, $b_0$ is therefore the maximum element of $B$. Therefore $b_0$ is the greatest lower bound for $A_0$.

$\impliedby$: Let $A$ be a set with the greatest lower bound property, and let $A_0 \subseteq A$ such that $A_0$ has an upper bound. Let $B$ be the set of all upper bounds of $A_0$. Pick an element $a \in A_0$. By definition of upper bound, $b \geq a$ for all $b \in B$. Therefore $B$ has a lower bound, namely $a$. Let $C$ denote the set of all lower bounds for $B$. Because $A$ has the greatest lower bound property, $C$ has a largest element, call it $b_0$. Then $b_0 \geq c$ for all $c \in C$. However, because every element in $A_0$ is a lower bound for $B$, it follows that $A \subseteq C$.  Therefore $b_0 \geq a$ for all $a \in A_0$. This means that $b_0$ is an upper bound for $A_0$, which means that $b_0 \in B$. Because $b_0 \leq b$ for all $b \in B$, $b_0$ is therefore the smallest element of $B$. Therefore $b_0$ is the least upper bound for $A_0$.