Appendix - Set Theory

A review of a few basic ideas from set theory is provided here. Set theory forms the foundation for almost all of modern mathematics. Indeed, one can say that modern mathematics is the study of sets. We will not make any attempts to define rigorously the notion of a set. Certain elementary definitions are provided here for convenient reference. More definitions will be introduced later on as and when they are required.

Describing a set

Loosely speaking, a set is a collection of elements. These elements are said to belong to the set. Given a set $S$, the statement that an element $a$ belongs to $S$ is abbreviated as $$a \in S.$$ The negation of this statement, that $a$ does not belong to $S$, is written as $$a \notin S.$$ The set consisting of $n$ elements $a_1, a_2, \ldots, a_n$ is written as $$\{a_1,a_2,\ldots,a_n\}.$$

Example

Let us collect together the list $C$ of India’s Twenty20 cricket captains so far (as of 2019): $$C = \{\text{Sehwag}, \text{Dhoni}, \text{Raina}, \text{Rahane}, \text{Kohli}, \text{Sharma}\}.$$ (I have listed only the last names since the full names would make the list too long.) We denote the fact that $\text{Dhoni}$ was a captain of the Indian Twenty20 cricket team as $$\text{Dhoni} \in C.$$ Similarly, we denote the fact that $\text{Tendulkar}$ was not a captain of the Indian Twenty20 cricket team using the notation $$\text{Tendulkar} \notin C.$$ Notice how the set-theoretic notation $\text{Tendulkar} \notin C$ succinctly represents the more verbose statement ‘Tendulkar was not a captain of the Indian Twenty20 cricket team’.

Remark

Whenever you see a mathematical expression, keep in mind that it just summarizes a possibly long, or, complex idea - it is a good idea to read it out fully until you gain enough intuition to think abstractly.

A more powerful notation to represent a set is as follows. Suppose we are given a property $P(a)$ that any element $a$ belonging to a set $S$ may, or may not, satisfy. The set of all elements in $S$ that satisfy the property $P$ is written as $$\{a \in S \,|\, P(a)\}.$$ The above statement is read ‘the set of all $a$ in $S$ for which $P(a)$ is true’.

Example

Continuing the earlier example involving the set $C$ of all Indian Twenty20 cricket team (as of 2019), notice that only $\text{Rahane}$ and $\text{Sharma}$ represented Mumbai, in the domestic matches. Using the notation just introduced, we see that the set $$\{\text{Rahane}, \text{Sharma}\}$$ consisting of just those Indian Twenty20 captains until 2019 who played for Mumbai as $$\{A \in C \,|\, A\text{ played for Mumbai}\}.$$

It is helpful to postulate the existence of a special set called the empty set that contains nothing. The standard notation for the empty set is $\emptyset$.

Example

Returning to the set $C$ of all Indian Twenty20 captains, it turns out that none of them were born in Mumbai. In set-theoretic notation, we write this as $$\{A \in C \,|\, A\text{ was born in Mumbai}\} = \emptyset.$$

Finally, we will always work within the confines of a universal set, which contains everything that we are dealing with in a particular context.

Example

In all the earlier examples involving the set $C$ of all Indian Twenty20 captains, a convenient choice of universal set is the set $P$ of all cricketers who represented India at the international level in cricket matches: $$P = \{\text{Indians who played for India in at least one international cricket match}\}.$$ Note that the set $C$ can be obtained from $P$ as follows: $$C = \{A \in P \,|\, A\text{ captained India in a Twenty20 match}\}.$$

Remark

Note that the choice of universal set is not unique. In the examples considered above, we might just as well have chosen the set $I$ of all Indians who were born, say, after 1900, as our universal set. In practice, the universal set is often implicitly understood from the context; it is always a good idea to be aware of it.

Numerical sets

While set theory is very broad in its purview, we will limit our discussion henceforth to studying the properties of special kinds of sets. In particular, we will find the following numerical sets to be very useful:

