# 13.1: The Language of Sets and Functions

- Page ID
- 242

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)All of mathematics can be seen as the study of relations between collections of objects by rigorous rational arguments. More often than not the patterns in those collections and their relations are more important than the nature of the objects themselves. The power of mathematics has a lot to do with bringing patterns to the forefront and abstracting from the “real” nature if the objects. In mathematics, the collections are usually called sets and the objects are called the elements of the set. Functions are the most common type of relation between sets and their elements and the primary objects of study in Analysis are functions having to do with the set of real numbers. It is therefore important to develop a good understanding of sets and functions and to know the vocabulary used to deﬁne sets and functions and to discuss their properties.

# B.1 Sets

A set is an unordered collection of distinct objects, which we call its elements. \(A\) set is uniquely determined by its elements. If an object a is an element of a set \(A\), we write \(a \in A\), and say that a belongs to \(A\) or that \(A\) contains a. The negation of this statement is written as \(a \not\in A\), i.e., a is not an element of \(A.\) Note that both statements cannot be true at the same time

If \(A\) and \(B\) are sets, they are identical (this means one and the same set), which we write as \(A = B\), if they have exactly the same elements. In other words \(A = B\) if and only if forall \(a \in A\) we have \(a \in B\), and for all \(b \in B\) we have \(b \in A.\) Equivalently, \(A \neq B\) if and only if there is a diﬀerence in their elements: there exists \(a \in A\) such that \(a \not\in B\) or there exists \(b \in B\) such that \(b \not\in A.\)

**Example B.1.1.** We start with the simplest examples of sets.

- The
**empty set**(a.k.a. the**null set**), is what it sounds like: the set with no elements. We usually denote it by \(\emptyset\) or sometimes by \(\{~\}\). The empty set, \(\emptyset\), is uniquely determined by the property that for all \(x\) we have \(x \not\in \emptyset\). Clearly, there is exactly one empty set. - Next up are the
**singletons**. A singleton is a set with exactly one element. If that element is \(x\) we often write the singleton containing \(x\) as \(\{x\}\). In spoken language, ‘the singleton \(x\)’ actually means the set \(\{x\}\) and should always be distinguished from the element \(x: x \neq \) {\(x\)}. A set can be an element of another set but no set is an element of itself (more precisely, we adopt this as an axiom). E.g., \(\{\{x\}\}\) is the singleton of which the unique element is the singleton \(\{x\}\). In particular we also have \(\{x\} \neq \{\{x\}\}.\) - One standard way of denoting sets is by listing its elements. E.g., the set \(\{\alpha, \beta, \gamma\}\) contains the ﬁrst three lower case Greek letters. The set is completely determined by what is in the list. The order in which the elements are listed is irrelevant. So, we have \(\{\alpha, \gamma, \beta\} = \{\gamma, \beta, \alpha\} = \{\alpha, \beta, \gamma\},\) etc. Since a set cannot contain the same element twice (elements are distinct) the only reasonable meaning of something like \(\{ \alpha, \beta, \alpha, \gamma\}\) is that it is the same as \(\{\alpha, \beta, \gamma\}\). Since \(x \neq \{x\}, \{x, \{x\}\}\) is a set with two elements. Anything can be considered as an element of a set and there is not any kind of relation is required of the elements in a set. E.g., the word ‘apple’ and the element uranium and the planet Pluto can be the three elements of a set. There is no restriction on the number of diﬀerent sets a given element can belong to, except for the rule that a set cannot be an element of itself.
- The number of elements in a set may be inﬁnite. E.g., \(\mathbb{Z}, \mathbb{R},\) and \(\mathbb{C}\), denote the sets of all integer, real, and complex numbers, respectively. It is not required that we can list all elements.

When introducing a new set (new for the purpose of the discussion at hand) it is crucial to deﬁne it unambiguously. It is not required that from a given deﬁnition of a set \(A\), it is easy to determine what the elements of \(A\) are, or even how many there are, but it should be clear that, in principle, there is unique and unambiguous answer to each question of the form “is \(x\) an element of \(A\)?”. There are several common ways to deﬁne sets. Here are a few examples.

**Example B.1.2.**

