Proof:A = (A ∩ B) ∪ (A ∖ B)

From CS2800 wiki
[math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{=} (A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%96}{∖} B) [/math]
Proof:
Let RHS denote the right hand side ([math](A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B) \href{/cs2800/wiki/index.php/%E2%88%AA}{∪} (A \href{/cs2800/wiki/index.php/%E2%88%96}{∖} B) [/math]).

In order to show that [math]A \href{/cs2800/wiki/index.php/Equality_(sets)}{=} RHS [/math], we must show both that 1. [math]A \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} RHS [/math] and 2. [math]RHS \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A [/math].

1. Choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math]. Clearly [math]x [/math] is either in [math]B [/math] or not. In the first case, we have that [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math] so [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} RHS [/math] (by definition of ). In the second case, we have that [math]x \in A \href{/cs2800/wiki/index.php/%E2%88%96}{∖} B [/math], so again [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} RHS [/math]. In either case, we have [math]x \in RHS [/math] as desired.

2. Now we wish to show that [math]\href{/cs2800/wiki/index.php/RHS}{RHS} \href{/cs2800/wiki/index.php/%E2%8A%86}{⊆} A [/math], so we choose an arbitrary [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/RHS}{RHS} [/math]. By definition of the union, we know that either [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%E2%88%A9}{∩} B [/math] or [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A \href{/cs2800/wiki/index.php/%E2%88%96}{∖} B [/math]. In the first case, we have [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] (by definition of ), while in the second case we have [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] by definition of . In either case we have [math]x \href{/cs2800/wiki/index.php/%5Cin}{\in} A [/math] as

desired.