• The set of all natural numbers: $\mathbb{N} = \{1, 2, 3, \ldots \}$.

• The set of all integers: $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$.

• The set of all rational numbers, which are numbers of the form $p/q$ where $p \in \mathbb{Z}$ and $q \in \mathbb{N}$, will be denoted by the symbol $\mathbb{Q}$.

• Finally, the set of all real numbers will be denoted by the symbol $\mathbb{R}$.

We will sometimes use the symbol $\mathbb{R}_+$ to denote the set of non-negative real numbers: $\mathbb{R}_+ = \{a \in \mathbb{R} \,|\, a \ge 0\}$.

Remark

In the modern mathematical formalism, all the numerical sets introduced above are constructed from the empty set $\emptyset$. Understanding how this is done is beyond the scope of these notes. Any good book on real analysis should, however, provide the necessary details.

All the discussions henceforth will be confined to numerical sets, or sets constructed from numerical sets, unless stated otherwise.

Subsets, inclusion and equality

A set $S$ is said to be a subset of another set $T$, written $S \subseteq T$, if, and only if, it is true that whenever $a \in S$, it is also the case that $a \in T$. Formally, $$S \subseteq T \,\Leftrightarrow\, a\in S \Rightarrow a \in T.$$

Remark

We will use a variety of logical qualifiers in these notes. The symbol $\forall$ stands for the logical qualifier for all. We also use the logical qualifiers $\exists$ and $\exists!$ to represent the notions there exists, and there exists a unique, respectively. The symbol $\Rightarrow$ stands for implication. Thus, $a \Rightarrow b$ is read $b$ if $a$, or $a$ only if $b$. Finally, the symbol $\Leftrightarrow$ stands for equivalence. Thus, $a \Leftrightarrow b$ is read $a$ if, and only if, $b$. We will henceforth abbreviate the phrase if, and only if as iff.

Example

We will use the following subsets of $\mathbb{R}$ to be very useful: for any $a,b \in \mathbb{R}$, $$\begin{split} (a,b) &= \{x \in \mathbb{R}\,|\, a < x < b\},\\ (a,b] &= \{x \in \mathbb{R}\,|\, a < x \le b\},\\ [a,b) &= \{x \in \mathbb{R}\,|\, a \le x < b\},\\ [a,b] &= \{x \in \mathbb{R}\,|\, a \le x \le b\},\\ (a,\infty) &= \{x \in \mathbb{R}\,|\, x > a\},\\ [a,\infty) &= \{x \in \mathbb{R}\,|\, x \ge a\},\\ (\infty,a) &= \{x \in \mathbb{R}\,|\, x < a\},\\ (\infty,a] &= \{x \in \mathbb{R}\,|\, x \le a\}. \end{split}$$

The phrase $S$ is contained in $T$ is also used for $S \subseteq T$. This can alternatively be stated as, $T \supseteq S$, and we say that $T$ is a superset of $S$, or that $T$ contains $S$. $S$ is said to be a strict subset of $T$, written $S \subsetneq T$, if $S$ is a subset of $T$, and there exists an element $a \in T$ such that $a \notin S$. Formally, $$S \subsetneq T \,\Leftrightarrow\, S \subseteq T, \text{ and } \exists\, a \in T \text{ such that } a \notin S.$$

Example

Note that the following inclusion relation holds among the numerical sets introduced earlier: $$\emptyset \subseteq \mathbb{N} \subseteq \mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}.$$

Finally, two sets $S$ and $T$ are said to be equal, written $S = T$, if both $S \subseteq T$ and $T \subseteq S$. In other words, every element in $S$ belongs to $T$, and vice versa. Formally, $$S = T \,\Leftrightarrow\, S \subseteq T \text{ and } T \subseteq S \,\Leftrightarrow\, (a \in S \Leftrightarrow a \in T).$$ This is an important strategy to prove the equality of two sets.

Example

