Algebra of Sets

The algebra of sets is the analogue of the algebra of numbers, but for set theory. This is the algebra of the set-theoretic operations of union, intersection and complementation, and the relations of equality and inclusion. 
Note: not to be confused with the mathematical structure, an algebra of sets, (X,\mathcal{F}).
== Basic set operations ==
* Complement: A^c = \{x \in S ~|~ x \notin A \}, the set of elements not in a set.
* Union: A \cap B = \{x \in S ~|~ x \in A \text{ and } x \in B\}, the set of elements that are both in set A and set B.
* Intersection: A \cup B := \{x \in S ~|~ x \in A \text{ or } x \in B\}, the set of elements in A, B, or both.
* Difference: A \setminus B := \{x \in A ~|~ x \notin B \} = A \cap B^{c}, the elements in A that are not in B.
* Symmetric Difference: A \triangle B := (A \cup B) \setminus (A \cap B), the elements inA or B, but not in both.
*Cartesian Product: A \times B := \{ (x, y) ~|~ x \in A ~\text{and}~ y \in B \}, this is a way of defining ordered pairs/sequences/lists from sets. [ADD AND LINK TO ARTICLE WITH DETAILS ON OPERATIONS ON CARTESIAN PRODUCT].
If the intersection of two sets is empty A \cap B = \varnothing, then the two sets are disjoint.
== Fundamental properties of set algebra ==
Some fundamental identities that union (\cup) and intersection (\cap) satisfy are:
*Commutative property:
** A \cup B = B \cup A
** A \cap B = B \cap A
*Associative property:
** A \cup (B \cup C) = (A \cup B) \cup C
** A \cap (B \cap C) = (A \cap B) \cap C
*Distributive property:
** A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
** A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
Two additional sets of fundamental properties involving the empty set (\varnothing), universal set (\Omega), and the complement are:
* Identity: 
** A \cup \varnothing = A
** A \cap \Omega = A
* Complement:
** A \cup A^c = \Omega
** A \cap A^c = \varnothing
The preceding five pairs of formulae encompass all of set algebra, in the sense that every valid proposition in the algebra of sets can be derived from them!
== De Morgan's Laws ==
Let A_i \subset \Omega ~\forall i, then:
* (A \cup B)^c = A^c \cap B^c or more generally, \bigl(\bigcup_i A_i \bigr)^c = \bigcap_i A_i^c
* (A \cap B)^c = A^c \cup B^c or more generally, \bigl(\bigcap_i A_i \bigr)^c = \bigcup_i A_i^c
=== Proof ===
* If x \in \bigl( \bigcup_i A_i \bigr)^c \implies x \notin \bigcup_i A_i \implies x \notin A_i ~\forall i \implies x \in A_i^c ~\forall i \implies x \in \bigcap_i A_i^c. Hence, \bigl(\bigcup_i A_i \bigr)^c \subseteq \bigcap_i A_i^c
* If x \in \bigcap_i A_i^c \implies x \in A_i^c ~\forall i \implies x \notin A_i ~\forall i \implies x \notin \bigcup_i A_i \implies x \in \bigl( \bigcup_i A_i \bigr)^c . Hence, \bigcap_i A_i^c \subseteq \bigl(\bigcup_i A_i \bigr)^c
* If x \in \bigl( \bigcap_i A_i \bigr)^c \implies x \notin \bigcap_i A_i \implies \exists A_i ~\text{s.t.}~ x \notin A_i \implies \exists A_i ~\text{s.t.}~ x \in A_i^c \implies x \in \bigcup_i A_i^c. Hence, \bigl(\bigcap_i A_i \bigr)^c \subseteq \bigcup_i A_i^c
* If x \in \bigcup_i A_i^c \implies \exists A_i^c ~\text{s.t.}~ x \in A_i^c \implies \exists A_i ~\text{s.t.}~ x \notin A_i \implies x \notin \bigcap_i A_i \implies x \in \bigl(\bigcap_i A_i \bigr)^c. Hence, \bigl(\bigcap_i A_i \bigr)^c \subseteq \bigcup_i A_i^c
== Summary/comparison with algebra of numbers ==
Summary/comparison with algebra of numbers
For numbers: 
* addition and multiplication are (1) associative, and (2) commutative.
* multiplication is distributive over addition: x \cdot (a + b) = (a + b) \cdot x = (x \cdot a) + (x \cdot b) = (x \cdot b) + (x \cdot a)
* addition is not distributive over multiplication: x + (a \cdot b) \neq (x + a) \cdot (x + b)
* the arithmetic relation \leq is (1) reflexive, (2) antisymmetric, and (3) transitive.
For sets: 
* union and intersection are (1) associative and (2) commutative.
* union is distributive over intersection: A \cup (B \cap C) = (A \cup B) \cap (A \cup C)
* intersection is distributive over union: A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
* the set relation \subseteq is (1) reflexive, (2) antisymmetric, and (3) transitive.
The union and intersection of sets may be seen as analogous to the addition and multiplication of numbers. Like addition and multiplication, the operations of union and intersection are commutative and associative, and intersection distributes over union. However, unlike addition and multiplication, union also distributes over intersection.
== To do: ==
add proofs where useful. E.g. union, intersection, maybe De Morgan’s laws, etc.
Some properties of these basic set operations include:
* The order in which one takes unions or intersections does not matter: (A \cup B) \cup C = A \cup B \cup C, and (A \cap B) \cap C = A \cap B \cap C. So, for a class of sets A_{i}we can unambiguously write: \bigcup_{i \in I} A_{i} and \bigcap_{i \in I} A_{i}.
* Distributive law applies to unions and intersections: B \cap (\bigcup_{i} A_i) = \bigcup_{i} (B \cap A_i) and B \cup (\bigcap_{i} A_i) = \bigcap_{i} (B \cup A_i).
De Morgan’s Laws: if \mathcal{C} is a class of subsets of S, then [ADD PROOFS FOR THIS, see math notes]. 
\Bigl( \bigcap_{A \in \mathcal{C}} A \Bigl)^{c} = \bigcup_{A \in \mathcal{C}} A^c and \Bigl( \bigcup_{A \in \mathcal{C}} A \Bigl)^{c} = \bigcap_{A \in \mathcal{C}} A^c