Proving properties of set's operations

Defining operations on sets

In order to prove some properties of set's operations, it's worth precisely defining those operations:

• Union: $A \cup B = \{x \mid x \in A \lor x \in B\}$
• Intersection: $A \cap B = \{x \mid x \in A \land x \in B\}$
• Difference: $A - B = \{x \mid x \in A \land x \not \in B\}$
• Complement: $A^\complement = \{x \mid x \not \in A\}$

Summary

1. Comutative Laws
2. Associtative Laws
3. Distributive Laws
4. Identity Laws
5. Complement Laws
6. Double Complement Laws
7. Idempotent Laws
8. Universal Bound Laws
9. De Morgan's Laws
10. Absorption Laws
11. Complements of U and $\emptyset$
12. Set Difference Law

Proving properties

1 - Commutative Laws

a) $A \cup B = B \cup A$

Let $A, B$ be arbitrary sets.
Suppose $x \in A \cup B$.
Then, by definition, $x \in A \lor x \in B$.
Case 1: if $x \in A$, $x \in B \lor x \in A$.
Case 2: if $x \in B$, $x \in B \lor x \in A$.
So, $\forall x \in A \cup B$, $x \in B \lor x \in A$.
By definition, $x \in B \cup A$.
$\forall A,B$, if $x \in A \cup B$, then $x \in B \cup A$.

Let $A, B$ be arbitrary sets.
Suppose $x \in B \cup A$.
Then, by definition, $x \in B \lor x \in A$.
Case 1: if $x \in B$, $x \in B \lor x \in A$.
Case 2: if $x \in A$, $x \in B \lor x \in A$.
So, $\forall x \in B \cup A$, $x \in A \lor x \in B$.
By definition, $x \in A \cup B$.
$\forall A,B$, if $x \in B \cup A$, then $x \in A \cup B$.

$\forall x \in A \cup B$, $ x \in B \cup A$.
$\forall x \in B \cup A$, $x \in A \cup B$.
By definition, $A \cup B = B \cup A$.

b) $A \cap B = B \cap A$

Let $A, B$ be arbitrary sets.
Suppose $x \in A \cap B$.
Then, by definition, $x \in A \land x \in B$ $x \in B$
$x \in A$
Then, $x \in B \land x \in A$
So, $\forall x \in A \cap B, x \in B \land x \in A$
By definition, $x \in B \cap A$
$\forall A,B$, if $x \in A \cap B$, then $x \in B \cap A$.

Let $A, B$ be arbitrary sets.
Suppose $x \in B \cap A$.
Then, by definition, $x \in B \land x \in A$ $x \in A$
$x \in B$
Then, $x \in A \land x \in B$
So, $\forall x \in B \cap A, x \in A \land x \in B$
By definition, $x \in A \cap B$
$\forall A,B$, if $x \in B \cap A$, then $x \in A \cap B$.

$\forall A,B$, if $x \in A \cap B$, $x \in B \cap A$.
$\forall A,B$, if $x \in B \cap A$, $x \in A \cap B$.
By definition, $A \cap B = B \cap A$.

2 - Associative Laws

a) $(A \cup B) \cup C = A \cup (B \cup C)$

Let $A, B, C$ be arbitrary sets.
Suppose $x \in (A \cup B) \cup C$
Then $x \in (A \cup B) \lor x \in C$
Then $(x \in A \lor x \in B) \lor x \in C$.
Case 1: if $x \in A$, $x \in A \lor (x \in B \lor x \in C)$.
Then $x \in A \lor x \in A \cup B$, then $x \in A \cup (B \cup C)$.
Case 2: if $x \in B$, $x \in B \lor x \in C$. If $x \in B \lor x \in C, (x \in B \lor x \in C) \lor x \in A.$
Then $x \in B \cup C \lor x \in A$, then $x \in (B \cup C) \cup A$.
By commutative law, $x \in A \cup (B \cup C)$.
Case 3: if $x \in C$, $x \in B \lor x \in C$. If $x \in B \lor x \in C, (x \in B \lor x \in C) \lor x \in A.$
Then $x \in B \cup C \lor x \in A$, then $x \in (B \cup C) \cup A$.
By commutative law, $x \in A \cup (B \cup C)$.
$\forall A,B,C$, if $x \in (A \cup B) \cup C$, then $x \in A \cup (B \cup C)$.

