# Proving uniqueness in naive set theory

I am doing the following exercise from Velleman's How To Prove It:

Prove that there is a unique $A \in \mathcal P (U)$ such that for every $B\in \mathcal P (U)$, $A \cup B=A$. ($\mathcal P (U)$ being the powerset of U)

One solution I found is as follows:

To prove the existence, try $A=U$. For any $B\in \mathcal P (U)$, $B\subseteq U$ and so $U\cup B=U$.

To prove the uniqueness, let say there is another set $C\in \mathcal P (U)$ s.t. $\forall B \in \mathcal P (U)(C \cup B=C)$. We can put $B=U \setminus C$ in this equation to get $C \cup (U \setminus C) =C$, therefore $U=C$ and hence $C=U=A$.

Two confusions I have:

1. I understand the existence proof, but how could you know you should substitute $U$ for $A$? Is it just by practice and experience?

2. I do not understand what's going on in the uniqueness proof at all. In the preceding pages the following existence and uniqueness form have been mentioned:

a. $\exists x(Fx \land \forall y(Fy \to y=x)$

b. $\exists x \forall y(Fy$↔$y=x)$

c. $\exists x Fx \land \forall y \forall z ((Fy \land Fz) \to y=z)$

But none of these seem to fit into what he is trying to do here. I don't understand where is the $C\in \mathcal P (U)$ from; it seems that he did an existential instantiation but it is not apparent to me where the existential comes from.

More importantly, why substitute $B$ (instead of $A$) for $B=U \setminus C$? And wouldn't $B=U \setminus C$ be contradictory to the conclusion? Since if we substitute $B$ with this from $(C \cup B=C)$, it becomes $x\in C \lor (x \in U \land \sim x \in C)=x \in C$. If we try to prove this by cases, the second case i.e. second disjunction would yield the negated form of the conclusion: $\sim x \in C$!

• Your exercise is to prove about intersection but the proof is about union? – lEm Mar 15 '16 at 14:58
• Thank you, should be ok now – Daniel Mak Mar 15 '16 at 15:01
• Well, there is a simpler uniqueness argument which uses commutativity: if you have two such sets, say $A$ and $A'$, then $$A= A \cup A' = A' \cup A = A'$$ – Crostul Mar 17 '16 at 10:51

To answer the first question:If you think about the property that such $A\in \mathcal{P}$ should satisfy, it is:

**$(\star)$ For each $B\in\mathcal{P}(U)$, $A\cup B=A$. **

So, such $A$ is a subset of $U$, and since $A\cup B=A$ iff $B\subseteq A$, we have that such $A$ is actually the largest subset of $U$. This gives you some intuition of why $A$ should be equal to $U$.

For the second question: I don't see clearly why the intersections become unions in your argument, so I take the opportunity to change it a little bit:

Goal: Prove that if $C$ satisfy the required condition, then $C=U$.

First of all, we know that $C\in \mathcal{P}(U)$, so $C\subseteq U$. On the other hand, if we put $B=U\setminus C$, then by the condition $(\star)$ we have

$$C=B\cup C=(U\setminus C) \cup C$$ and so, $U\setminus C\subseteq C$. This is only possible if $U\setminus C=\emptyset$, or equivalent, if $U\subseteq C$.

This shows that $C=U$, by double contenence.

• @DanielMak For the first question, note that for any sets $A,B$, it is true that $B\subseteq A\cup B$. So $A\cup B=A$ immediately leads to $B\subseteq A$. On the other hand, if $A$ satisfies the required property, then $A$ is a subset of $U$ and for all $B\subseteq U$ we will also have (by the previous part) that $B\subseteq A$. This only gives you the intuition that the required set will be $A=U$, but you will have to prove that $A=U$ indeed satisfies the required property (I did not do it, but it is easy). What I did from that point to the end was prove uniqueness – Darío G Mar 19 '16 at 8:33
• @DanielMak The most important part of the sentence you were quoting is the part that you omitted. The desired property is: "$X\in \mathcal{P}(U)$ and for all $B\in \mathcal{P}(U)$, $X\cup B=X$". – Darío G Mar 19 '16 at 10:40
• @DanielMak First, note that for any sets $X,Y$ we have $X\subseteq X\cup Y$. (Can you show why?). That explains why $U\setminus C\subseteq (U\setminus C)\cup C$, and the last is equal to $C$ by the hypothesis. [$C$ satisfies the desired property] – Darío G Mar 20 '16 at 7:10
• @DanielMak Now, note that $U\setminus C=\emptyset \Leftrightarrow \neg \exists x(x\in U \wedge x\not\in C)$ and this is equivalent to $\forall x(x\in C\rightarrow x\in U)\Leftrightarrow C\subseteq U$ – Darío G Mar 20 '16 at 7:12
• @DanielMak No problem! – Darío G Mar 20 '16 at 17:53

To answer the first question:If you think about the property that such $A\in \mathcal{P}$ should satisfy, it is:

**$(\star)$ For each $B\in\mathcal{P}(U)$, $A\cap B=B$. **

So, such $A$ is a subset of $U$, and since $A\cap B=B$ iff $B\subseteq A$, we have that such $A$ is actually the largest subset of $U$. This gives you some intuition of why $A$ should be equal to $U$.

For the second question: I don't see clearly why the intersections become unions in your argument, so I take the opportunity to change it a little bit:

Goal: Prove that if $C$ satisfy the required condition, then $C=U$.

First of all, we know that $C\in \mathcal{P}(U)$, so $C\subseteq U$. On the other hand, if we put $B=U\setminus C$, then by the condition $(\star)$ we have

$$U\setminus C=B=B\cap C=(U\setminus C) \cap C=\emptyset$$ and so, $U\subseteq C$ (because we knew already that $C\subseteq U$).

This shows that $C=U$, by double contenence.

• I am terribly sorry about this; I made a typo when I first typed this question up so that the conclusion I need to reach is actually supposed to be A∪B=A instead of A∩B=B. So sorry about this – Daniel Mak Mar 16 '16 at 14:46
• @DanielMak If you understood the argument above, I am sure that you can reconstruct the proof that you need. Note that $A\cup B=A$ if and only if $B\subseteq A$. – Darío G Mar 17 '16 at 10:38