1
$\begingroup$

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$!

Could anyone please help me on this? Thank you so much!

$\endgroup$
  • 2
    $\begingroup$ Your exercise is to prove about intersection but the proof is about union? $\endgroup$ – lEm Mar 15 '16 at 14:58
  • $\begingroup$ Thank you, should be ok now $\endgroup$ – Daniel Mak Mar 15 '16 at 15:01
  • $\begingroup$ 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'$$ $\endgroup$ – Crostul Mar 17 '16 at 10:51
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @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 $\endgroup$ – Darío G Mar 19 '16 at 8:33
  • 1
    $\begingroup$ @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$". $\endgroup$ – Darío G Mar 19 '16 at 10:40
  • 1
    $\begingroup$ @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] $\endgroup$ – Darío G Mar 20 '16 at 7:10
  • 1
    $\begingroup$ @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$ $\endgroup$ – Darío G Mar 20 '16 at 7:12
  • 1
    $\begingroup$ @DanielMak No problem! $\endgroup$ – Darío G Mar 20 '16 at 17:53
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Daniel Mak Mar 16 '16 at 14:46
  • 1
    $\begingroup$ @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$. $\endgroup$ – Darío G Mar 17 '16 at 10:38

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.