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:
I understand the existence proof, but how could you know you should substitute $U$ for $A$? Is it just by practice and experience?
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$!
Could anyone please help me on this? Thank you so much!