Using the same reasoning, supposing $x \in A \cup (B \cup C)$ we conclude that
$\forall A,B,C$, if $x \in A \cup (B \cup C)$, then $x \in (A \cup B) \cup C$.

$\forall A,B,C$, if $x \in (A \cup B) \cup C$, then $x \in A \cup (B \cup C)$.
$\forall A,B,C$, if $x \in A \cup (B \cup C)$, then $x \in (A \cup B) \cup C$.
By definition, $(A \cup B) \cup C = A \cup (B \cup C)$.

b) $(A \cap B) \cap C = A \cap (B \cap C)$

Let $A, B, C$ be arbitrary sets.
Suppose $x \in (A \cap B) \cap C$.
Then $x \in (A \cap B) \land x \in C$.
Then $(x \in A \land x \in B) \land x \in C$.
$x \in B$.
$x \in C$.
$x \in B \land x \in C$, then $x \in B \cap C$.
$x \in A$, then $x \in A \land x \in (B \cap C)$.
By definition, $x \in A \cap (B \cap C)$.
So, $\forall A, B, C$, if $x \in (A \cap B) \cap C$, then $x \in A \cap (B \cap C)$.

Using the same reasoning, supposing $x \in A \cap (B \cap C)$ we conclude that
$\forall A, B, C$, if $x \in A \cap (B \cap C)$, then $x \in (A \cap B) \cap C$.
By definition, $(A \cap B) \cap C = A \cap (B \cap C)$.

3 - Distributive Laws

a)$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$

Let $A, B, C$ be arbitrary sets.
Suppose $x \in A \cup (B \cap C)$.
Then $x \in A \lor x \in (B \cap C).$
Case 1: if $x \in A$, $x \in A \lor x \in B$, then $x \in A \cup B$.
Also, if $x \in A$, $x \in A \lor x \in C$, then $x \in A \cup C$.
Then, if $x \in A$, $x \in A \cup B \land x \in A \cup C$.
By definition, $x \in (A \cup B) \cap (A \cup C).$
$\forall A,B,C$, if $x \in A \cup (B \cap C)$, then $x \in (A \cup B) \cap (A \cup C)$.

Let $A, B, C$ be arbitrary sets.
Suppose $x \in (A \cup B) \cap (A \cup C).$
Then $x \in (A \cup B) \land x \in (A \cup C).$
Then $(x \in A \lor x \in B) \land (x \in A \lor x \in C).$
Case 1: If $x \in A$, $x \in A \lor x \in (B \cap C)$, then $x \in A \cup (B \cap C)$.
Case 2: If $x \not \in A$, $x \in B \land x \in C$, then $x \in (B \cap C)$.
If $x \in (B \cap C)$, $x \in A \lor x \in (B \cap C)$.
By definition, $x \in A \cup (B \cap C)$.
$\forall A,B,C$, if $x \in (A \cup B) \cap (A \cup C)$, then $x \in A \cup (B \cap C)$.

$\forall A,B,C$, if $x \in A \cup (B \cap C)$, then $x \in (A \cup B) \cap (A \cup C)$.
$\forall A,B,C$, if $x \in (A \cup B) \cap (A \cup C)$, then $x \in A \cup (B \cap C)$.
By definition, $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.

b)$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

