1: Sets and Functions

Section 1: Foundations

1: Sets and Functions

Sets form the bedrock of mathematical structures. A set is a collection of distinct objects (elements), denoted as $A = \{a, b, c\}$. Key operations include:

• Union ($A \cup B$): Elements in $A$, $B$, or both.
• Intersection ($A \cap B$): Elements common to both sets.
• Complement ($A^c$): Elements not in $A$ relative to a universal set.
• Cartesian Product ($A \times B$): Ordered pairs $(a, b)$ where $a \in A$, $b \in B$.

A relation $R$ between sets $A$ and $B$ is a subset of $A \times B$. An equivalence relation on $A$ satisfies:

1. Reflexivity: $a \sim a$ for all $a \in A$.
2. Symmetry: If $a \sim b$, then $b \sim a$.
3. Transitivity: If $a \sim b$ and $b \sim c$, then $a \sim c$.
   Equivalence relations partition sets into disjoint equivalence classes.

Functions map elements from a domain $X$ to a codomain $Y$, denoted $f: X \to Y$. Each $x \in X$ maps to exactly one $f(x) \in Y$. The range (or image) is the set $\{ f(x) \mid x \in X \} \subseteq Y$.

Function Types:

• Injective (one-to-one): If $f(x_1) = f(x_2)$ implies $x_1 = x_2$. (No two distinct inputs map to the same output.)
• Surjective (onto): Range equals codomain. (Every element in $Y$ is mapped to by some $x \in X$.)
• Bijective: Both injective and surjective. (Permits a well-defined inverse.)

Composition: For $f: X \to Y$ and $g: Y \to Z$, the composite $g \circ f: X \to Z$ is defined by $(g \circ f)(x) = g(f(x))$. Composition preserves injectivity and surjectivity.

Inverse Functions: A bijective $f: X \to Y$ has an inverse $f^{-1}: Y \to X$ such that $f^{-1}(f(x)) = x$ and $f(f^{-1}(y)) = y$.

Images and Preimages: For $f: X \to Y$:

• Image of $A \subseteq X$: $f(A) = \{ f(x) \mid x \in A \}$.
• Preimage of $B \subseteq Y$: $f^{-1}(B) = \{ x \in X \mid f(x) \in B \}$.
  Note: $f^{-1}(B)$ is defined even when $f$ lacks an inverse. Preimages preserve set operations:

$$f^{-1}(B_1 \cap B_2) = f^{-1}(B_1) \cap f^{-1}(B_2), \quad f^{-1}(B_1 \cup B_2) = f^{-1}(B_1) \cup f^{-1}(B_2).$$

Images only preserve unions: $f(A_1 \cup A_2) = f(A_1) \cup f(A_2)$.