1. The simplest way is a generalization of the list notation to inﬁnite lists that can be described by a pattern. E.g., the set of positive integers \(\mathbb{N} = \{1, 2, 3, \ldots \}.\) The list can be allowed to be bi-directional, as in the set of all integers \(\mathbb{Z} = \{\ldots , -2, -1, 0, 1, 2, \ldots \}.\)

Note the use of triple dots \(\ldots\) to indicate the continuation of the list.

2. The so-called set builder notation gives more options to describe the membership of a set. E.g., the set of all even integers, often denote by \(2 \mathbb{Z}\), is deﬁned by

\[2\mathbb{Z} = \{2a ~|~ a \in \mathbb{Z}\} .\]

Instead of the vertical bar, |, a colon, :, is also commonly used. For example, the open interval of the real numbers strictly between \(0\) and \(1\) is deﬁned by

\[(0, 1) = \{x \in \mathbb{R} : 0 < x < 1\}.\]

# B.2 Subset, union, intersection, and Cartesian product

**Deﬁnition B.2.1.** Let \(A\) and \(B\) be sets. \(B\) is a subset of \(A\), denoted by \(B \subset A\), if and only if for all \(b \in B\) we have \(b \in A.\) If \(B \subset A\) and \(B \neq A,\) we say that \(B\) is a** proper subset **of \(A.\)

If \(B \subset A\), one also says that \(B\) is contained in \(A\), or that \(A\) contains \(B\), which is sometimes denoted by \(A \supset B.\) The relation \(\subset\) is called** inclusion**. If \(B\) is a proper subset of \(A\) the inclusion is said to be strict. To emphasize that an inclusion is not necessarily strict, the notation \(B \subseteq A\) can be used but note that its mathematical meaning is identical to \(B \subset A.\) Strict inclusion is sometimes denoted by \(B \subsetneq A\), but this is less common.

**Example B.2.2.** The following relations between sets are easy to verify:

- We have \(\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}\), and all these inclusions are strict.
- For any set \(A\), we have \( \emptyset \subset A\), and \(A \subset A.\)
- \((0, 1] \subset (0, 2).\)
- For \(0 < a \leq b, [-a, a] \subset [-b, b].\) The inclusion is strict if \(a < b.\)

In addition to constructing sets directly, sets can also be obtained from other sets by a number of standard operations. The following deﬁnition introduces the basic operations of taken the **union**,** intersection**, and **diﬀerence** of sets.

**Deﬁnition B.2.3**. Let \(A\) and \(B\) be sets. Then

- The
**union**of \(A\) and \(B\), denoted by \(A \cup B\), is deﬁned by \[A \cup B = \{x ~|~ x \in A {\it{~or~}} x \in B\}.\] - The
**intersection**of \(A\) and \(B\), denoted by \(A \cap B\), is deﬁned by \[A \cap B = \{x~ |~ x \in A {\it{~and~}} x \in B\}.\] - The set
**diﬀerence**of \(B\) from \(A\), denoted by \(A \setminus B\), is deﬁned by \[A \setminus B = \{x ~|~ x \in A {\it{~and~}} x \not\in B\}.\]

Often, the context provides a ‘universe’ of all possible elements pertinent to a given discussion. Suppose, we have given such a set of ‘all’ elements and let us call it \(U\). Then, the **complement** of a set \(A\), denoted by \(A^c\) , is deﬁned as \(A^c = U \setminus A.\) In the following theorem the existence of a universe \(U\) is tacitly assumed.

**Theorem B.2.4.** *Let* \(A, B,\) *and* \(C\) *be sets. Then*

- (
*distributivity*) \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)*and*\(A \cup (B \cap C) = (A \cup B) \cap (A \cup C).\) - (
*De Morgan’s Laws*) \((A \cup B)^c = A^c \cap B^c\)*and*\((A \cap B)^c = A^c \cup B^c .\) - (
*relative complements*) \(A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\)*and*\(A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C).\)

To familiarize your self with the basic properties of sets and the basic operations if sets, it is a good exercise to write proofs for the three properties stated in the theorem.

The so-called **Cartesian product** of sets is a powerful and ubiquitous method to construct new sets out of old ones.

