Set Theory

Subset:

• $A \subseteq B : \forall x\, (x \in A \to x \in B) \;$
• Proper subset:
• $A \subset B : \forall x\, (x \in A \to x \in B) \text{ and } A \ne B$

Set identities

Inclusion-exclusion principle

$$|A_1 \cup A_2 \cup \dots \cup A_n| = |A_1| + |A_2| + \dots + |A_n|$$

$$- \big[\, |A_1 \cap A_2| + |A_1 \cap A_3| + \dots + |A_{n-1} \cap A_n| \,\big]$$

$$+ \big[\, |A_1 \cap A_2 \cap A_3| + |A_1 \cap A_2 \cap A_4| + \dots + |A_{n-2} \cap A_{n-1} \cap A_n| \,\big]$$

$$+ \cdots+ (-1)^{n-1} |A_1 \cap A_2 \cap \dots \cap A_n|$$

Cartesian Product

$$A \times B = \{(a, b) \ | \ a \in A, b \in B\}$$

Power Set

$$\mathcal{P}(S) = \{\, A \mid A \subseteq S \,\}$$

$$\text{For set S with } n \text{ elements, } \left| \mathcal{P}(S) \right| = 2^n$$

Partition

The partition of set A is the set of nonempty sets,$\{A_1, \ldots, A_n\} \text{ where } A_1 \cup \ldots \cup A_n = A, \text{ and } A_i \cap A_j = \varnothing, \; \forall\, i,j \in \{1, \ldots, n\}, \; i \neq j$

Common questions

Prove by set identities

Element chasing - LHS and RHS subsets of each other

Membership table

$$\text{Prove that }(A \Delta B)\Delta B = A \text{ using a membership table.}$$