Question

Prove that A - (A - B) : A intersectionB

Answer 1

Answer on Question #16803 – Math – Discrete Mathematics

Question

Prove that

$$A \backslash (A \backslash B) = A \cap B$$

Solution

It is known that

$$A \backslash B = A \cap B',$$

where $B' = \{x \mid x \notin B\}$.

$$B \cap B' = \emptyset,$$ $$B'' = (B')' = B$$ $$(C \cap D)' = C' \cup D' \text{ (De Morgan's Law)}$$ $$C \cap (D \cup E) = (C \cap D) \cup (C \cap E) \text{ (Distributive Law)}$$ $$\emptyset \cup C = C$$

Consider

$$(A \backslash B)' = (A \cap B')' = A' \cup B'' = A' \cup B$$

Method 1

$$\begin{aligned} A \backslash (A \backslash B) &= |(1)| = A \cap (A \backslash B)' = |(1)| = A \cap (A \cap B')' = |(4)| = A \cap (A' \cup B'') = |(5)| = \\ &= (A \cap A') \cup (A \cap B'') = |(2)| = \emptyset \cup (A \cap B'') = |(3)| = \emptyset \cup (A \cap B) = |(6)| = \\ &= A \cap B. \end{aligned}$$

All transformations are equivalent due to correctness of laws (1) to (6).

This proves that $A \backslash (A \backslash B) = A \cap B$.

Method 2

If $x \in A \backslash (A \backslash B)$, then it means that

$$(x \in A)$$

and

$$(x \notin A \backslash B).$$

If (9) holds true, then $x \in (A \backslash B)'$, hence using (7) obtain that

$$x \in A'$$

or

$$x \in B$$

Case (10) contradicts to (8), therefore, case $x \in A'$ is not possible. Case $x \in B$ is possible.

We know $x \in A$ according to (8) and $x \in B$ according to (11). Hence $(x \in A)$ and $(x \in B)$, therefore, $x \in A \cap B$.

So we showed that

$$A \backslash (A \backslash B) \subset A \cap B.$$

This means $A \backslash (A \backslash B)$ is a subset of $A \cap B$.

On the other hand, if $x \in A \cap B$, then $(x \in A)$ and $(x \in B)$, so $x \in A$, but $x \notin A \setminus B$, because $x \in B$.

So $x \in A \backslash (A \backslash B)$. Then

$$A \cap B \subset A \backslash (A \backslash B),$$

This means $A \cap B$ is a subset of $A \backslash (A \backslash B)$.

Both (12) and (13) are true, hence these sets are equal:

$$A \cap B = A \backslash (A \backslash B)$$

www.AssignmentExpert.com