2

$U$ can be any set.

For the existence element of this proof, I have $A = \varnothing$

But it's for the uniqueness element of this proof where I am having trouble. So far I have:

$\forall(C\in\mathscr{P}(U))(\forall(B\in\mathscr{P}(U))(C\cup B=B)\rightarrow C\in\mathscr{P}(U) = A\in\mathscr{P}(U))$

Assume $C\in\mathscr{P}(U)$ is arbitrary and assume $\forall(B\in\mathscr{P}(U))(C\cup B=B)$ then:

What I have left to prove is: $C\in\mathscr{P}(U) = A\in\mathscr{P}(U) $

which is where I am having trouble. I can say that $C = \varnothing$ which would then equal $A$ but it is not certain that $C = \varnothing$.

Michael Hardy
  • 1
Bavneet
  • 121
  • 6
  • I feel like this question was asked before. Finding it would be a real hassle though. – Asaf Karagila May 27 '13 at 21:14
  • @BavneetJhutty: To simplify things (at the very least notationally), note that $C \in \mathscr{P}(U)$ is equivalent to $C \subseteq U$, so your proof could just say, "$A$, $B$, and $C$ range over subsets of some universe $U$". Also note that $A \cup B = B$ is equivalent to $A \subseteq B$. – MarnixKlooster ReinstateMonica May 27 '13 at 21:22

4 Answers4

5

For uniqueness: The claim has to hold in particular for $B = \varnothing$. So if $A \neq \varnothing$, what would happen?

kahen
  • 15,760
  • Okay, so for A∪B=B, it has to hold when B=$\varnothing$, i.e. when A∪$\varnothing$=$\varnothing$, therefore A has to equal $\varnothing$. And therefore, C as well has to equal $\varnothing$ in the case of C∪B=B. Is this correct? – Bavneet May 27 '13 at 21:39
5

For the uniqueness if $A$ and $A'$ are two sets verifying the hypothesis then we have $$A\cup A'=A'=A'\cup A=A$$ so $A=A'$ and obviously this set is $\emptyset$

1

Here is an attempt at a slightly more constructive answer, where $\;\varnothing\;$ is not pulled like a rabbit out of a magician's hat.

First a point of notation: noticing that $\;X\in\mathscr{P}(U)\;$ is equivalent to $\;X \subseteq U\;$, I will implicitly assume in this answer that $\;A\;$ and $\;B\;$ range over subsets of $\;U\;$. This gets rid of a lot of occurrences of $\;\in\mathscr{P}(U)\;$.

Using this notation we are to prove that there is a unique $\;A\;$ such that $$ (0) \;\;\; \langle \forall B :: A \cup B = B \rangle $$ Apart from simplifying this to $$ (1) \;\;\; \langle \forall B :: A \subseteq B \rangle $$ using set theory, the only way to make progress seems to be to choose a specific $\;B\;$. And there three values of $\;B\;$ immediately suggest themselves: $\;\varnothing\;$, $\;A\;$, or $\;U\;$. Since the last two only lead to tautologies, we choose $\;\varnothing\;$. (There are also combinations of these, like $\;U \setminus A\;$ which also turns out to work but in a more complex way. However, the simplest option already works, as we will see.)

Therefore we calculate for any $\;A\;$ \begin{align} & \langle \forall B :: A \subseteq B \rangle \\ \Rightarrow & \;\;\;\;\;\text{"choose $\;B := \varnothing\;$ -- as discussed above"} \\ & A \subseteq \varnothing \\ \equiv & \;\;\;\;\;\text{"set theory: simplify using $\;\varnothing \subseteq X\;$ for any $\;X\;$"} \\ & A = \varnothing \\ \end{align} And the same law that was used in the last step above can now immediately be used for the other direction: assuming $\;A = \varnothing\;$ we directly prove $(1)$ by \begin{align} & \langle \forall B :: A \subseteq B \rangle \\ \equiv & \;\;\;\;\;\text{"assumption"} \\ & \langle \forall B :: \varnothing \subseteq B \rangle \\ \equiv & \;\;\;\;\;\text{"set theory: $\;\varnothing \subseteq X\;$ for any $\;X\;$"} \\ & \textrm{true} \\ \end{align} Putting these together we see that $(0)$ is equivalent to $$ A = \varnothing $$ Therefore the unique $\;A\;$ satisfying $(0)$ is $\;\varnothing\;$.

MarnixKlooster ReinstateMonica
  • 5,576
0

If $U$ is empty then this is trivial. If $U$ is not empty then suppose some such $A\ne \varnothing$ exists. Let $x\in A$. There is at least one subset of $U$ not containing $x$, since $\varnothing$ is such a set. For any subset $B$ of $U$ such that $x\not\in B$, we have $A\cup B\ne B$.

Michael Hardy
  • 1