Let us consider the two sets $$S = [-1,1] \subseteq \mathbb{R},$$ and $$T = \{ \sin x \,|\, x \in \mathbb{R} \} \subseteq \mathbb{R}$$ For any $y \in S$, note that it is possible to find a unique $x \in [-\pi/2,\pi/2]$ such that $y = \sin x \in T$. Thus, we see that $S \subseteq T$. To prove the reverse inclusion, note that for any $x \in \mathbb{R}$, $\sin x \in [-1,1]$, and hence it is true that $T \subseteq S$. We have thus shown that $$S = [-1,1] = \{ \sin x \,|\, x \in \mathbb{R} \} = T.$$

Families of sets

We will now introduce a useful notation that will serve us well in the subsequent development of set theory. A family of sets indexed by the set $I$ is a set $S$ whose elements are sets $S_i$ where $i \in I$. In symbols, $$S = \{S_i \,|\, i \in I\}.$$ The set $I$ is also called the index set for the family. It is also conventional to represent the family as $$\{S_i\}_{i\in I}.$$

Example

Suppose that we have $4$ sets $S_1, S_2, S_3, S_4$ defined as follows: $$\begin{split} S_1 &= [0, 1) \subseteq \mathbb{R},\\ S_2 &= [0, 1/2) \subseteq \mathbb{R},\\ S_3 &= [0, 1/3) \subseteq \mathbb{R},\\ S_4 &= [0, 1/4) \subseteq \mathbb{R}. \end{split}$$ Let $I_n \subseteq \mathbb{N}$ be the set consisting of the first $n$ natural numbers: $$I_n = \{1, 2, \ldots, n\}.$$ We can now collect together all the $4$ sets $S_1, S_2, S_3, S_4$ into a single set $S$, and index it using $I_5$: $$S = \{[0,1), [0,1/2), [0,1/3), [0,1/4)\} = \{S_i \,|\, i \in I_4\} = \{S_i\}_{i \in I_4}.$$ The indexing notation is particularly convenient when dealing with index sets which are subsets of real numbers. For instance, defining the sets $$T_a = \{[0, 1/a) \subseteq\mathbb{R}\,|\, a \in (0,1]\},$$ we write the set $T$ consisting of every such $T_a$ as $$T = \{T_a \,|\, a \in (0,1]\} = \{T_a\}_{a \in (0,1]}.$$

An important kind of family of sets is the power set $\mathcal{P}(S)$ of a given set $S$, consisting of all the subsets of $S$. Note that since $\emptyset \subseteq S$ for every set $S$, $\emptyset \in \mathcal{P}(S)$.

Example

Consider the set $S = \{1,2,3\}$. The power set of $S$ is the set $$\mathcal{P}(S) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{2,3\}, \{1,3\}, \{1,2,3\} \}.$$ Note that $\mathcal{P}(S)$ has $2^3 = 8$ elements. In general, the power set of a finite set consisting of $n$ elements has $2^n$ elements.

Remark

The power set of a given set is strictly larger than that set. Consider the set $\mathbb{N}$ of all natural numbers. Intuitively, we think of this as an infinite set. Consider the power set $\mathcal{P}(\mathbb{N})$ of $\mathbb{N}$. Based on the comment just made, $\mathcal{P}(\mathbb{N})$ should have more elements in it than $\mathbb{N}$, which by itself has infinite elements. Does it make sense to say that something is larger than infinity? We will unfortunately not have the pleasure of studying this very interesting question in these notes.

Set operations

Given an initial collection of sets, we can construct new sets from the existing ones using a variety of set operations. We will study a few of the more important one here.

Union

