Interactions between functions and sets
If we already know about sets, then we can actually construct functions directly. At first the definition looks a little strange.
Definition. Let $X$ and $Y$ be sets. A function $f : X \to Y$ is a subset \(\Gamma \subseteq X \times Y\) satisfying the condition \(\forall~ x, \exists !~ (x',y) \in \Gamma, x = x'\) In other words, in our subset of pairs, $\Gamma$, given an element $x \in X$, there is one and exactly one ordered pair of the form $(x,y)$.
Given a function, $\Gamma_f$, we can define application of the function to an element $x \in X$ as \(x \mapsto y\) where $y$ is the unique element of $Y$ making $(x,y) \in \Gamma_f$ hold.
Given a function of the familiar type $f : X \to Y$, we can make subset of $X \times Y$ as \(\Gamma_f := \lbrace (x,f(x)) \mid x \in X \rbrace\) This is commonly called the graph of $f$.
Given a $f : A \to B$ and a subset $X \subseteq A$, we define a new subset of $B$.
Definition. The image of $X$ under the function $f$ is the set \(f(X) := \lbrace b \mid \exists~ x \in X, f x = b \rbrace\)
Example. If \(f : \mathbb{N} \to \mathbb{N} \\ n \mapsto n^2\) is our function, then $f(\mathbb{N})$ is the set of natural numbers which are squares.
If we instead start with a subset $Y \subseteq B$, then we can create a subset of $A$.
Definition. The pre-image (or inverse image) of $Y$ is the set \(f^{-1}(Y) := \{ a \mid f(a) \in Y \}\)
Coming back to our example of the squaring map, we would have \(f^{-1}(\lbrace 0,1,2,3,4,5,6,7,8 \rbrace) = \{0,1,2\}\)
Lemma. $f$ is surjective if and only if $f(X) = Y$.
Proof. (Expand to view)
Assume that $f$ is surjective. From the definition, we know that $f(X) \subseteq Y$. For the other direction, assume we have $y \in Y$. Since $f$ is surjective, there exists a $x \in X$ with $f(x) = y$. But, by definition of the image $X$ under $f$, this says $y \in f(X)$. Assume that $f(X) = Y$. To show that $f$ is surjective, we choose some $y \in Y$ and look for an $x$ with $f(x) = y$. But, by definition of the image, we know there is such an $x$. ■
More generally, we get two statements describing what happens when we take images of pre-images and pre-images of images.
Lemma. For any $Y$, we have
\(f(f^{-1} Y) \subseteq Y\)
Proof. (Expand to view)
Let $b \in f(f^{-1} Y)$. We unfold the definitions to check this. Since $b \in f(f^{-1} Y)$, we have, by definition, there exists some $a \in f^{-1} Y$ such that $f(a) = b$. Since $a \in f^{-1} Y$, by definition, we have $f(a) \in Y$. Thus, $b = f(a) \in Y$. ■
Note that this is not an equality in general. If we have an equality, then every element of $Y$ is in the image of $f$ applied to $f^{-1} Y$. In particular, it forces $f$ to surject onto $Y$.
Lemma. For any $X$, we have
\(X \subseteq f^{-1}(f(X))\)
Proof. (Expand to view)
Again, this comes from chaining together the definitions. Assume that $a \in X$. Then $f(a) \in f(X)$. Thus, by definition, $a \in f^{-1} (f(X))$. ■
Again this is not always an equality. For example, lets taking our squaring map but now view it a function $\mathbb{Z} \to \mathbb{Z}$. If $X = \mathbb{N}$, then $f^{-1}(f(\mathbb{N})) = \mathbb{Z}$.
Both images and pre-images behave well with respect to unions and intersections. We have
-- The union of inverse images is the inverse image of the union
theorem union_preimage (f : α → β) (Y Y' : Set β) :
f⁻¹ (Y ∪ Y') = f⁻¹ Y ∪ f⁻¹ Y' := by rfl
-- The intersection of inverse images is the inverse image of
-- the intersection
theorem inter_preimage (f : α → β) (Y Y' : Set β) :
f⁻¹ (Y ∩ Y') = f⁻¹ Y ∩ f⁻¹ Y' := by rfl
-- The union of images is the image of the union
theorem union_image (f : α → β) (X X' : Set α) :
Image f (X ∪ X') = Image f X ∪ Image f X' := by
set_extensionality b
· intro h
have ⟨a,h'⟩ := h
cases h'.left with
| inl hl => exact Or.inl ⟨a,hl,h'.right⟩
| inr hr => exact Or.inr ⟨a,hr,h'.right⟩
· intro h
cases h with
| inl hl =>
have ⟨a,h'⟩ := hl
exact ⟨a,⟨Or.inl h'.left,h'.right⟩⟩
| inr hr =>
have ⟨a,h'⟩ := hr
exact ⟨a,⟨Or.inr h'.left,h'.right⟩⟩
-- The image of the intersection is a subset of the
-- intersection of the image
theorem inter_image (f : α → β) (X X' : Set α) :
Image f (X ∩ X') ⊆ Image f X ∩ Image f X' := by
intro b h
have ⟨a,h'⟩ := h
exact ⟨⟨a,⟨h'.left.left,h'.right⟩⟩,⟨a,⟨h'.left.right,h'.right⟩⟩⟩ In general, $f (X \cap X’) \neq f(X) \cap f(X’)$. For example, take the unique function $f : \mathbb{Z} \to \lbrace 0 \rbrace$, $X$ the odd integers, and $X’$ the even integers. Then $X \cap X’ = \varnothing $ but $f(X) \cap f(X’) = \lbrace 0\rbrace$.
Being in bijection
Saying that we have a bijection $f : A \to B$ is quite strong. For each element of $a$ there is exactly one element of $b$ and vice-versa. You go back and forth by apply $f$ or its inverse. While particular bijections can be highly non-trivial, we can still abstract them as a “change of labels” for a set.
Example. Let $R_m$ be the complex roots of the polynomial $z^m - 1$. The roots are of the form $e^{2 \pi \imath j/m}$ for $j = 0,\ldots,m-1$. Thus, there is a bijection between the set of $R_m$ and the set $[m] := \lbrace 0, 1, \ldots, m-1 \rbrace$.
One of this is very simple, $[m]$, while the other carries interesting algebraic information.
Definition. We say $A$ and B$ are in bijection if there exists a bijection $f : A \to B$. We write $A \cong B$ if $A$ and $B$ are in bijection.
Even if $A \cong B$, there is, in general, not a single bijection nor a canonical choice for one.
Let’s look at self-bijections $\sigma : [m] \to [m]$. In general, if we have an injective function $f : [m] \to A$, then we have at least $m$ distinct (up to equality) elements of $A$. Now, if $A = [m]$, then we only have $[m]$ distinct elements to being with. Thus, $\sigma : [m] \to [m]$ is bijective if and only if it is injective.
Similarly, if $\sigma : [m] \to [m]$ is surjective, then we have to have $m$ elements in $\sigma([m])$. But, for any function with domain $[m]$, the image can have at most $m$ elements since we only have $m$ elements to plug in to $f$. If we have exactly $m$ elements, then $\sigma$ must be injective. Each time $\sigma(i) = \sigma(j)$, with $i \neq j$, we drop the size of the image of by 1. Thus, $\sigma$ is bijective if and only if it is surjective.
We have established the following result.
Theorem. (Pigeonhole Principle) A function $f : X \to Y$ with $X, Y$ finite and of the same order is a bijection if and only if it is an injection if and only if it is a surjection.
Similar logic gives the
Corollary. If $f : X \to Y$ is a function between finite sets and $|X| < |Y|$, then $f$ is not surjective. If $|X| > |Y|$, then $f$ is not injective.
The previous results tell us to recognize bijections between finite sets. We see that for $\sigma : [m] \to [m]$ to be a bijection. We have some value $\sigma(0)$. Then there is some value $\sigma(1) \neq \sigma(0)$. Then $\sigma(2) \neq \sigma(1)$ and $\neq \sigma(0)$ . . . Finally, leaving a unique choice for $\sigma(m)$.
So a self-bijection of $[m]$ is scrambling of the order of the numbers $0,1,2,\ldots, m-1$. There are $m$ choices for the value of $0$, $m-1$ choices for $1$,. . ., $2$ choices for $m-2$, and a single choice for $m-1$. Thus, we have \(m! := m(m-1)(m-2) \cdots 2 \cdot 1\) unique self-bijections of $[m]$. Such self-bijections are called permutations.
Example. Let’s write down all the permutations of the set $[3]$. We as (possibly) disordered lists: \(123, 132, 213, 312, 231, 321\) The first entry of the list is the identity function.