Let $A, B, C$ be arbitrary sets.
Suppose $x \in A \cap (B \cup C)$.
Then $x \in A \land x \in (B \cup C).$
$x \in A$.
$x \in (B \cup C).$
Then, $x \in B \lor x \in C$.
Case 1: If $x \in B, x \in A \land x \in B$, then $x \in A \cap B$.
Case 2: If $x \in C, x \in A \land x \in C$, then $x \in A \cap C$.
Then, $x \in A \cap B \lor x \in A \cap C$.
By definition, $x \in (A \cap B) \cup (A \cap C).$
$\forall A,B,C$, if $x \in A \cap (B \cup C)$, then $x \in (A \cap B) \cup (A \cap C)$.

Let $A, B, C$ be arbitrary sets.
Suppose $x \in (A \cap B) \cup (A \cap C)$.
Then $x \in (A \cap B) \lor x \in (A \cap C)$.
Case 1: if $x \in (A \cap B), x \in A \land x \in B$.
If $x \in B, x \in B \lor x \in C$, then $x \in B \cup C$.
Given that $x \in A \land x \in B \cup C, x \in A \cap (B \cup C)$.
Case 2: if $x \in (A \cap C), x \in A \land x \in C$.
If $x \in C, x \in B \lor x \in C$, then $x \in B \cup C$.
Given that $x \in A \land x \in B \cup C, x \in A \cap (B \cup C)$.
$\forall A,B,C$, if $x \in (A \cap B) \cup (A \cap C)$, then $x \in A \cap (B \cup C)$.

$\forall A,B,C$, if $x \in A \cap (B \cup C)$, then $x \in (A \cap B) \cup (A \cap C)$.
$\forall A,B,C$, if $x \in (A \cap B) \cup (A \cap C)$, then $x \in A \cap (B \cup C)$.
By definition, $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

4 - Identity Laws

a) $A \cup \emptyset = A$

Let $A$ be an arbitrary set.
Suppose $x \in A \cup \emptyset$.
Then $x \in A \lor x \in \emptyset$.
Case 1: if $x \in A, x \in A$.
Case 2: if $x \not \in A, x \in \emptyset$. Absurd, then $x \in A$.
$\forall A$, if $x \in A \cup \emptyset$, then $x \in A$.

Let $A$ be an arbitrary set.
Suppose $x \in A$.
If $x \in A$, $x \in A \lor x \in \emptyset$, then $x \in A \cup \emptyset$.
$\forall A$, if $x \in A, x \in A \cup \emptyset$.

$\forall A$, if $x \in A \cup \emptyset$, then $x \in A$.
$\forall A$, if $x \in A, x \in A \cup \emptyset$.
By definition, $A \cup \emptyset = A$.

b) $A \cap U = A$

Let $A$ be an arbitrary set and $A \subset U$.
Suppose $x \in A \cap U$.
Then $x \in A \land x \in U$.
$x \in A$.
$\forall A$, if $x \in A \cap U$, then $x \in A$.

Let $A$ be an arbitraty set and $A \subset U$.
Then $\forall x \in A, x \in U$.
Suppose $x \in A$, then $x \in U$, then $x \in A \cap U$.
$\forall A$, if $x \in A$, then $x \in A \cap U$.

$\forall A$, if $x \in A \cap U$, then $x \in A$.
$\forall A$, if $x \in A$, then $x \in A \cap U$.
By definition, $A \cap U = A$.

5 - Complement Laws

a) $A \cup A^\complement = U$

Let $A$ be an arbitrary set and $A \subset U$.
Suppose $x \in A \cup A^\complement$.
Then $x \in A \lor x \in A^\complement$.
$x \in U$.
Case 1: if $x \in A$, then $x \in U$.
Case 2: if $x \in A^\complement$, $x \not \in A$, $x \in U$.
$\forall A$, if $x \in A \cup A^\complement$, then $x \in U$.

Let $A$ be an arbitrary set and $A \subset U$.
Suppose $x \in U$.
$x \in A \lor x \not \in A$.
So, $x \in A \cup A^\complement$.
$\forall A$, if $x \in U$, then $x \in A \cup A^\complement$.

$\forall A$, if $x \in A \cup A^\complement$, then $x \in U$.
$\forall A$, if $x \in U$, then $x \in A \cup A^\complement$.
By definition, $A \cup A^\complement = U$.

