Sets

Motivation: Sets are the modeling language of mathematics and a fundamental skill.

Definitions

Definition 1: A set is a collection of unique objects.

Definition 2: A is defined as the subset of B (denoted by $A \subset B$) iff $\{a : a \in A \text{ and } a \in B\}$.

Definition 3: The union of two sets $A \cup B$ is defined as $A \cup B = \{x : x \in A \lor x \in B\}$. ⊕Note that in maths, $=$ implies equivalence, not assignment.

Definition 4: The intersection of two sets $A \cap B$ is defined as $A \cap B = \{x : x \in A \land x \in B\}$.

Definition 5: The product of two sets $A, B$, denoted $A \times B$ is the set of all ordered pairs ${a, b} : a \in A, b \in B$.

Definition 6: Let $A, B$ be sets, and $F \subset A \times B$. We say $F$ is a function if and only if it satisfies the following property: for each $a \in A$, there is a unique pair $(a, b) \in F$ (an input must have exactly one output). The set $A$ is called the domain of F and $B$ is called the codomain of $F$. We denote this with the arrow notation: $f: A \to B$.

Definition 7: Given a function $f: A \to B$, we define the image of $f$ as the set $f(A) = \{f(a) : a \in A\}$. Alternatively, $$\text{im } f = \{b \in B: \exists a \in A \text{ with } f(a) = b\}$$

Definition 8: Let $A, B$ be sets and $f: A \to B$ a function. The preimage of $B$ under $f$ is defined as $$f^{-1}(b) = \{a \in A: f(a) = b\}$$

Definition 9: A function $f: A \to B$ is called an injection (it is injective) if $$\exists a, a' \in A, a \neq a': f(a) \neq f(a')$$

Definition 10: A function $f: A \to B$ is called a surjection (it is surjective) if $\forall b \in B, \exists a \in A$ such that $f(a) = b$. A function is a bijection if it is both surjective and injective.

Definition 11: Inverses are unique.

Theorems

Theorem 1: $\varnothing$ is a subset of all other sets. That is, $\forall A \text{ where } A \text { is a set,} \varnothing \subset A$. ⊕This theorem isn't in the book, but I wanted to prove it to myself and to use it as a foundation for the other proofs.

Proof: There are no elements in $\varnothing$, therefore all elements in $\varnothing$ are elements of any other set.

$\square$

Theorem 2: $A \cap B \subset A$

Proof: Let $C = A \cap B = \{x : x \in A \land x \in B\}$. By definition 3, $\forall c \in C, c \in A$. Therefore $C \subset A$.

$\square$

Theorem 3: $A \subset A \cup B$

Proof: Let $C = A \cup B = \{x : x \in A \lor x \in B\}$. By definition, $C$ contains every element in $A$ and therefore $A \subset C$.

$\square$

Theorem 4a: De Morgan's law for sets: $(A \cap B)^C = A^C \cup B^C$.

Proof: $A \cap B$ contains only the elements of $X$ in both $A$ and $B$. Therefore, $(A \cap B)^C$ contains only the elements of X that do not appear in both $A$ and $B$. That is, $$(A \cap B)^C = \{x \in X: x \notin A \land x \notin B\}$$ $A^C$ contains the elements of $X$ that don't appear in $A$; similarly, $B^C$ contains the elements of $X$ that don't appear in $B$. Therefore, $A^C \cup B^C$ contains the elements of $X$ that appear either in $A$, $B$, or neither. That is, $$A^C \cup B^C = \{x \in X: x \notin A \land x \notin B\}$$ These two definitions are equivalent, and therefore $(A \cap B)^C = A^C \cup B^C$.