Proving De-Morgan laws for sets

2k Views Asked by At

Let $A$ and $B$ be subsets of $\mathbb R$.

Prove that $(A \cap B) ' = A' \cup B' $

Let $ x \in (A \cap B) '$. So $ x \notin (A \cap B) $. So $x \in A-B$ or $x \in B-A$. So $x \in A'$ or $x \in B'$. So $x \in A' \cup B' $.

Let $x \in A' \cup B'$.

Case 1 : $x \in A'$. So $x \notin A$ so $x \in B-A$ Case 2 : similarly $x \in A-B$

So $x \in (A-B) \cup (B-A)$ and so $x\notin A \cap B$

Is this correct ?

1

There are 1 best solutions below

7
On BEST ANSWER

There's a problem with your proof. We cannot assume from $x \notin (A\cap B)'$ that either $x \in A-B \lor x\in B-A$, because $x$ may not be in either $A$ nor $B$. This cannot be the case if $x \in A-B$ or $x \in B-A$, because this implies $x$ is in one of A or B, and we don't know that.

Consider, e.g., $x \notin A \land x \notin B$. Then $x \in (A\cap B)',$ but $x \notin A-B,$ nor is $x \in B-A$.

In fact, $A\triangle B = A-B \lor B-A$, is the symmetric difference of A, B, which can also be defined, $(A\cup B)\cap (A\cap B)'$.

Here I use element chasing, and DeMorgan's Law in propositional logic, to prove (one of) DeMorgan's laws for sets. Note that set union correlates with the inclusive form of or.

$$\begin{align} x\in (A\cap B)' &\iff x \notin (A\cap B)\\ \\ & \iff \lnot (x \in (A\cap B)) \\ \\ & \iff \lnot (x \in A \land x\in B) \\ \\ &\iff \lnot(x \in A) \lor \lnot(x \in B)\\ \\ & \iff x \in A' \lor x\in B'\\ \\ & \iff x\in A'\cup B'\end{align}$$