The union of two sets $S$ and $T$, written as $S \cup T$, is defined as the set of elements that belong to either $S$, or to $T$, or to both. Symbolically, $$S \cup T = \{a \,|\, a \in S, \text{ or } a \in T\}.$$ Given a family of sets $\{ S_i \}_{i \in I}$, the union of the family is defined similarly as $$\cup_{i \in I} S_i = \{a \,|\, \exists\,j\in I \text{ such that }a \in S_j\}.$$ Two special cases are worth noting here. When $I = \{1,2,\ldots,N\}$, the union is written as $$\cup_{i=1}^N S_i.$$ When $I = \mathbb{N}$, it is written as $$\cup_{i=1}^\infty S_i.$$

Example

Continuing the previous example involving the family $\{S_i \,|\, i\in I_4\}$ and $\{T_a \,|\, a \in (0,1]\}$, we see that $$\cup_{i \in I_4} S_i = [0,1) \cup [0,1/2) \cup [0,1/3) \cup [0,1/4) = [0,1).$$ Similarly, it is easily checked that $$\cup_{a \in (0,1]} T_a = [0,1).$$

Intersection

The intersection of two sets $S$ and $T$, written $S \cap T$, is defined as the set of elements that belong to both $S$ and $T$. In symbols, $$S \cap T = \{a \,|\, a \in S, \text{ and } a \in T\}.$$ The extension of the notation to the case of families of sets is analogous to the case of unions described earlier.

Two sets $S$ and $T$ are said to be disjoint if they have no element in common, $S \cap T = \emptyset$. A collection of sets is said to be pairwise disjoint if every pair of two sets in the collection is disjoint.

Example

With the sets $\{S_i \,|\, i \in I_4\}$ defined as earlier, note that $$\cap_{i \in I_4} S_i = [0,1) \cap [0,1/2) \cap [0,1/3) \cap [0,1/4) = [0,1/4).$$ Note also that $S_i \cap [1,2] = \emptyset$ for every $i \in I_4$. We therefore say that $S_i$ and $[1,2]$ are disjoint for every $i \in I_4$.

Set difference

The set difference of two sets $S$ and $T$, denoted as $S \setminus T$, is defined as the set of all elements of $S$ that do not belong to $T$: $$S \setminus T = \{a \in S \,|\, a \notin T\}.$$ If a universal set $X$ is provided, the complement of a set $S \subset X$, written as $S^c$, is defined as the set difference of $X$ and $S$. In symbols, $S^c = X \setminus S$.

Example

For any $a \in (0,1]$, we defined the set $T_a$ earlier as $[0,1/a)$. If $I = [0,1]$, then we see that $$I \setminus T_a = [1/a,1].$$ Since $T_a \subseteq \mathbb{R}$, we can compute its complement in $\mathbb{R}$ as $$T_a^c = \mathbb{R} \setminus T_a = (-\infty, 0) \cup [1/a,\infty).$$

Cartesian products

A set containing two elements $\{a,b\}$ has no natural ordering among its elements. Thus, this set is exactly the same as the set $\{b,a\}$. We define an ordered pair $(a,b)$ as a collection of two elements such that $a$ is the first element, and $b$ is the second element. Note that the ordered pair $(a,b)$ is different from the ordered pair $(b,a)$.

Remark

The notion of an ordered pair can be defined entirely in terms of sets. Consider the set $\{a,\{a,b\}\}$. This prescribes a set $\{a,b\}$, and singles out a particular element, $a$ in this case. If we define $(a,b) = \{a,\{a,b\}\}$, it is immediately obvious that the set $(a,b)$ is not the same as the set $(b,a) = \{b,\{a,b\}\}$. While this shows how an order is fundamentally just a special set, it is almost never explicitly written out in practice.

The Cartesian product of two sets $S$ and $T$ is defined as the set $S \times T$ that consists of all ordered pairs $(s,t)$ such that $s$ belongs to $S$ and $t$ belongs to $T$: $$S \times T = \{(s,t) \,|\, s \in S, t \in T\}.$$

Example

