Sets and functions

Section 1.1 Sets and functions

We will gradually make our way to definitions of the vector spaces and linear transformations mentioned in this text's title. For now it will suffice to observe that a vector space is a certain kind of set, and a linear transformation is a special type of function. Accordingly we gather here some notions about sets and functions that will come in handy once we meet the two main players of linear algebra.

Subsection 1.1.1 Sets

Definition 1.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 1.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 1.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 1.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. We describe these notions in more detail in Logic, and we outline techniques for proving “if and only if” and “if-then” statements, including statements about set equality and the subset relation, in Proof techniques.

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 1.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 1.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 1.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 1.1.8. Basic set operations.

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, the union \(A_1\cup A_2\dots \cup A_n\) of a collection of subsets of \(A_i\subseteq X\) is defined as

\begin{equation*} A_1\cup A_2\dots \cup A_n=\{x\in X\colon x\in A_i \text{ for some } 1\leq i\leq n\}. \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, the intersection \(A_1\cap A_2\dots \cap A_n\) of a collection of subsets of \(A_i\subseteq X\) is defined as

\begin{equation*} A_1\cap A_2\dots \cap A_n=\{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*}

With the help of these set operations, we can now describe some common sets used in mathematics.

Definition 1.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*}

The complex numbers \(\mathbb{C}\) are defined as the set of all formal expressions of the form \(a+bi\text{,}\) where \(a,b\in\mathbb{R}\text{.}\) Identifying a real number \(a\) with the complex number \(a+0i\text{,}\) we have the following chain of subsets:

\begin{equation*} \mathbb{Z}\subseteq\mathbb{Q}\subseteq\mathbb{R}\subseteq\mathbb{C}\text{.} \end{equation*}

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

Lastly, we define the cartesian product of sets, which is a formal description of an ordered collection of objects.

Definition 1.1.10. Cartesian product.

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

Remark 1.1.11.

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 1.1.12.

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.

What about the tuples \((1,1,1)\) and \((1,1,1,1)\text{?}\) Are these equal? Technically our definition of equality only applies to tuples living in the same fixed Cartesian product. In particular, for the question of equality to make sense, the tuples must have the same length. As such we will officially avoid writing things like \((1,1,1)\ne (1,1,1,1)\text{,}\) although unofficially we consider these two objects as completely different. You should think of \((1,1,1)\) and \((1,1,1,1)\) as creatures living on two different planets in the universe of tuples.

Subsection 1.1.2 Functions

Definition 1.1.13. 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 1.1.14.

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 1.1.15. 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 1.1.16.

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 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 1.1.17. 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 1.1.18. 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 1.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 1.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 1.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 1.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 1.1.23. Invertible is equivalent to bijective.

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

Proof.

The proof of this theorem is left as an example of proving “if and only if” statements. See Example 1.3.3.