Function Notation for 104.

• $E\sube A$ then $f(E) = \{f(x)\} _{x \in E}$ is its image under $f$
• $D \sube B$ then $f^{-1}(D) = \{x\} _{f(x) \in D}$ is its preimage under $f$
• $f$ is injective iff, for all $y \in B$, $f^{-1}(\{y\})$ has at most $1$ element.
• $f$ is surjective iff $f(A) = B$.

Equipotence

Sets $A$ and $B$ are equipotent, denoted $A \sim B$, if there exists a bijection $f : A \rightarrow B$. Moreover, this notion defines an equivalence class on the two sets.

$$ \hspace{42pt} \textbf{Transitivity. } A\sim B \wedge B\sim C \implies A \sim C \\

\textbf{Reflexive. } A \sim A \hspace{68pt}\\

\textbf{Symmetric. } A \sim B \iff B \sim A $$

• Proof

Cardinality

The notion of equipotence lets us rigorously define classes of size $|\cdot|$ on sets. A set $A$ is

• Finite iff $A \sim [n] = \{1, \dots, n\}$ or $A = \empty$.
• Infinite iff $A$ is not finite, or equivalently, there exists a proper subset $B\sub A$ for which $A \sim B$.
• Countable iff $A \sim \N$.
• Uncountable iff $A$ is infinite but not countable.
• At most countable iff $A$ is finite or countable.

<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />

No Infinite Cardinality between Finite and Countable. Countable sets are the smallest infinite sets — i.e. any infinite subset of a countable set is also countable.

</aside>