Consider the sets $S = \{1,2,3\}$ and $T = \{\text{red}, \text{blue}\}$. The Cartesian product of $S$ and $T$ in this case is computed as $$S \times T = \{ (1,\text{red}), (1,\text{blue}), (2,\text{red}), (2,\text{blue}, (3,\text{red}), (3,\text{blue} \}$$

Remark

The word Cartesian derives from the the name of the French philosopher Rene Descartes. We will capitalize the first letter of the name of a term if that term has its origin in the name of an individual.

The Cartesian product of a finite collection of sets $S_1, S_2, \ldots, S_n$ is defined similarly as $$S_1 \times S_2 \times \ldots \times S_n = \{(s_1, s_2, \ldots, s_n) \,|\, \forall\,i\in\{1,2,\ldots,n\},\,s_i \in S_i\}.$$ A similar extension holds for an infinite collection of sets.

The Cartesian product of a set $S$ with itself, $S \times S$, is often written as $S^2$. Similarly, the cartesian product of $n$ copies of $S$ is written as $S^n$.

Example

As an important example of the Cartesian product of a set with itself is the set $\mathbb{R}^n$: $$\mathbb{R}^n = \underbrace{\mathbb{R} \times \ldots \times \mathbb{R}}_{n \text{ factors}}.$$ In particular, the sets $\mathbb{R}$, $\mathbb{R}^2$ and $\mathbb{R}^3$ will play a significant role in these notes.

Binary relations

A binary relation $R$ on a set $S$ is a subset of $S \times S$. If $(a,b) \in R$, it is conventional to represent this as $a\,R\,b$.

Remark

In the example presented earlier in the context of the Cartesian product, $S = \{1,2,3\}$ and $T = \{\text{red}, \text{blue}\}$. One possible relation on $S \times T$ is the set $R$ defined as $$R = \{(1, \text{red}), (1, \text{blue}), (3, \text{blue})\}.$$ Note that, in this case, $1 \,R\, \text{blue}$, while it is not true that $2 \,R\, \text{blue}$.

A binary relation $R \subseteq S \times S$ is said to be

• reflexive, if it is true that for each $a \in S$, it is the case that $a\,R\,a$.

• symmetric, if for every $a,b \in S$, $a\,R\,b \Rightarrow b\,R\,a$.

• antisymmetric if for every $a,b \in S$, $(a\,R\,b\text{ and }b\,R\,a)\Rightarrow a = b$.

• transitive if for every $a,b,c \in S$, $(a\,R\,b\text{ and }b\,R\,c)\Rightarrow a\,R\,c$.

Example

Given any set $S$, let us consider the relation $\subseteq$ on the power set $\mathcal{P}(S)$ of $S$. Note that for any $A, B, C \in \mathcal{P}(S)$, $A \subseteq A$ shows us that the relation is reflexive; $A \subseteq B \text{ and } B \subseteq A \Rightarrow A = B$ shows us that the relation is anti-symmetric; and, $A \subseteq B \text{ and } B \subseteq C \Rightarrow A \subseteq C$ shows us that the relation is transitive.

Example

Consider the set $S = \{1,2,3\}$. The relation $R$ on $S$ defined as $$R = \{(1,1), (2,2), (1,2), (2,1), (2,3), (3,2), (1,3), (3,1)\}$$ is not reflexive since $(3,3) \notin R$. It is, however, symmetric and transitive.

An equivalence class on a set $S$ is a binary relation on $S$ that is reflexive, symmetric and transitive. An equivalence class is typically represented using symbols like $\sim$, and $(a,b)\in\sim$ is usually written as $a \sim b$. Given an equivalence relation $\sim$ on $S$, we define the equivalence class of $a \in S$ as the set $[a]$ consisting of all elements in $S$ that are related to $a$ through $\sim$, $$[a] = \{b \in S \,|\, b \sim a\}.$$ The notation $[a]_\sim$ is used if the particular equivalence relation used to define this class is to be emphasized. The collection of all equivalence classes $[a]$ of $S$ induced by the equivalence relation $\sim$ is called the factor space of $S$, and is denoted as $S / \sim$. Thus, $$S / \sim = \{[a] \,|\, a \in S\}.$$

Example

Consider the following equivalence relation $\sim$ on the set $\mathbb{N}$ of all natural numbers: $$m \sim n \text{ iff } (m - n) \text{ is divisible by } 5.$$ Let us first verify that this is an equivalence relation. $\sim$ is reflexive since for any natural number $n \in \mathbb{N}$, $n - n = 0$ is divisible by $5$. For any $m, n \in \mathbb{N}$, if $m \sim n$, then $(m - n)$ is divisible by $5$. But this also means that $(n - m)$ is divisible by $5$. In other words, $n \sim m$. Thus, we see that $\sim$ is symmetric. Finally, for $m,n,k \in \mathbb{N}$, if $m \sim n$ and $n \sim k$, then $(m -n) = 5p$ for some $p \in \mathbb{Z}$, and $(n - k) = 5q$ for some $q \in \mathbb{Z}$. Adding these two equations, we see that $(m - k) = 5(p + q)$, and hence that $m \sim k$. We therefore see that $\sim$ is also a transitive relation. Together, these three results show that $\sim$ is an equivalence relation on $\mathbb{N}$. The equivalence classes of $\mathbb{N}$ in this case are given by $$\begin{split} [0] &= \{0, 5, 10, 15, \ldots \},\\ [1] &= \{1, 6, 11, 16, \ldots \},\\ [2] &= \{2, 7, 12, 17, \ldots \},\\ [3] &= \{3, 8, 13, 18, \ldots \},\\ [4] &= \{4, 9, 14, 19, \ldots \}. \end{split}$$ There are only $5$ distinct equivalence classes in this case. The factor space is thus seen to be $$\mathbb{N}/\sim = \{[0], [1], [2], [3], [4]\}.$$

Equivalence classes offer a power means to partition a set. A partition of a set $S$ is a pairwise disjoint family $\{T_i \, |\, i \in I\}$ of subsets of $S$ such that the $\cup_{i \in I} T_i = S$. The sets $\{T_i\}_{i \in I}$ are then said to partition the set. The importance of equivalence relation lies in the fact that it partitions the set on which it is defined into disjoint equivalence classes.

Proof

A proof of the statement that an equivalence class $\sim$ on a set $S$ partitions the set into disjoint equivalence classes is provided here. This can be skipped on a first reading.

Consider the set $P = \{[a]\,|\,a \in S\}$ consisting of all the equivalence classes of $S$. It is easy to see that $\cup_{a \in S} [a] = S$. By construction, $\cup_{a \in S} [a] \subseteq S$. Further, $a \in S \Rightarrow a \in [a] \subseteq \cup_{a \in S} [a]$, which gives the reverse inclusion, $S \subseteq \cup_{a \in S} [a]$. Thus, $\cup_{a \in S} [a] = S$.

We prove next that if $a,b \in S$ and $a \sim b$, then $[a] = [b]$. Choose any $c \in [a]$. This choice is always possible since $a \in [a]$, and hence $[a] \neq \emptyset$. From the definition of an equivalence class, $c \in [a] \Rightarrow c \sim a$. Using the transitivity property of the equivalence relation, $(c \sim a$ and $a \sim b) \Rightarrow c \sim b$, and hence $c \in [b]$. We have thus shown that $[a] \subseteq [b]$. By a symmetric argument, it is evident that $[b] \subseteq [a]$. This shows that if $a \sim b$, then $[a] = [b]$.

Finally, let us show that the equivalence classes that are not disjoint are identical. Consider any two equivalence classes $[a]$ and $[b]$, where $a, b \in S$. It is either the case that $[a] \cap [b] = \emptyset$, or $[a] \cap [b] \neq \emptyset$. In the latter case, $\exists\,c \in S$ such that $c\in[a]$ and $c\in[b]$. But this means that $c \sim a$ and $c \sim b$, and hence, by symmetry and transitivity of the equivalence relation, $a \sim b$. Using the argument given earlier, we see that $[a] = [b]$. We have thus shown that $\cup_{a \in S} [a] = S$ is a pairwise disjoint cover of $S$, consisting of subsets of $S$.

Example

In the example considered earlier, notice how the set of equivalence classes $\{[0], [1], [2], [3], [4]\}$ is pairwise disjoint, and further that $$\cup_{i \in I_5} [i-1] = \mathbb{N}.$$ The factor space $S/\sim = \{[0], [1], [2], [3], [4]\}$ thus provides a partition the set of natural numbers $\mathbb{N}$.

Maps and functions

Given two sets $S$ and $T$, a map, or a mapping, from $S$ into $T$ is a relation $\varphi \subseteq S \times T$ between $S$ and $T$ with the property that for every $s \in S$, there exists a unique $t \in T$ such that $(s,t) \in \varphi$. In symbols, $$\forall\,s\in S,\,(s,t)\in\varphi\text{ and }(s,t')\in\varphi \,\Rightarrow\,t = t'.$$ It is conventional to notate $(s,t)\in\varphi$ as $\varphi(s) = t$ to make connection with the notation often employed in applications. We will also use the notation $\varphi:s \mapsto t$ to denote the fact that $\varphi$ maps $s \in S$ to $t \in T$. The set $\{(s,t)\in S \times T \,|\, (s,t) \in \varphi\}$ is called the graph of $\varphi$. We will reserve the word function to denote a map of the form $\varphi:S \to \mathbb{R}$.

Example

Consider the sets $S = \{1,2,3\}$ and $T = \{\text{red},\text{blue}\}$. The relation $\varphi \subseteq S \times T$ defined as $$\varphi = \{(1,\text{red}),(1,\text{blue}),(2,\text{red}),(3,\text{blue})\}$$ does not represent a map since $1$ is related to both $\text{red}$ and $\text{blue}$. One the other hand, the relation $\psi \subseteq S \times T$ defined as $$\psi = \{(1,\text{red}),(2,\text{red}),(3,\text{blue})\}$$ represents a mapping between $S$ and $T$: $\psi(1) = \text{red}$, $\psi(2) = \text{red}$, and $\psi(3) = \text{blue}$.

The fact that the map $\varphi$ takes an element of $S$ and returns an element of $T$ is compactly written using the notation $\varphi:S \to T$. Here, the set $S$ is called the domain of $\varphi$, and $T$ is called the codomain of $\varphi$. The domain of $\varphi$ is sometimes abbreviated as $\text{dom }\varphi$. The set $\varphi(S) = \{t \in T \,|\, \exists\,s\in S\text{ such that }\varphi(s) = t\}$ is called the range of $\varphi$. $\varphi(S)$ is also called the image of $S$ under $\varphi$, and is sometimes abbreviated as $\text{img }\varphi$.

Remark

It is important to always be aware of the domain and codomain of any map/function. For instance, the two functions $f:\mathbb{R}\to\mathbb{R}$, defined as $$\forall\,x \in \mathbb{R}, \quad f(x) = x^2,$$ and the function $g:\mathbb{R}_+\to\mathbb{R}$, defined as $$\forall\,x \in \mathbb{R}_+, \quad g(x) = x^2,$$ represent two different functions.

The pre-image, or inverse image, of a subset $V \subseteq T$ of $T$ under the mapping $\varphi:S \to T$ is the subset of $S$ consisting of all those elements that are mapped into $V$ through $\varphi$, $$\varphi^{-1}(V) = \{ s \in S \,|\,\varphi(s) \in V\}.$$ The notation $\varphi^{-1}$ should not be confused with the inverse map, to be defined later. We also note that $\varphi^{-1}(V) = \emptyset$ if there is no $s \in S$ such that $\varphi(s) \in V$. Thus, the inverse image is defined for all subsets of $V$.

Example

Consider the sets $S = \{1,2,3\}$, $T = \{\text{red}, \text{green}, \text{blue}\}$ and the map $\psi:S \to T$ defined as $$\psi = \{(1,\text{red}), (2,\text{red}), (3,\text{blue})\}.$$ In this case, $\psi^{-1}(\text{red}) = \{1,2\}$, $\psi^{-1}(\text{blue}) = \{3\}$ and $\psi^{-1}(\text{green}) = \emptyset$.

Given sets $S,T,V$ and maps $\varphi:S \to T$ and $\psi:T\to V$, the composition map $\psi \circ \varphi:S \to V$ is defined as $\psi\circ\varphi(s) = \psi(\varphi(s))$, for every $s \in S$. The composition of maps is associative. What this means is that if $\varphi:S \to T$, $\psi: T \to V$, and $\xi:V \to W$ are given maps, then $\xi\circ(\psi\circ\varphi) = (\xi\circ\psi)\circ\varphi$. It thus makes sense to write the composition map as $\xi\circ\psi\circ\phi:S \to W$.

Example

Let $f:\mathbb{R}\to\mathbb{R}_+$ be the function defined as $$\forall\, x\in \mathbb{R}, \quad f(x) = x^2.$$

Let $g:\mathbb{R}_+\to \mathbb{R}$ be the function defined as $$\forall\, x\in\mathbb{R}, \quad g(x) = \log x.$$

Then the composite function $g \circ f:\mathbb{R}\to\mathbb{R}$ is given by $$\forall\,x\in\mathbb{R},\quad (g\circ f)(x) = g(f(x)) = \log x^2.$$

The map $\varphi:S \to T$ is said to be a one-to-one map from $S$ into $T$, or injective, or an injection, if for $s,s' \in S,\,\varphi(s) = \varphi(s') \Rightarrow s = s'$. The map $\varphi:S\to T$ is said to be a map from $S$ onto $T$, or surjective, or a surjection, if $\varphi(S) = T$. The map $\varphi:S\to T$ that is both one-to-one and onto, or, equivalently, both injective and surjective, is said to be a one-to-one correspondence, or bijective, or a bijection from $S$ onto $T$. A bijection thus allows us to identify elements of one set with that of another.

Example

We will now illustrate how the choice of the domain and codomain for the same rule can be critical in deciding the nature of the corresponding map:

• The function $f:\mathbb{R} \to \mathbb{R}_+$ defined as $$\forall\, x \in \mathbb{R}, \quad f(x) = x^2,$$ is onto, but not one-to-one.

• The function $g:\mathbb{R}_+ \to \mathbb{R}$ defined as $$\forall\, x \in \mathbb{R}_+, \quad g(x) = x^2,$$ is one-to-one, but not onto.

• The function $h:\mathbb{R}_+ \to\mathbb{R}_+$ defined as $$\forall\, x \in \mathbb{R}_+, \quad h(x) = x^2,$$ is both one-to-one and onto.

If $\varphi:S \to T$ is a bijection, the inverse map $\varphi^{-1}:T \to S$ is defined as follows: $\forall\,t\in T,\,\varphi^{-1}(t) = s$, where $s \in S$ is the unique element in $S$ such that $\varphi(s) = t$.

Remark

It is important to distinguish the inverse map from the inverse image. The latter is a mapping from subsets of $T$ to subsets of $S$, and is defined even when the inverse map does not exist.

Given any set $S$, we will use the notation $\text{id}_S:S \to S$ to denote the identity map defined as $\text{id}_S(s) = s$ for every $s \in S$. (Depending on the context, other notations will also be used for the identity map.) We thus see that if $\varphi:S \to T$ is a bijection, then $\varphi^{-1} \circ \varphi = \text{id}_S$ and $\varphi \circ \varphi^{-1} = \text{id}_T$.