Sets and functions

Section 0.1 Sets and functions

We gather here some notions about sets and functions.

Subsection 0.1.1 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.

🔗

Remark 0.1.4.

The definitions of set equality and the subset relation make use of two important logical operations: namely, the “if and only if” (or “iff” for short) and “if-then” operations.

🔗

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*}

🔗

Remark 0.1.6.

Set builder notation ‘\(\{x \in A\colon P(x)\}\)’ is parsed from left to right as follows:

‘\(\{\)’ is read as “the set of”
🔗

🔗
‘\(x\in A\)’ is read as “elements of \(A\)”
🔗

🔗
‘\(\colon\)’ is read as “such that”
🔗

🔗
‘\(P(x)\)’ is read as “\(P(x)\) is true”.
🔗

🔗

Taken altogether we get: “The set of elements of \(A\) such that \(P(x)\) is true”.

🔗

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{.}\)

Set union.

The union \(A \cup B\) of \(A\) and \(B\) is defined as

\begin{equation*} A\cup B=\{x\in X\colon x\in A\text{ or } x\in B\}\text{.} \end{equation*}

More generally, if \(\{A_i\colon i\in I\}\) is any collection of subsets \(A_i\subseteq X\) indexed by an arbitrary set \(I\text{,}\) then the union \(\bigcup_{i\in I}A_i\) of this collection is defined as

\begin{equation*} \bigcup_{i\in I}A_i=\{x\in X\colon x\in A_i \text{ for some } i\in I\}\text{.} \end{equation*}

🔗

🔗
Set intersection.

The intersection \(A \cap B\) of \(A\) and \(B\) is defined as

\begin{equation*} A\cap B=\{x\in X\colon x\in A\text{ and } x\in B\}\text{.} \end{equation*}

More generally, if \(\{A_i\colon i\in I\}\) is any collection of subsets \(A_i\subseteq X\) indexed by an arbitrary set \(I\text{,}\) then the intersection \(\bigcap_{i\in I}A_i\) of this collection is defined as

\begin{equation*} \bigcap_{i\in I}A_i=\{x\in X\colon x\in A_i \text{ for all } 1\leq i\leq n\}. \end{equation*}

🔗

🔗
Set difference.

The difference \(A-B\) is defined as

\begin{equation*} A-B=\{x\in X\colon x\in A\text{ and } x\notin B\}\text{.} \end{equation*}

🔗

🔗
Set complement.
The complement of \(A\) in \(X\) is defined as \(X-A\text{.}\) In contexts where there is clear what the larger set \(X\) is, we denote the complement of \(A\) in \(X\) as \(A^c\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.

The empty set is the set containing no objects, denoted \(\{\ \}\) or \(\emptyset\text{.}\)

🔗

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}

Additionally, for any integer \(a\in \Z\) we denote by \(\Z_{\geq a}\) the set of all integers \(n\geq a\text{:}\) i.e.,

\begin{equation} \Z_{\geq a}=\{n\in \Z\colon n\geq a\}=\{a,a+1,a+2,\dots, \}\text{.}\tag{0.1.2} \end{equation}

Lastly, we denote by \(\Z_+\) the set of all positive integers: i.e.,

\begin{equation*} \Z_+=\{n\in \Z\colon n\geq 0\}=\{1,2,\dots, \}\text{.} \end{equation*}

🔗

The power set of a set \(A\) is the set of all subsets of \(A\text{.}\)

🔗

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{.}\)

🔗

Subsection 0.1.2 Functions

Definition 0.1.12. 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.13.

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.14. 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*}

🔗

Remark 0.1.15.

Invoking the notion of a rule in the definition of a function is admittedly somewhat vague. A more precise definition can be given using the Cartesian product. Namely, given sets \(X\) and \(Y\text{,}\) we define a function \(f\colon X\rightarrow Y\) to be a subset \(f\subseteq X\times Y\) satisfying the following property: for all \(x\in X\) there is a unique element \((x,y)\in f\text{.}\) The uniqueness of the pair \((x,y)\) then allows us to define the value \(f(x)\) of \(f\) at \(x\) as \(y\text{,}\) denoted \(f(x)=y\text{.}\)

