Section 1.1
Sets and maps
In standard mathematics, that is, Zermelo–Fraenkel set theory, literally every mathematical object is a set. Each of the numbers $0, 1, 2, \ldots$ is actually a set:
$$ 0 = \emptyset = \lbrace \rbrace , \quad 1 = \lbrace \emptyset \rbrace = \lbrace \lbrace \rbrace \rbrace , \quad 2 = \lbrace \emptyset, \lbrace \emptyset \rbrace \rbrace = \lbrace \lbrace \rbrace , \lbrace \lbrace \rbrace \rbrace \rbrace , \ldots. $$
But because the notion of sets provides a foundation for mathematics, it does not make sense to mathematically define what a set is. Instead, people take the notion as granted and assume that sets satisfy certain axioms. But we are not going to worry to much about these issues and the following definition will be good for us.
A set is a well-defined collection of objects. If an object $x$ is inside the set $X$, we say that $x$ is an element of $X$ and write $x \in X$.
The set of natural numbers $\mathbb{Z}_{\ge 0} = \lbrace 0, 1, 2, \ldots \rbrace $ is a set. The set of integers $\mathbb{Z} = \lbrace \ldots, -1, 0, 1, \ldots \rbrace $ is a set. The set of even integers
$$ 2\mathbb{Z} = \lbrace \ldots, -2, 0, 2, 4, \ldots \rbrace = \lbrace 2x : x \in \mathbb{Z} \rbrace $$
is a set.
An issue arises when one tries to look at the set of all sets. In fact, in Zermelo–Fraenkel set theory, it is possible to prove that there is no set that contains all sets. But again, we are going to ignore such issues.
Given two sets $X$ and $Y$, if $x \in Y$ implies $x \in X$, we say that $Y$ is a subset of $X$ and write $Y \subseteq X$. Equivalently, we say that $X$ is a superset of $Y$ and write $X \supseteq Y$. For instance, $\lbrace 1, 3 \rbrace \subseteq \lbrace 1, 2, 3 \rbrace $.
Given two sets $X$ and $Y$, we define the difference $X \setminus Y$ as the subset
$$ \lbrace x \in X : x \notin Y \rbrace \subseteq X $$
of $X$.
Let $A, B, C$ be sets. Show that if $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.
Let $A$ and $B$ be sets. If $A \subseteq B$ and $B \subseteq A$, show that $A = B$. (Here, $A = B$ means that they have the same elements, i.e., $x \in A$ if and only if $x \in B$.) In the future, this will be a useful way to prove that two sets are equal.
Given two sets $X$ and $Y$, their intersection $X \cap Y$ is the set consisting of elements in both of the sets, and their union $X \cup Y$ is the set consisting of elements in either one of the sets. For instance, $\lbrace 1, 3 \rbrace \cap \lbrace 2, 3 \rbrace = \lbrace 3 \rbrace $ and $\lbrace 1, 3 \rbrace \cup \lbrace 2, 3 \rbrace = \lbrace 1, 2, 3 \rbrace $.
Let $A$ and $B$ be sets. Show that $A \cap B$ and $A \setminus B$ are disjoint, i.e., their intersection is $\emptyset$, and that their union is $A$.
For sets $A, B, C$, show that $(A \cap B) \cap C = A \cap (B \cap C)$ and $(A \cup B) \cup C = A \cup (B \cup C)$.
For sets $A, B, C$, show that $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$.
We are now ready to define maps between sets. The right way to think about a map is as a machine that takes in an element of one set and spits out an element of another set. But this is not mathematically rigorous, and to make it rigorous, we need to complicate it a little bit. But be sure to keep the intuitive picture of a map while reading the formal definition.
Given two sets $X$ and $Y$, define their Cartesian product
$$ X \times Y = \lbrace (x, y) : x \in X, y \in Y \rbrace $$
as the set of (ordered) pairs $(x, y)$ where $x$ and $y$ are elements of $X$ and $Y$ respectively.
Let $X$ and $Y$ be sets. A map or function $f : X \to Y$ is a subset $f \subseteq X \times Y$ such that for each element $x \in X$, there exists a unique $y \in Y$ such that $(x, y) \in f$. In such a case, we write $f(x) = y$ or $f : x \mapsto y$. We call the set $X$ the domain of $f$ and the set $Y$ the target or codomain of $f$.
Consider the map $f : \mathbb{R} \to \mathbb{R}$ given by $f(x) = x^2$. According to this definition, this is actually a subset
$$ f = \lbrace (x, x^2) : x \in \mathbb{R} \rbrace \subseteq \mathbb{R} \times \mathbb{R}. $$
If you draw this subset out on the coordinate plane $\mathbb{R} \times \mathbb{R}$, you get the graph of the parabola $y = x^2$.
For each set $X$, show that there is a unique map $\emptyset \to X$. (Note that this is true even for $X = \emptyset$.) Also show that there is a unique map $X \to \lbrace 0\rbrace $. (This set $\lbrace 0\rbrace $ can be replaced by any set with exactly one element.)
Given an arbitrary set $X$, there is a canonical map $X \to X$ we can define.
The identity map on $X$ is defined as
$$ \id_X : X \to X; \quad x \mapsto x. $$
Formally, it is the diagonal subset
$$ \id_X = \Delta = \lbrace (x, x) : x \in X \rbrace \subseteq X \times X. $$
We can also compose to maps to get another map.
Let $f : X \to Y$ and $g : Y \to Z$ be two maps. We define their composite to be
$$ g \circ f : X \to Z; \quad x \mapsto g(f(x)). $$
It is rather unfortunate that $g \circ f$ means applying $f$ first and then applying $g$. But this notation is pretty set in mathematics, so just remember to switch the order every time you compose maps. From now on, I will no longer use the “subset of $X \times Y$” interpretation of a map. Nobody seriously thinks of maps as sets, and instead tries to distinguish maps and sets as different types of objects. If we really want to discuss that particular subset, we will refer to it as the graph of $f$.
For $f : X \to Y$ a map, show that $f \circ \id_X = \id_Y \circ f = f$.
Given maps $f : X \to Y$, $g : Y \to Z$, and $h : Z \to W$, show that $(h \circ g) \circ f = h \circ (g \circ f)$. This shows that we can just write this composite as $h \circ g \circ f$ without ambiguity.
Let $f : X \to Y$ be a map. For a subset $T \subseteq Y$, we define its inverse image as
$$ f^{-1}(T) = \lbrace x \in X : f(x) \in T \rbrace . $$
For a subset $S \subseteq X$, we define its image as
$$ f(S) = \lbrace f(x) : x \in S \rbrace . $$
Let $f : X \to Y$ be a map. If $A, B \subseteq Y$ are two subsets, show that $f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)$ and $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$. But the analogous statement does not hold for images. Find examples of maps $f$ and $C, D \subseteq X$ such that $f(C \cap D) \neq f(C) \cap f(D)$.
A map $f : X \to Y$ is called injective if for every $y \in Y$ there exists at most one $x \in X$ such that $f(x) = y$. It is called surjective if for every $y \in Y$ there exists at least one $x \in X$ such that $f(x) = y$. A map is called bijective if it is both injective and surjective.
When a map is injective, we will sometimes draw the arrow as $X \hookrightarrow Y$ to indicate injectivity. When it is surjective, we will draw it as $X \twoheadrightarrow Y$. When it is bijective, we will draw $X \xrightarrow{\sim} Y$ or sometimes $X \cong Y$.
Show that a map $f : X \to Y$ is surjective if and only if $f(X) = Y$.
Let $f : X \to Y$ and $g : Y \to Z$ be maps. Show that if $f$ and $g$ are both injective, then $g \circ f$ is injective. Likewise, show that if $f$ and $g$ are surjective, then $g \circ f$ is surjective.
Let $f : X \to Y$ and $g : Y \to Z$ be maps. Show that if $g \circ f$ is injective, then $f$ is injective. Dually, show that if $g \circ f$ is surjective, then $g$ is surjective. Find counterexamples to the statement that the other map is injective/surjective.
Note that $\id : X \to X$ is always bijective. From this exercise, we see that if $g \circ f = \id_X$, then $f$ is injective and $g$ is surjective. Hence if $g \circ f = \id_X$ and $f \circ g = \id_Y$ then both $f$ and $g$ are bijective. In this case, we say that $f$ is an inverse map of $g$ and vice versa.
Let $f : X \to Y$ be a bijective map. Show that there exists a map $g : Y \to X$ such that $g \circ f = \id_X$ and $f \circ g = \id_Y$.
We say that a set $X$ is finite if there is a bijection between $X$ and $\lbrace 1, 2, \ldots, n\rbrace $ for some $n \in \mathbb{Z}_{\ge 0} = \lbrace 0, 1, \ldots \rbrace $. In this case, we write $\lvert X \rvert = n$ or $\# X = n$, and call $n$ the cardinality of size of the set $X$.
Let $X$ and $Y$ be finite sets. Then there exists an injection $X \hookrightarrow Y$ if and only if $\lvert X \rvert \le \lvert Y \rvert$. However, it is not true that there exists a surjection $Y \twoheadrightarrow X$ if and only if $\lvert X \rvert \le \lvert Y \rvert$. Take $X = \emptyset$.