1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mauro ALLEGRANZA Feb 6 '14 at 11:57
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}

$\endgroup$
0
$\begingroup$

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'$.

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

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

$\endgroup$

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.