🔗

As with sets, 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.16. 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.17. 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.18. 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.19. 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.20. 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.21. 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.22. 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.23. Invertible is equivalent to bijective.

A function \(f\colon X\rightarrow Y\) is invertible if and only if it is bijective.

🔗

Subsection 0.1.3 Tuples and Cartesian product

Next we introduce the notion of a tuple, which will both provide a rigorous foundation for the notion of an ordered sequence (or list), and vastly generalize that notion. Interestingly, as revealed in the next definition, a tuple is just a function by another name.

🔗

Definition 0.1.24. Tuple.

Let \(I\) and \(X\) be sets. An \(X\)-valued tuple indexed by \(I\) is a function \(f\colon I\rightarrow X \text{.}\) We call \(I\) the indexing set of the tuple \(f\text{,}\) and for all \(i\in I\text{,}\) we call \(f(i)\) the \(i\)-th entry (or coordinate) of \(f\text{.}\) Furthermore, we will write \(f=(x_i)_{i\in I}\) to denote the function \(f\colon I\rightarrow X\) defined as \(f(i)=x_i\) for all \(i\in I\text{.}\)

🔗

Remark 0.1.25. Tuple versus function.

As mentioned above, the introduction of tuple language and notation simply gives us another way of conceptualizing a function \(f\colon I\rightarrow X\text{:}\) one that let’s us think of a function as a sort of sequence. Being able to fluently move between these two conceptions requires a little bit of practice. The following correspondence diagram can help in this regard:

🔗

Figure 0.1.26. Correspondence between functions and tuples
🔗

🔗

Remark 0.1.27. Tuple equality.

Fix a set \(X\text{,}\) and let \(f=(x_i)_{i\in I}\) and \(g=(y_i)_{j\in J}\) be two tuples with entries in \(X\text{.}\) When are these tuples equal? The answer is provided by our definition of function equality. By definition, the functions \(f\colon I\rightarrow X\) and \(g\colon J\rightarrow X\) are equal if and only if (i) \(I=J\) (the indexing sets are equal), and (ii) \(f(i)=g(i)\) for all \(i\in I\text{.}\) In terms of our tuple notation this means \((x_i)_{i\in I}=(y_i)_{i\in I}\) if and only if \(x_i=y_i\) for all \(i\in I\text{:}\) i.e., two tuples with the same indexing set \(I\) are equal if and only if their \(i\)-th coordinate is equal for all \(i\in I\text{.}\) Sound familiar? This is precisely how we define equality between two finite (ordered)sequences \((x_1,x_2,\dots, x_n)\) and \((y_1,y_2,\dots, y_n)\text{.}\) We make this observation more official in the next definition.

🔗

Definition 0.1.28. \(n\)-tuples.

Let \(X\) be a set. An \(n\)-tuple (or sequence of length \(n\)) with entries in \(A\) is a tuple

\begin{equation*} f\colon \{1,2,\dots, n\}\rightarrow A \end{equation*}

indexed by the set \(I=\{1,2,\dots, n\}\text{.}\) We write \(f=(x_i)_{i=1}^n\) or \(f=(x_1,x_2,\dots, x_n)\) to denote the \(n\)-tuple \(f\) whose \(i\)-th entry is \(f(i)=x_i\) for all \(1\leq i\leq n\text{.}\)

🔗

Remark 0.1.29.

We have more suggestive names for \(n\)-tuples when \(n\) is small: a 2-tuple \((a,b)\) is called a pair, a 3-tuple \((a,b,c)\) is called a triple, a 4-tuple \((a,b,c,d)\) is called a quadruple, etc.. We will use the generic term “tuple” to designate a \(n\)-tuple of unspecified length.

🔗

Remark 0.1.30.

Observe how tuples capture the notion of an ordered collection of object. For example, whereas the sets \(\{1, 1, 2, 3\}\) and \(\{1,2,2,3\}\) are all equal to one another, the 4-tuples \((1,1,2,3)\) and \((1,2,2,3)\) are not: they differ in their second entries.

🔗

