0
$\begingroup$

The title refers to an exercise in Velleman's "How to Prove It" that I'm trying to work through for self-study. My proof doesn't feel right, so am hoping that the wisdom of the group can help me correct my mistakes. Specifically, I'm suspect of the proof because:

1) I haven't used all the givens;

2) I'm assuming a least upper bound exists in the left direction, and;

3) I only use the fact that the least upper bound is an upper-bound.

Suppose $A$ is a set, $\mathcal{F} \subseteq \mathcal{P}(A)$, and $\mathcal{F} \neq \emptyset$. Then the least upper bound of $\mathcal{F}$ (in the subset partial order) is $\cup \mathcal{F}$.

($\rightarrow$) Suppose $F'$ is the least upper bound of $\mathcal{F}$. Then by definition $F' \in \mathcal{F}$. Next, let $f \in F'$. Then clearly $f \in \cup\mathcal{F}$. So $F' \subseteq \cup F$.

($\leftarrow$) Suppose $\mathcal{F}$ has a least upper bound $F'$, and let $x \in \cup \mathcal{F}$. It follows that $\exists A \in \mathcal{F}(x \in A)$. But since $F'$ is an upper bound, then $A \subseteq F'$. So $x \in F'$ and $\cup \mathcal{F} \subseteq F'$.

Thanks for any and all comments!

$\endgroup$
  • $\begingroup$ We don't necessarily have $F' \in \mathcal F$ in your $(\to)$ paragraph. For instance, take $A = \{a, b\}$ with $\mathcal F = \{\{a\}, \{b\}\}$. In that case, $A$ is the only upper bound for $\mathcal F$, and we don't have $A \in \mathcal F$. $\endgroup$ – Arthur Nov 10 '15 at 19:48
1
$\begingroup$

For all $F \in \mathcal{F}$, we have that $F \subseteq \cup \mathcal{F}$, or $F \le \cup \mathcal{F}$ (to use the order notation). This means that $\cup \mathcal{F}$ is an upper bound of $\mathcal{F}$. This is one part of the definition.

Suppose that $G$ is another upper bound for $\mathcal{F}$. Then for each $F \in \mathcal{F}$ we have that $F \le G$, or otherwise put $F \subseteq G$. So the union of all such $F$, $\cup \mathcal{F} \subseteq G$. So $\cup \mathcal{F}$ is less than or equal to any upper bound for $\mathcal{F}$, so the latter is the least upper bound, by definition.

$\endgroup$
  • $\begingroup$ Very nice. Thanks so much for the help! $\endgroup$ – Scentless Apprentice Nov 10 '15 at 21:02
  • $\begingroup$ Happy to help out $\endgroup$ – Henno Brandsma Nov 10 '15 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.