Subsection Sets
Definition 0.1.1. Sets.
A set is a collection of objects. An object \(x\) is a member (or element) of a set \(A\) if \(A\) contains \(x\text{.}\) In this case, we write \(x \in A\text{.}\) If \(x\) is not a member of \(A\text{,}\) we write \(x \notin A\text{.}\)
We use curly braces to describe the contents of a set. For example, \(A=\{1,2,3\}\) is the set containing the first three positive integers, and \(B=\{1,2,3,\dots\}\) is the set of all positive integers. The defining property of sets is that they are completely determined by their members, and nothing more. In particular, when describing sets as above, it does not matter in what order the elements are listed, nor if they are repeated: e.g., \(\{1,2,3\}\text{,}\) \(\{2,1,3\}\text{,}\) and \(\{2,1,1,3,2\}\) are three descriptions of the same set. This somewhat slippery notion is made perfectly clear by specifying exactly what it means for two sets to be equal, as we do below.
Definition 0.1.2. Set equality.
Sets \(A\) and \(B\) are equal, denoted \(A=B\text{,}\) if they have precisely the same elements: i.e., if for any object \(x\text{,}\) we have \(x\in A\) if and only if \(x\in B\text{.}\)
Set membership naturally extends to a notion of one set “lying” within another.
Definition 0.1.3. Set inclusion (subsets).
A set \(A\) is a subset of a set \(B\text{,}\) denoted \(A \subseteq B\text{,}\) if every member of \(A\) is a member of \(B\text{:}\) i.e., \(x\in A\) implies \(x\in B\) for any object \(x\text{.}\) The relation \(A\subseteq B\) is called set inclusion.
With the fundamental notions of membership, equality, and subset in place, we now introduce means of building new sets from existing ones. The first is a manner of carving out a subset of a given set using a specified property.
Definition 0.1.5. Set-builder notation.
Let \(A\) be a set, and let \(P\) be a property that elements of \(A\) either satisfy or do not satisfy. For an element \(x\in A\text{,}\) let \(P(x)\) denote the statement that \(x\) satisfies \(P\text{.}\) The set of all elements of \(A\) satisfying \(P\) is denoted
\begin{equation*}
\{x \in A \colon P(x) \}\text{.}
\end{equation*}
Example 0.1.7.
Let \(A=\{0,1,2,\dots \}\) be the set of nonnegative integers. The subset \(B=\{0,2,4,\dots\}\) of even positive integers can be described using set-builder notation as
\begin{equation*}
B=\{x\in A\colon x \text{ is even}\}\text{,}
\end{equation*}
or alternatively,
\begin{equation*}
B=\{x\in A\colon x=2k \text{ for some integer} k\}\text{.}
\end{equation*}
Next we use set builder notation, the set membership relation, and some basic logic to define the union, intersection, and difference of sets.
Definition 0.1.8. Union, intersection, difference, and complement.
Let \(A\) and \(B\) be subsets of a common set \(X\text{.}\)
With the help of these set operations, we can now describe some common sets used in mathematics.
Definition 0.1.9. Common mathematical sets.
We denote by \(\mathbb{R}\) the set of all real numbers. The integers \(\Z\) and rational numbers \(\mathbb{Q}\) are the subsets of \(\R\) defined as
\begin{align*}
\mathbb{Z} \amp =\{0,1,2,3,\dots\}\cup \{-1,-2,-3,\dots\} \\
\mathbb{Q} \amp = \{x\in\mathbb{R}\colon x=\tfrac{m}{n} \text{ for some } m,n\in\Z\} \text{.}
\end{align*}
This yields the following chain of subsets:
\begin{equation}
\mathbb{Z}\subseteq\mathbb{Q}\subseteq\mathbb{R}\text{.}\tag{0.1.1}
\end{equation}
The empty set is the set containing no objects, denoted \(\{\ \}\) or \(\emptyset\text{.}\)
The set \(\{1,2,3,\dots\}\) of all positive integers is denoted \(\Z_{+}\text{.}\)
The
power set of a set
\(A\) is the set of all subsets of
\(A\text{.}\) We will make use of this notion in our very first definition (
1.1.1).
Definition 0.1.10. Power set.
Given a set \(A\text{,}\) its power set \(\mathcal{P}(A)\) is defined as the set of all subsets of \(A\text{.}\)
Example 0.1.11. Power set.
Let \(A=\{a,7\}\text{.}\) The power set \(\mathcal{P}(A)\) is the set of all subsets of \(A\text{.}\) We can enumerate \(\mathcal{P}(A)\) systematically by listing all the subsets in order of increasing cardinality. There is one subset of \(A\) containing zero elements: namely, the empty set \(\emptyset\text{.}\) The two subsets of \(A\) containing exactly one element are \(\{a\}\) and \(\{7\}\text{.}\) Lastly, the unique subset of \(A\) containing two elements is \(A\) itself. We conclude that
\begin{equation*}
\mathcal{P}(A)=\{ \emptyset, \{a\}, \{7\}, \{a,7\}\}\text{.}
\end{equation*}
In general if \(A\) has cardinality \(\abs{A}=n\text{,}\) then \(\mathcal{P}(A)\) has cardinality \(\abs{\mathcal{P}(A)}=2^n\text{.}\)
Lastly, we define the cartesian product of sets, which is a formal description of an ordered collection of objects.
Definition 0.1.12. Cartesian product (finite).
An \(n\)-tuple (or sequence) of the sets \(A_1, A_2,\dots, A_n\) is an ordered list \((a_1,a_2,\dots, a_n)\) such that \(a_i\in A_i\) for all \(1\leq i\leq n\text{.}\) We define two \(n\)-tuples \((a_1,a_2,\dots, a_n)\text{,}\) and \((a_1',a_2',\dots, a_n')\) to be equal, denoted \((a_1,a_2,\dots, a_n)=(a_1',a_2',\dots, a_n')\text{,}\) if \(a_i=a_i'\) for all \(1\leq i\leq n\text{.}\) We call \(n\) the length of the sequence \((a_1,a_2,\dots, a_n)\text{,}\) and we call \(a_i\) its \(i\)-th entry for all \(1\leq i\leq n\text{.}\)
The (Cartesian) product of the sets \(A_1, A_2,\dots, A_n\text{,}\) denoted \(A_1\times A_2\times\cdots \times A_n\) or \(\displaystyle\prod_{i=1}^nA_i\text{,}\) is the set of all \(n\)-tuples: i.e.,
\begin{equation*}
\prod_{i=1}^nA_i=A_1\times A_2\times\cdots \times A_n=\{(a_1,a_2,\dots, a_n)\colon a_i\in A_i \text{ for all } 1\leq i\leq n\}\text{.}
\end{equation*}
Given a set \(A\text{,}\) its \(n\)-ary Cartesian product \(A^n\) is defined as
\begin{equation*}
A^n=\prod_{i=1}^n A=\underset{n\text{ times}}{\underbrace{A\times A\times\cdots \times A}}\text{.}
\end{equation*}
The notion of a Cartesian product can be generalized to an infinite list of sets \(A_1, A_2, \dots\text{,}\) and indeed to any collection \(\{A_i\}_{i\in I}\) indexed by a set \(I\text{.}\)
Definition 0.1.15. I-tuple.
Let \(I\) and \(X\) be sets. An \(I\)-tuple with entries (or coordinates) in \(X\) is a function \(f\colon I\rightarrow X
\text{.}\) Given an \(I\)-tuple \(f\) and element \(i\in I\) we will often denote the value \(f(i)\) as \(x_i\text{,}\) and denote \(f\) itself as \(f=(x_i)_{i\in I}\text{.}\) In analogy to finite tuples, we call \(x_i\) the \(i\)-th entry or coordinate of \(f\text{.}\)
Definition 0.1.16. Cartesian product (arbitrary).
Let \(X\) be a set, and let \(\{A_i\}_{i\in I}\) be a collection of subsets \(A_i\subseteq X\) indexed by the set \(I\text{.}\) The Cartesian product \(\prod_{i\in I}A_i\) of this collection is defined as
\begin{align*}
\prod_{i\in I}A_i\amp =\{f\colon I\rightarrow X\colon f(i)\in A_i \text{ for all } i\in I\} \\
\amp =\{(x_i)_{i\in I}\colon x_i\in A_i \text{ for all } i\in I\}\text{.}
\end{align*}
In other words, the Cartesian product is the set of all \(I\)-tuples with coordinates in \(X\) whose \(i\)-th coordinate is an element of \(A_i\) for all \(i\in I\text{.}\)
In the special case where \(A_i=A\) for all \(i\in I\text{,}\) we denote \(\prod_{i\in I}A\) as \(A^I\text{.}\)
Subsection Functions
Definition 0.1.17. Functions.
Let \(X\) and \(Y\) be two sets. A function from \(X\) to \(Y\), denoted \(f\colon X\rightarrow Y\text{,}\) is a rule which, given any input \(x\in X\text{,}\) returns an output \(y\in Y\text{.}\) In this case we write \(y=f(x)\) and call \(y\) the image of \(x\) under \(f\), or the value of \(f\) at \(x\). Similarly, we say \(f\) maps (or sends) the input \(x\) to the output \(y\text{.}\)
The set \(X\) is called the domain of \(f\text{;}\) the set \(Y\) is called the codomain of \(f\text{.}\)
When we wish to indicate what rule defines the function, we use the elaborated notation
\begin{align*}
f\colon X \amp\rightarrow Y\\
x \amp\mapsto f(x)\text{.}
\end{align*}
This is read as “The function \(f\) with domain \(X\) and codomain \(Y\) maps an input \(x\) to the output \(f(x)\)”.
Example 0.1.18.
Consider the function
\begin{align*}
f\colon \mathbb{Z}\amp \rightarrow \mathbb{Z}\\
x\amp\mapsto x^2 \text{.}
\end{align*}
This function has domain and codomain equal to \(\mathbb{Z}\) and maps an integer to its square.
Example 0.1.19. Arithmetic operations as functions.
Our familiar arithmetic operations can be expressed as functions whose inputs are pairs of numbers: addition is the function
\begin{align*}
a\colon \R\times \R \amp\rightarrow \R \\
(x,y) \amp\mapsto x+y
\end{align*}
and multiplication is the function
\begin{align*}
m\colon\mathbb{R}\times \mathbb{R} \amp \rightarrow \mathbb{R}\\
(x,y)\amp\mapsto xy
\end{align*}
As with sets and tuples, we are obliged to specify what we mean for two functions to be equal. The definition below makes clear how the the domain and codomain, as well as the rule that takes inputs to outputs, are all essential ingredients of a function.
Definition 0.1.21. Function equality.
Functions \(f\) and \(g\) are equal if
they have the same domain \(X\) and codomain \(Y\text{,}\) and
for all \(x\in X\text{,}\) we have \(f(x)=g(x)\text{.}\)
Definition 0.1.22. Image of a set.
Given a function \(f\colon X\rightarrow Y\) and a subset \(A \subseteq X\text{,}\) the image of \(A\) under \(f\), denoted \(f(A)\text{,}\) is defined as
\begin{equation*}
f(A)=\left\{ y \in Y \colon f(a)=y \text{ for some } a \in A \right\}\text{.}
\end{equation*}
In other words, \(f(A)\) is the set of all outputs \(f(a)\text{,}\) where \(a\in X\text{.}\)
The image of \(f\), denoted \(\operatorname{im} f\text{,}\) is the set of all outputs of \(f\text{:}\) i.e.,
\begin{equation*}
\operatorname{im} f=f(X)=\left\{ y \in Y \colon f(x)=y \text{ for some } x \in X \right\}\text{.}
\end{equation*}
Definition 0.1.23. Preimage of set.
Given a function \(f\colon X\rightarrow Y\text{,}\) the preimage of a subset \(A\subseteq Y\) is the subset \(f^{-1}(A)\subseteq X\) defined as
\begin{equation*}
f^{-1}(A)=\{x\in X\colon f(x)\in A\}\text{.}
\end{equation*}
In plain English: the preimage of \(A\) under \(f\) is the set of all \(x\in X\) whose image under \(f\) lies in \(A\text{.}\)
Definition 0.1.24. Injective, surjective, bijective.
Let \(f\colon X\rightarrow Y\) be a function.
The function \(f\) is injective (or one-to-one) if for all \(x,x'\in X\text{,}\) if \(f(x)=f(x')\text{,}\) then \(x=x'\text{:}\) equivalently, if \(x\ne x'\text{,}\) then \(f(x)\ne f(x')\text{.}\)
The function \(f\) is surjective (or onto) if for all \(y\in Y\text{,}\) there is an \(x\in X\) such that \(f(x)=y\text{:}\) equivalently, \(\im f=Y\text{.}\)
The function \(f\) is bijective (or a one-to-one correspondence) if it is injective and surjective.
Example 0.1.25. Role of domain and codomain in injectivity and surjectivity.
Consider the following three functions
\begin{align*}
f\colon \R \amp\rightarrow \R \amp g\colon [0,\infty)\amp\rightarrow \R \amp h\colon [0,\infty)\amp \rightarrow [0,\infty) \\
x \amp\mapsto x^2 \amp x \amp\mapsto x^2 \amp x \amp\mapsto x^2 \amp \text{.}
\end{align*}
Although all three functions are defined using the same rule (\(x\mapsto x^2\)), they are not equal thanks to their differing domains and/or codomains. The choice of domain and codomain in these examples also plays a crucial role in determining whether the function is injective and/or surjective. The function \(f\) is neither injective (\(f(-2)=f(2)=4\)) nor surjective (\(f(X)=[0,\infty)\ne \R\)); the function \(g\) is injective but not surjective; the function \(h\) is both injective and surjective, hence bijective.
Definition 0.1.26. Function composition.
Suppose \(f\colon Z\rightarrow W\) and \(g\colon X\rightarrow Y\) are functions satisfying \(Y\subseteq Z\text{.}\) The composition of \(f\) and \(g\) is the function \(f\circ g\colon X\rightarrow W\) defined as \(f\circ g\, (x)=f(g(x))
\text{,}\) for all \(x\in X\text{.}\)
Definition 0.1.27. Identity and inverse functions.
For any set \(X\) the identity function on \(X\) is the function \(\id_X\colon X\rightarrow X\) defined as \(\id_X(x)=x\) for all \(x\in X\text{.}\)
A function \(f\colon X\rightarrow Y\) is invertible if there is a function \(g\colon Y\rightarrow X\) satisfying \(g\circ f=\id_X\) and \(f\circ g=\id_Y\text{:}\) i.e.,
\begin{align*}
g(f(x))\amp =x \text{ for all } x\in X, \\
f(g(y))\amp=y \text{ for all } y\in Y \text{.}
\end{align*}
The function \(g\) in this case is called the inverse of \(f\text{,}\) denoted \(g=f^{-1}\text{.}\)
Theorem 0.1.28. Invertible is equivalent to bijective.
A function \(f\colon X\rightarrow Y\) is invertible if and only if it is bijective.