b) $A \cap A^\complement = \emptyset$

Let $A$ be an arbitraty set.
Suppose $x \in A \cap A^\complement$.
Then $x \in A \land x \not \in A$. Absurd.
$\forall A, \not \exists x \mid x \in A \cap A^\complement$.
By the the definition of an empty set and the uniqueness of the empty set, $A \cap A^\complement = \emptyset$.

6 - Double Complement Law

a)$(A^\complement)^\complement = A$

Let $A$ be an arbitrary set.
Suppose $x \in (A^\complement)^\complement$. Then $x \not \in A^\complement$. Then $x \in A$. $\forall A$, if $x \in (A^\complement)^\complement$, then $x \in A$.
Let $A$ be an arbitrary set.
Suppose $x \in A$.
Then $x \not \in A^\complement$.
By definition, $x \in (A^\complement)^\complement$.
$\forall A$, if $x \in A$, then $x \in (A^\complement)^\complement$.
$\forall A$, if $x \in (A^\complement)^\complement$, then $x \in A$. $\forall A$, if $x \in A$, then $x \in (A^\complement)^\complement$. By definition, $(A^\complement)^\complement = A$.

7 - Idempotent Laws

a)$A \cup A = A$

Let $A$ be an arbitrary set.
Suppose $x \in A \cup A$.
Then $x \in A \lor x \in A$.
$x \in A$.
$\forall A$, if $x \in A \cup A$, then $x \in A$.

Let $A$ be an arbitrary set.
Suppose $x \in A$.
Then $x \in A \lor x \in A$.
By definition, $x \in A \cup A$.
$\forall A$, if $x \in A$, then $x \in A \cup A$.

$\forall A$, if $x \in A \cup A$, then $x \in A$.
$\forall A$, if $x \in A$, then $x \in A \cup A$.
By definition, $A \cup A = A$.

b)$A \cap A = A$

Let $A$ be an arbitrary set.
Suppose $x \in A \cap A$.
Then $x \in A \land x \in A$.
$x \in A$.
$\forall A$, if $x \in A \cap A$, then $x \in A$.

Let $A$ be an arbitrary set.
Suppose $x \in A$.
Then $x \in A \land x \in A$.
By definition, $x \in A \cap A$.
$\forall A$, if $x \in A$, then $x \in A \cap A$.

$\forall A$, if $x \in A \cap A$, then $x \in A$.
$\forall A$, if $x \in A$, then $x \in A \cap A$.
By definition, $A \cap A = A$.

8 - Universal Bound Laws

a)$A \cup U = U$

Let $A$ be an arbitrary set and $A \subset U$.
By definition of subset, $\forall x \in A, x \in U$.
Suppose $x \in A \cup U$.
Then $x \in A \lor x \in U$.
Case 1: if $x \in A, x \in U$.
Case 2: if $x \in U, x \in U$.
$\forall x \in A \cup U, x \in U$.

Let $A$ be an arbitrary set and $A \subset U$.
By definition of subset, $\forall x \in A, x \in U$.
Suppose $x \in U$.
Then $x \in A \lor x \in U$, then $x \in A \cup U$.
$\forall x \in A, x \in A \cup U$.

$\forall x \in A \cup U, x \in U$.
$\forall x \in A, x \in A \cup U$.
By definition, $A \cup U = U$.

b)$A \cap \emptyset = \emptyset$

Let $A$ be an arbitrary set.
Suppose $x \in A \cap \emptyset$.
Then $x \in A \land x \in \emptyset$.
$x \in \emptyset$. Absurd.
Then $\not \exists x \mid x \in A \cap \emptyset$.

By the the definition of an empty set and the uniqueness of the empty set, $A \cap \emptyset = \emptyset$.

9 - De Morgan's Laws

a)$(A \cup B)^\complement = A^\complement \cap B^\complement$

b)$(A \cap B)^\complement = A^\complement \cup B^\complement$

