1. Types of Functions
One-to-One (Injective)
A function $F: X \to Y$ is one-to-one if distinct inputs map to distinct outputs. No two arrows point to the same dot.
$\forall x_1, x_2 \in X$, if $F(x_1) = F(x_2)$, then $x_1 = x_2$.
Proof Example
Is $f(x) = 4x - 1$ one-to-one?
Suppose $f(x_1) = f(x_2)$.
$\implies 4x_1 - 1 = 4x_2 - 1$
$\implies 4x_1 = 4x_2$
$\implies x_1 = x_2$. Yes.
Counter Example
Is $g(n) = n^2$ one-to-one on $\mathbb{Z}$?
Let $n_1 = 1, n_2 = -1$.
$g(1) = 1$ and $g(-1) = 1$.
$g(n_1) = g(n_2)$ but $n_1 \neq n_2$. No.
Interactive Practice: Creating One-to-One Mappings
Onto (Surjective)
A function is onto if every element in the codomain is "hit" by at least one element from the domain.
$\forall y \in Y, \exists x \in X$ such that $F(x) = y$.
Proof Strategy
Start with an arbitrary $y$. Construct specific $x$ that maps to it.
Problem: Is $f(x) = 4x-1$ onto?
Let $y \in \mathbb{R}$. We need $4x-1 = y$.
Solving for $x$: $x = (y+1)/4$.
Since $(y+1)/4$ is a real number, $x$ exists. Yes.
Counterexample Strategy
Find a $y$ that cannot be generated.
Problem: Is $g(n) = 4n-1$ onto for $\mathbb{Z}$?
Try to reach $y=0$.
$4n-1 = 0 \implies n = 1/4$.
$1/4$ is not an integer. 0 is never hit. No.
Interactive Practice: Creating Onto Mappings
One-to-One Correspondence (Bijection)
A function is a bijection if it is both one-to-one and onto. This implies an Inverse Function exists.
Example: Coordinate Geometry
Define $F(x,y) = (x+y, x-y)$. Is it a bijection?
1. One-to-One: Assume $F(x_1, y_1) = F(x_2, y_2)$.
$\implies x_1+y_1 = x_2+y_2$ and $x_1-y_1 = x_2-y_2$. Adding equations gives $2x_1=2x_2 \implies x_1=x_2$. Subtracting gives $y_1=y_2$.
2. Onto: Given $(u,v)$, find $(x,y)$.
Set $x+y=u, x-y=v$. Solving gives $x=(u+v)/2, y=(u-v)/2$. These exist in $\mathbb{R}$.
Conclusion: It is a bijection.
2. Composition of Functions
$(g \circ f)(x) = g(f(x))$
"g composed with f" means apply f first, then g.
Example Calculation
$f(n) = n+1$ (Successor)
$g(n) = n^2$ (Square)
$(g \circ f)(n) = g(n+1) = (n+1)^2$
$(f \circ g)(n) = f(n^2) = n^2+1$
Order matters! $g \circ f \neq f \circ g$
Key Properties
- Identity: $f \circ I_X = f$ and $I_Y \circ f = f$.
- Inverse: $f^{-1} \circ f = I_X$ (Identity on Domain).
- If $f, g$ are one-to-one, $g \circ f$ is one-to-one.
- If $f, g$ are onto, $g \circ f$ is onto.
3. Infinite Sets & Cardinality
Countable Sets
Sets that have the same size ("cardinality") as the natural numbers $\mathbb{N}$. You can list them: 1st, 2nd, 3rd...
- $\mathbb{N}$ (Natural Numbers)
- $\mathbb{Z}$ (Integers)
- $\mathbb{Z}^{even}$ (Even Integers)
- $\mathbb{Q}^+$ (Rational Numbers)
Uncountable Sets
Sets that are strictly larger than $\mathbb{N}$. You cannot list them; any list will miss elements.
- $\mathbb{R}$ (Real Numbers)
- Intervals like $(0,1)$ or $[0,1]$
- Set of all infinite binary sequences
Paradox: Integers vs. Even Integers
Intuitively, there are half as many even numbers as integers. But mathematically, they have the same cardinality!
The One-to-One Correspondence:
$\mathbb{Z}$
... -2, -1, 0, 1, 2 ...
$\mathbb{Z}^{even}$
... -4, -2, 0, 2, 4 ...
Function: $f(n) = 2n$
Since $f$ is a bijection, $|\mathbb{Z}| = |\mathbb{Z}^{even}|$. An infinite set can have the same size as its proper subset!
Proof: Rational Numbers are Countable
How do we list fractions? We can't just do $1/1, 1/2, 1/3...$ because we'd never get to $2/1$. Instead, we use Cantor's Zig-Zag method.
Path: 1/1 $\to$ 1/2 $\to$ 2/1 $\to$ 3/1 $\to$ 2/2 $\to$ 1/3 $\to$ ...
(Skip duplicates like 2/2 if strictly counting values)
Since we can create a path that eventually hits every fraction, we can map them to $1, 2, 3...$. Thus, $|\mathbb{Q}^+| = |\mathbb{N}|$.
4. Advanced Visual Proofs
1. Uncountability of Real Numbers (Cantor's Diagonalization)
Proof that $[0, 1]$ is uncountable. Assume for contradiction we CAN list all real numbers:
1: 0.d₁₁d₁₂d₁₃...
2: 0.d₂₁d₂₂d₂₃...
3: 0.d₃₁d₃₂d₃₃...
Construct a new number $D = 0.x_1x_2x_3...$ where $x_i = 1$ if $d_{ii} \neq 1$, else $2$.
This number $D$ differs from the $n$-th number in the list at the $n$-th digit. Therefore, $D$ is missing from the list. Contradiction!
2. Geometric Bijection: $(0,1) \leftrightarrow \mathbb{R}$
How can a small segment have as many points as the infinite line? Stereographic Projection.
Imagine bending the interval $(0,1)$ into a semi-circle. Place a light source at the center. Every point on the circle casts a shadow on unique point on the infinite line below. This is a bijection.
3. Why Computer Programs are Countable
Every computer program is just a finite string of text (code).
- Convert the program text into binary (using ASCII).
- Treat this binary string as a number.
- Sort all valid programs by length, then by value.
- This creates a list: Program 1, Program 2, Program 3...
Conclusion: The set of all possible computer programs is Countable.