**Deﬁnition B.2.5**. Let \(A\) and \(B\) be sets. Then the **Cartesian product** of \(A\) and \(B\), denoted by \(A \times B\), is the set of all ordered pairs \((a, b),\) with \(a \in A\) and \(b \in B.\) In other words,

\[A \times B = \{(a, b) ~|~ a \in A, b \in B\} .\]

An important example of this construction is the Euclidean plane \(\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}\). It is not an accident that \(x\) and \(y\) in the pair \((x, y)\) are called the *Cartesian* coordinates of the point \((x, y)\) in the plane.

# B.3 Relations

In this section we introduce two important types of relations: order relations and equivalence relations. A **relation** \(R\) between elements of a set \(A\) and elements of a set \(B\) is a subset of their Cartesian product: \(R \subset A \times B.\) When \(A = B\), we also call \(R\) simply a relation on \(A\).

Let \(A\) be a set and \(R\) a relation on \(A\). Then,

- \(R\) is called
**reﬂexive**if for all \(a \in A, (a, a) \in R.\) - \(R\) is called
**symmetric**if for all \(a, b \in A,\) if \((a, b) \in R\) then \((b, a) \in R.\) - \(R\) is called
**antisymmetric**if for all \(a, b \in A\) such that \((a, b) \in R\) and \((b, a) \in R, a = b.\) - \(R\) is called
**transitive**if for all \(a, b, c \in A\) such \((a, b) \in R\) and \((b, c) \in R\), we have \((a, c) \in R.\)

**Deﬁnition B.3.1.** Let \(R\) be a relation on a set \(A\). \(R\) is an **order relation** if \(R\) is *reﬂexive, antisymmetric, and transitive*. \(R\) is an equivalence relation if \(R\) is *reﬂexive, symmetric, and transitive.*

The notion of subset is an example of an order relation. To see this, ﬁrst deﬁne the** power set** of a set \(A\) as the set of all its subsets. It is often denoted by \({\cal{P}}(A).\) So, for any set \(A, {\cal{P}}(A) = \{B : B \subset A\}.\) The, the inclusion relation is deﬁned as the relation \(R\) by setting

\[R = \{(B, C) \in {\cal{P}}(A) \times {\cal{P}}(A)~ |~ B \subset C\}\]

Important relations, such as the subset relation, are given a convenient notation of the form \(a <symbol> b\), to denote \((a, b) \in R.\) The symbol for the inclusion relation is \(\subset\).

**Proposition B.3.2.** *Inclusion is an order relation. Explicitly,*

- (
*reﬂexive*)*For all*\(B \in {\cal{P}}(A), B \subset B.\) - (
*antisymmetric*)*For all*\(B, C \in {\cal{P}}(A),\)*if*\(B \subset C\)*and*\(C \subset B\),*then*\(B = C.\) - (
*transitive*)*For all*\(B, C, D \in {\cal{P}}(A),\)*if*\(B \subset C\)*and*\(C \subset D,\)*then*\(B \subset D.\)

Write a proof of this proposition as an exercise.

For any relation \(R \subset A \times B\), the **inverse relation**, \(R^{-1} \subset B \times A\), is deﬁned by

\[R^{-1} = \{(b, a) \in B \times A ~| ~(a, b) \in R\}.\]

# B.4 Functions

Let \(A\) and \(B\) be sets. A **function** with **domain** \(A\) and **codomain** \(B\), denoted by \(f : A \rightarrow B\), is relation between the elements of \(A\) and \(B\) satisfying the properties: for all \(a \in A,\) there is a unique \(b \in B\) such that \((a, b) \in f \). The symbol used to denote a function as a relation is an arrow: \((a, b) \in f\) is written as \(a \rightarrow b\) (often also \(a \mapsto b\)). It is not necessary, and a bit cumbersome, to remind ourselves that functions are a special kind of relation and a more convenient notation is used all the time: \(f (a) = b.\) If \(f\) is a function we then have, by deﬁnition, \(f (a) = b\) and \(f (a) = c\) implies \(b = c\). In other words, for each \(a \in A\), there is exactly one \(b \in B\) such that \(f (a) = b.\) \(b\) is called the** image** of a under \(f\) . When \(A\) and \(B\) are sets of numbers, \(a\) is sometimes referred to as the **argument** of the function and \(b = f (a)\) is often referred to as the **value** of \(f\) in \(a\).