The last definition indicates how our notion of tuple generalizes that of a finite sequence. As the next example illustrates, infinite sequences can also be considered as simply a particular type of tuple: one with indexing set \(\Z_{\geq a}=\{a,a+1,\dots\}\text{.}\)

🔗

Definition 0.1.31. Infinite sequence.

Let \(X\) be a set. An infinite sequence with entries in \(X\) is a tuple of the form

\begin{equation*} f\colon \Z_{\geq a}\rightarrow A\text{,} \end{equation*}

for some \(a\in \Z\text{.}\) We write \(f=(x_i)_{i=a}^\infty\) or \(f=(x_a,x_{a+1},\dots)\) to denote the tuple \(f\colon \Z_{\geq a}\rightarrow A\) whose \(i\)-th entry is \(f(i)=x_i\) for all \(i\in \Z_{\geq a}\text{.}\)

🔗

Remark 0.1.32. Indexed collection of sets.

In mathematics we often deal with indexed collections of sets: that is, a collection of sets \(A_i\) indexed by some set \(I\text{.}\) When all of the sets \(A_i\) are subsets of a common set \(X\text{,}\) we can make this notion rigorous with the concept of a tuple: namely, a collection of subsets of \(X\) indexed by \(I\) is just a tuple \(f=(A_i)_{i\in I}\text{,}\) where each \(A_i=f(i)\) is a subset of \(X\text{.}\) More technically, this is just a function

\begin{equation*} f\colon I\rightarrow \mathcal{P}(X) \end{equation*}

from \(I\) to the power set of \(X\text{.}\)

🔗

Definition 0.1.33. Cartesian product.

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 \(X\)-valued tuples whose \(i\)-th coordinate is an element of \(A_i\) for all \(i\in I\text{.}\)

🔗

When \(A_i=A\) for all \(i\in I\text{,}\) we denote \(\prod_{i\in I}A\) as \(A^I\text{.}\)

🔗

Additionally, in the special case where \(I=\{1,2,\dots, n\}\) we write

\begin{align*} \prod_{i\in \{1,2,\dots, n\}}A_i \amp =A_1\times A_2\times \cdots A_n \amp \\ \amp = \{(a_1,a_2,\dots, a_n)\colon a_i\in A_i \text{ for all } 1\leq i\leq n\} \end{align*}

and

\begin{equation*} A^{\{1,2,\dots, n\}}=A^n\text{,} \end{equation*}

and we call \(A^n\) the \(n\)-fold Cartesian product of \(A\).

🔗

Lastly, in the special case where \(I=\Z_{+}=\{1,2,\dots\}\) we write

\begin{align*} \prod_{i\in \Z_{+}}A_n \amp=A_1\times A_2\times \cdots \amp \\ \amp = \{(a_i)_{i=1}^\infty\colon a_i\in A_i \text{ for all } i\in \Z_+\} \end{align*}

and

\begin{equation*} A^{\Z_+}=A^\infty\text{.} \end{equation*}

🔗

Subsection 0.1.4 Cardinality and countability

Definition 0.1.34. Cardinality.

Let \(X\) be a set.

Finite and infinite sets.
The set \(X\) is finite if either \(X=\emptyset\) or there is a bijection \(f\colon X\rightarrow \{1,2,\dots, n\}\) for some positive integer \(n\text{.}\) Roughly speaking, the cardinality of a finite set \(X\text{,}\) denoted \(\abs{X}\text{,}\) is the number of distinct elements it contains. In more detail if \(X=\emptyset\text{,}\) then \(\abs{X}=0\) by definition; if there is a bijection \(f\colon X\rightarrow \{1,2,\dots, n\}\text{,}\) then \(\abs{X}=n\text{.}\)
🔗

The set \(X\) is infinite if it is not finite. In this case \(X\) is said to have infinite cardinality.
🔗

🔗
Countable and uncountable sets.
The set \(X\) is countably infinite if there is a bijection \(f\colon X\rightarrow \Z_{+}\text{,}\) where \(\Z_+=\{1,2,\dots, \}\) is the set of all positive integers; it is countable if it is either finite or countable infinite.
🔗

The set \(X\) is uncountable if it is not countable.
🔗

🔗

🔗

Prev Top Next