10 - Absorption Laws

a)$A \cup (A \cap B) = A$

Let $A, B$ be arbitrary sets.
Suppose $x \in A \cup (A \cap B)$.
Then $x \in A \lor x \in (A \cap B)$.
Case 1: if $x \in A$, then $x \in A$.
Case 2: if $x \in A \cap B$, then $x \in A \land x \in B$, then $x \in A$.
$\forall A$, if $x \in A \cup (A \cap B)$, then $x \in A$.

Let $A, B$ be arbitrary sets.
Suppose $x \in A$.
Then $x \in A \lor x \in A \cup (A \cap B)$.
$\forall A$, if $x \in A$, then $x \in A \cup (A \cap B)$.

$\forall A$, if $x \in A \cup (A \cap B)$, then $x \in A$.
$\forall A$, if $x \in A$, then $x \in A \cup (A \cap B)$.
By definition, $A \cup (A \cap B) = A$.

b)$A \cap (A \cup B) = A$

Let $A, B$ be arbitrary sets.
Suppose $x \in A \cap (A \cup B)$.
Then $x \in A \land x \in (A \cup B)$.
$x \in A$.
$\forall A$, if $x \in A \cap (A \cup B)$, then $x \in A$.

Let $A, B$ be arbitrary sets.
Suppose $x \in A$.
Then $x \in A \lor x \in B$, then $x \in (A \cup B)$.
Then $x \in A \land x \in (A \cup B)$, then $x \in A \cap (A \cup B)$.
$\forall A$, if $x \in A$, then $x \in A \cap (A \cup B)$.

$\forall A$, if $x \in A \cap (A \cup B)$, then $x \in A$.
$\forall A$, if $x \in A$, then $x \in A \cap (A \cup B)$.
By definition, $A \cap (A \cup B) = A$.

11 - Complements of U and $\emptyset$

a)$U^\complement = \emptyset$

Let $A$ be an arbitrary set and $A \subset U$.
So, $\forall x \in A, x \in U$.
Suppose $x \in U^\complement$.
Then, $x \not \in U$. Absurd.
Then, $\not \exists x \mid x \in U^\complement$.

By the the definition of an empty set and the uniqueness of the empty set, $U^\complement = \emptyset$.

b)$\emptyset^\complement = U$

Suppose an arbitrary $x \in \emptyset^\complement$.
Then $x \not \in \emptyset$.
Then $x \in U$.
$\forall x \in \emptyset^\complement$, $x \in U$.

Suppose an arbitrary $x \in U$.
Then $x \not \in \emptyset$.
Then $x \in \emptyset^\complement$.
$\forall x \in U$, then $x \in \emptyset^\complement$.

$\forall x \in \emptyset^\complement$, $x \in U$.
$\forall x \in U$, then $x \in \emptyset^\complement$.
By definition, $\emptyset^\complement = U$.

12 - Set Difference Law

a)$A - B = A \cap B^\complement$

Let $A, B$ be arbitrary sets.
Suppose $x \in A - B$.
Then $x \in A \land x \not \in B$.
$x \in A$.
By definition, if $x \not \in B$, then $x \in B^\complement$.
Then, $x \in A \land x \in B^\complement$, then $x \in A \cap B^\complement$.
$\forall A, B$, if $x \in A - B$, then $x \in A \cap B^\complement$.

Let $A, B$ be arbitrary sets.
Suppose $x \in A \cap B^\complement$.
Then, $x \in A \land x \in B^\complement$.
If $x \in B^\complement$, then $x \not \in B$.
$x \in A$.
$If x \in A \land x \not \in B$, by definition, $x \in A - B$.
$\forall A, B$, if $x \in A \cap B^\complement$, $x \in A - B$.

$\forall A, B$, if $x \in A - B$, then $x \in A \cap B^\complement$.
$\forall A, B$, if $x \in A \cap B^\complement$, $x \in A - B$.
By definition, $A - B = A \cap B^\complement$.