The requirement that there is an image \(b \in B\) for all \(a \in A\) is sometimes relaxed in the sense that the domain of the function is a, sometimes not explicitly speciﬁed, subset of \(A\). It important to remember, however, that a function is not properly deﬁned unless we have also given its domain.

When we consider the **graph** of a function, we are relying on the deﬁnition of a function as a relation. The graph \(G\) of a function \(f : A \rightarrow B\) is the subset of \(A \times B\) deﬁned by

\[G = \{(a, f (a)) ~|~ a \in A\}.\]

The **range** of a function \(f : A \rightarrow B\), denoted by \(range (f ),\) or also \(f (A),\) is the subset of its codomain consisting of all \(b \in B\) that are the image of some \(a \in A:\)

\[range (f ) = \{b \in B ~|~ {\rm{~there ~exists~}} a \in A {\rm{~such ~that~}} f (a) = b\}.\]

The **pre-image** of \(b \in B\) is the subset of all \(a \in A\) that have \(b\) as their image. This subset if often denoted by \(f^{-1} (b).\)

\[f^{-1} (b) = \{a \in A ~|~ f (a) = b\}.\]

Note that \(f^{-1} (b) = \emptyset\) if and only if \(b \in B \setminus range (f ).\)

Functions of various kinds are ubiquitous in mathematics and a large vocabulary has developed, some of which is redundant. The term *map* is often used as an alternative for function and when the domain and codomain coincide the term *transformation* is often used instead of function. There is large number of terms for functions in particular context with special properties. The three most basic properties are given in the following deﬁnition.

**Deﬁnition B.4.1.** Let \(f : A \rightarrow B\) be a function. Then we call \(f\)

**injective**(\(f\) is an**injection**) if \(f (a) = f (b)\) implies \(a = b\). In other words, no two elements of the domain have the same image. An injective function is also called**one-to-one**.**surjective**(\(f\) is a**surjection**) if \(range (f ) = B.\) In other words, each \(b \in B\) is the image of at least one \(a \in A\). Such a function is also called**onto**.**bijective**(\(f\) is a**bijection**) if \(f\) is both injective and surjective, i.e.,**one-to-one and onto**. This means that f gives a one-to-one correspondence between all elements of \(A\) and all elements of \(B\).

Let \(f : A \rightarrow B\) and \(g : B \rightarrow C\) be two functions so that the codomain of \(f\) coincides with the domain of \(g\). Then, the **composition** ‘\(g\) after \(f\) ’, denoted by \(g \circ f\) , is the function \(g \circ f : A \rightarrow C,\) deﬁned by \(a \mapsto g(f (a)).\)

For every set \(A\), we deﬁne the **identity map**, which we will denote here by \({\rm{id}}_A\) or \({\rm{id}}\) for short. \({\rm{id}}_A : A \rightarrow A\) is deﬁned by \({\rm{id}}_A (a) = a\) for all \(a \in A\). Clearly, \({\rm{id}}_A\) is a bijection.

If \(f\) is a bijection, it is invertible, i.e., the inverse relation is also a function, denoted by \(f^{ -1} \). It is the unique bijection \(B \rightarrow A\) such that \(f^{-1} \circ f = {\rm{id}}_A\)

and \(f \circ f^{-1 }= {\rm{id}}_B\) .**Proposition B.4.2.** *Let* \(f : A \rightarrow B\) *and* \(g : B \rightarrow C\) *be bijections. Then, their composition* \(g \circ f\) *is a bijection and*

\[(g \circ f )^{-1} = f^{ -1} \circ g^{ -1} .\]

Prove this proposition as an exercise.

## Contributors

- Isaiah Lankham, Mathematics Department at UC Davis
- Bruno Nachtergaele, Mathematics Department at UC Davis
- Anne Schilling, Mathematics Department at UC Davis

Both hardbound and softbound versions of this textbook are available online at WorldScientific.com.