Exercise 3.1.9
Let $A$, $B$, $X$ be sets such that $A \cup B = X$ and $A \cap B = \emptyset$. Show that $A = X \setminus B$ and $B = X \setminus A$.
Show that $A = X \setminus B$
Let's start by writing down the meaning of $A \cup B = X$,
$$x \in X \iff (x \in A) \lor (x \in B)$$
and also the meaning of $A \cap B = \emptyset$,
$$\neg \exists x [(x \in A ) \land (x \in B)]$$
This is saying that there is no $x$ that is in both $A$ and $B$. We can write this as two separate statements,
$$x \in A \implies x \not \in B$$
$$x \in B \implies x \not \in A$$
Now, let's consider $A$. From $x \in X \iff (x \in A) \lor (x \in B)$, we have
$$x \in A \implies x \in X$$
And we already have
$$x \in A \implies x \not \in B$$
These two statements are both be true, so we can write them as
$$x \in A \implies (a \in X) \land (x \not \in B)$$
This gives us $A \subseteq X \setminus B$.
We need to show $X \setminus B \subseteq A$. Let's consider $X \setminus B$,
$$(x \in X) \land (x \not \in B)$$
Using $x \in X \iff (x \in A) \lor (x \in B)$, we have two cases, at least one of which is true,
- $x \in X \implies x \in A$
- $x \in X \implies x \in B$
The first case gives us
$$\begin{align}(x \in X) \land (x \not \in B) &\implies (x \in A) \land (x \not \in B) \\ \\ &\implies (x \in A) \end{align}$$
which confirms $X \setminus B \subseteq A$.
The second case gives us
$$(x \in X) \land (x \not \in B) \implies (x \in B) \land (x \not \in B)$$
which is a contradiction, meaning only the first case is true.
So having shown both $A \subseteq X \setminus B$, and $X \setminus B \subseteq A$, we can conclude $A = X \setminus B$. $\square$
Show that $B = X \setminus A$
We could prove this using the same logic as above, or we could simply use symmetry to argue that interchanging the variables $A$ and $B$ doesn't change the given information and constraints (because union and intersection are commutative), but does lead the desired conclusion. $\square$
No comments:
Post a Comment