# Prove $A \cup A' = U$ and$A \cap A' = \emptyset$

Prove $A \cup A' = U$ and $A \cap A' = \emptyset$

$A \cup A' = U$

set union definition with negation on the second $A$.

$[x: x \in A \lor x \notin A]$

This means that x is in $A$ or x is not in $A$. I wrote that since this is an or statement we can choose one or the other, but apparently that isn't a good reason to demonstrate that $A \cup A' = U$ . So, how do I prove it without set union definition? I don't think substituting $A \cup A' = U$ as $U=U$ is a good idea. That's too easy, and if that's the case, then I know it's wrong.

$A \cap A' = \emptyset$

is really easy to prove.

Using set definition of $A \cap A'$

$[x: x \in A \land x \notin A ]$

which tells me that x is in A and x is not an A. This is a very absurd statement. That's why it's an empty set.

• The same "reasoning" applied to $[x: x \in A \land x \notin A]$ that "it's absurd" (bacuse it is simply: $x \in A \land \lnot x \in A$, and this can never be true) applies to $[x: x \in A \lor x \notin A]$ that "it's obvious" (bacuse it is simply: $x \in A \lor \lnot x \in A$, and this in turn is always true). In the first case, never gives you that $\forall x$, $x$ does not satisfy the condition,and this means that the condition "define" the empty set. In the second case, the always gives you that $\forall x$, $x$ does satisfy the condition,and this "define" the universe. – Mauro ALLEGRANZA Feb 6 '14 at 11:57

Define $A' = \left\{ x : x \in U \text{ and } x \not \in A \right\}$. If $x \in A \cup A'$, then $x \in A$ or $x \in A'$, and either way $x \in U$, so $A \cup A' \subseteq U$. If $x \in U$, then either $x \in A$ or $x \not \in A$ and so $x \in A \cup A'$, so that $U \subseteq A \cup A'$. Then, $U = A \cup A'$.

The second statement is only vacuously true where $A = \emptyset$, however you could also prove it via contradiction.

Here is a calculational way to do these two proofs: expand definitions, simplify, and see where that leads you.

I'm assuming that $\;U\;$ is the universe we're working in, which contains every element, and that $\;{}'\;$ is set complement within $\;U\;$.

For every $\;x\;$ we have \begin{align} & x \in A \cup A' \\ \equiv & \qquad \text{"definition of $\;\cup\;$"} \\ & x \in A \lor x \in A' \\ \equiv & \qquad \text{"definition of $\;{}'\;$"} \\ & x \in A \lor \lnot (x \in A) \\ \equiv & \qquad \text{"logic: excluded middle"} \\ & \text{true} \\ \equiv & \qquad \text{"$\;U\;$ is our universe"} \\ & x \in U \\ \end{align} Therefore, by set extensionality, $\;A \cup A' = U\;$.

In a very similar way we can prove $\;A \cap A' = \emptyset\;$: for every $\;x\;$ \begin{align} & x \in A \cap A' \\ \equiv & \qquad \text{"definition of $\;\cap\;$"} \\ & x \in A \land x \in A' \\ \equiv & \qquad \text{"definition of $\;{}'\;$"} \\ & x \in A \land \lnot (x \in A) \\ \equiv & \qquad \text{"logic: contradiction"} \\ & \text{false} \\ \equiv & \qquad \text{"definition of $\;\emptyset\;$"} \\ & x \in \emptyset \\ \end{align}

You must use set union definition. For every $x \in U$ we have that either $x \in A$ or $x \notin A$, that is, either $x \in A$ or $x \in A'$. Therefore $$x \in U \Rightarrow x \in A \cup A' \ .$$ The other way of inclusion is trivial since $A \subset U, \ A' \subset U$. Conclude that $$U \subset A' \cup A \subset U$$ and hence $U = A \cup A'$.

• Ok, so I keep the set union definition. At least I got that part right. ...I guess my explanation wasn't good enough. – usukidoll Feb 6 '14 at 11:33

### a) show that $A \cup A' \subseteq U$

$$\forall_{ABC} A \subseteq C \land B \subseteq C \Rightarrow A \cup B \subseteq C$$ trivial one. Therefore in particular $$A \subseteq U \land A' \subseteq U \Rightarrow A \cup A' \subseteq U$$

### b) show that $U \subseteq A \cup A'$

$$\forall_x \; x \in A \lor x \notin A$$ $$_{(\text{this is p \lor \neg p tautology})}$$ by definition $x \notin A \iff x \in A'$ therefore $$\forall_x \; x \in A \lor x \in A'$$ so now we just $$x \in U \Rightarrow x \in A \lor x \in A' \Rightarrow x \in A \cup A'$$

### conclusion

a) and b) implicate that $A \cup A' = U$

### now with $A \cap A'= \emptyset$

we will use the fact that $$A=B \Rightarrow A'=B'$$ of course $$U'=\emptyset$$ and $$(A \cup A')'=A' \cap A = A \cap A'$$ if the first equality is not obvious to you then I'll show that $$\forall_{AB} (A \cup B)'=A' \cap B'$$ here we go $$x \in (A \cup B)' \iff x \notin A \cup B \iff x \notin A \land x \notin B \iff$$$$\iff x \in A' \land x \in B' \iff x \in A' \cap B'$$

 step $x \notin A \cup B \iff x \notin A \land x \notin B$ is taken from negating on both sides $$x \in A \cup B \iff x \in A \land x \in B$$  $$\neg (x \in A \cup B) \iff \neg(x \in A \land x \in B)$$ $$\neg (x \in A \cup B) \iff \neg(x \in A) \lor \neg(x \in B)$$ $$x \notin A \cup B \iff x \notin A \land x \notin B$$