Maps and functions

 We often study the properties of a set by comparing it with another set. The "comparison"' is done by a map between the sets. Roughly speaking, a map (also called a function) is a rule to assign an element of a set to an element of another set. 

Let $A$ and $B$ be sets. Then we write $f:A\to B$ to mean that $f$ is a map from $A$ to $B$. That is, for each $a\in A$, we assign an element $f(a)\in B$. We often use a "diagram" such as the following:

The mapping of each element $x\in A$ to $f(x)\in B$ is written as $x\mapsto f(x).$

Example. Let us define a map $f:\mathbb{Z}\to \mathbb{N}$ by

$$f(x)=1+x^2,(x\in \mathbb{Z}).$$

Note that $f(x)\in \mathbb{N}$ for any $x\in \mathbb{Z}$, indeed. □

Definition (domain, codomain)

Let $A$ and $B$ be sets, and $f:A\to B$ be a map. Then, $A$ and $B$ are called the domain and codomain of $f$, respectively. We write $\text{dom}f=A$ and $\text{cod}f=B$.

Definition (identity map)

For any set $A$, the map ${\text{Id}}_A:A\to A$ defined by

$${\text{Id}}_A(x)=x$$

is called the identity map of $A$.

Example. ${\text{Id}}_{\mathbb{N}}(1)=1,{\text{Id}}_{\mathbb{N}}(2)=2,{\text{Id}}_{\mathbb{N}}(3)=3,\cdots$. □

We can also define a function with cases.

Example. We can define $f:\mathbb{R}\to \{0,1\}$ by

$$f(x)=\{\begin{array}{cc}1& \text{ if }x\in \mathbb{Q},\\ 0& \text{ otherwise}\end{array}$$

□

Example. The absolute value (modulus) $|x|$ of a real number $x$ is a function, $|\cdot |:\mathbb{R}\to \mathbb{R}$, defined as

$$|x|=\{\begin{array}{cc}x& \text{ if }x\ge 0,\\ -x& \text{if }x<0\text{.}\end{array}$$

For example, $|3|=3,|-3|=-(-3)=3$, etc. □

Definition (image)

Let $f:A\to B$ be a map. The image of $f$, denoted $\text{im}f$, is the set defined by $$\text{im}f=\{f(a)|a\in A\}.$$ That is, the set of all possible values of $f(a)$. Clearly, $\text{im}f\subset \text{cod}f.$

Remark. The image of a map $f$ with the domain $A$ is also denoted as $f(A)$. □

Example. Let's define $f:\mathbb{N}\to \mathbb{R}$ by $f(x)=x$. Then, $\text{im}f=\mathbb{N}.$ □

Example. Let $f:\mathbb{R}\to \mathbb{R}$ be the function $f(x)=x^2$. Then $\text{im}f=\{x^2|x\in \mathbb{R}\}=\{x|x\ge 0\}$, namely, the set of all non-negative real numbers. □

Definition (onto, surjective)

A map $f:A\to B$ is said to be onto or surjective if $\text{im}f=\text{cod}f$, that is, 

$$\mathrm{\forall }b\in B\mathrm{\exists }a\in A(b=f(a)).$$

(Informal translation: every $b\in B$ comes from $a\in A$ through $f$.)

Roughly speaking, the image of a surjective map "covers" the entire codomain.

Example. $f:\mathbb{Z}\to \mathbb{N}$ defined by $f(x)=1+|x|$ is surjective. However, $g:\mathbb{Z}\to \mathbb{Z}$ defined by $g(x)=1+|x|$ is not surjective. Note that $f$ and $g$ apparently have the same definition, the only difference is their codomains.

Definition (one-to-one, injective)

A map $f:A\to B$ is said to be one-to-one or injective if, for all $a,a^{\prime }\in A$, $a\ne a^{\prime }$ implies $f(a)\ne f(a^{\prime })$. In a logical form,

$$\mathrm{\forall }a,a^{\prime }\in A(a\ne a^{\prime }⟹f(a)\ne f(a^{\prime })).$$

Remark. $a\ne a^{\prime }⟹f(a)\ne f(a^{\prime })$ is equivalent to $f(a)=f(a^{\prime })⟹a=a^{\prime }$ (contrapositive). We can use the latter in the definition above.

Roughly speaking, an injective map maps different elements in $A$ to different elements in $B$. If a map is not injective, then different elements in $A$ can be mapped to the same point in $B$. That is, there are some different elements $a\ne a^{\prime }$ such that $f(a)=f(a^{\prime })$.

Example (1). $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=2x^3+1$ is injective. To see this, suppose we have $f(x)=f(y)$ for some $x,y\in \mathbb{R}$. Then, $2x^3+1=2y^3+1$ $⟹x^3=y^3$ $⟹x=y$. □

Example. $f:\mathbb{R}\to \mathbb{R}$ defined by $f(x)=x^2$ is not injective (why?). However, $g:{\mathbb{R}}_{+}\to \mathbb{R}$ defined by $g(x)=x^2$, where ${\mathbb{R}}_{+}=\{x\in \mathbb{R}|x\ge 0\}$, is injective. □

Definition (bijective)

A map that is both injective and surjective is said to be bijective.

Example. The function in the above Example (1) is bijective. □

We also use nouns such as injection, surjection, and bijection to mean injective, surjective, and bijective maps, respectively.

Definition (Graph (1))

Let $f:A\to B$ be a map. The graph of $f$ is the subset of $A\times B$ defined by

$$\mathrm{graph}(f)=\{(a,b)\mid a\in A,b=f(a)\}(\subset A\times B).$$

This may appear rather abstract. Let's see a concrete example. Let's take $f(x)=x^2-1:\mathbb{R}\to \mathbb{R}$. We can draw the graph of $y=f(x)$ on the $x$-$y$ plane.  Now, the plane is actually the set $\mathbb{R}\times \mathbb{R}$. The graph $y=f(x)$ is a curve in this plane, and hence it is a subset of the plane. The above definition is a generalization of this picture. 

Note the following properties of $\text{graph}(f)$:

1. For any $a\in A$, there exists some $b\in B$ such that $(a,b)\in \text{graph}(f)$.
2. If $(a,b),(a,b^{\prime })\in \text{graph}(f)$, then $b=b^{\prime }$.

In short, for any $a\in A$, there is some $b\in B$ such that $(a,b)\in \mathrm{graph}(f)$ (part 1) and that $b$ is unique (part 2).

We can reverse the argument and use these two properties to define the graph.

Definition (Graph (2))

Let $A$ and $B$ be sets. Let $S$ be a subset of $A\times B$. $S$ is said to be a graph if it satisfies the following properties:

1. For any $a\in A$, there exists some $b\in B$ such that $(a,b)\in S$.
2. If $(a,b),(a,b^{\prime })\in S$, then $b=b^{\prime }$.

Note that this definition of the graph does not require the notion of a map. In fact, we can use the notion of the graph to define the map.

Definition (Map)

Let $A$ and $B$ be sets, and $S$ be a graph in the sense of (Graph (2)) above. Then, for any $a\in A$, there exists a unique $b\in B$ such that $(a,b)\in S$. We denote this unique $b$ by $f_S(a)$. That is, $f_S(a)=b$. This rule of making correspondence between each $a\in A$ to $f_S(a)\in B$ is called a map (induced by $S$), denoted 

$$f_S:A\to B.$$