1.4. Functions

A function is a special type of relation and, consequently, itself a set.

Definition.

A relation $f\subseteq A\times B$ is called a function from $A$ to $B$ if for all $a\in A$, there is a unique $b\in B$ such that $(a,b)\in f$.

1. I abbreviate these circumstances by the symbol $f:A\to B$.
2. The set $A$ is called the domain of $f$, and $B$ is called the codomain of $f$.
3. The element $b$ is called the image of $a$ under $f$ and always denoted by $f(a)$, and $a$ is called a preimage of $b$.

Exercise.

Determine which of these relations is a function from $\{0,1,2,3\}$ to $\mathbb{N}$.

1. $\{(0,1),(0,2),(1,0),(2,0),(3,3)\}$
2. $\{(0,1),(1,2),(2,3),(3,4)\}$
3. $\{(0,0),(1,0),(2,0),(3,0)\}$
4. $\{(0,0)\}$

Examples.

Let $X$ be a nonempty set.

1. A function of the form $X\times \{c\}$ is called a constant function.
2. The identity on $X$ is the function $\{(x,x):x\in X\}$. I denote this by ${\mathrm{id}}_X$.
3. If $X\subseteq Y$, the function $\{(x,x):x\in X\}$ is called the inclusion map from $X$ to $Y$. I denote this by $X\hookrightarrow Y$.

Exercises.

1. In the examples above, are 2 and 3 the same? What is the difference?
2. Rewrite all the above examples by defining the functions using only their rule of correspondence, that is, exhibiting a formula of the form $f(x)=?$.

Direct and inverse images

Recall that the symbol $\exists$ represents “exists.” Also, I use the symbol $:=$ instead of $=$ when I want to remind the reader that I am not just claiming the sets are equal, I am declaring it as part of a definition.

Definition.

Let $f:X\to Y$ and $A$ be any set.

1. The direct image of $A$ under $f$ is the set $f[A]:=\{y\in Y:\exists a\in A(a,y)\in f\}$.
2. The inverse image of $A$ under $f$ is the set $f^{-1}[A]:=\{x\in X:\exists a\in A(x,a)\in f\}$.
3. The set $f[X]$ is called the image of $f$. Some textbooks might use the word range.

My definition does not require any assumptions about the set $A$ and still makes perfect sense. However, most textbooks require $A\subseteq X$ for the direct image and $A\subseteq Y$ for the inverse image. How do these definition change in this case?

Warning:

Most textbooks will use the notation $f(A)$ to denote the direct image of $A$ under $f$. In most cases (e.g., analysis, linear algebra, etc.) this will not cause confusion. But in general, this notation is ambiguous if, for instance, the domain of $f$ also consists of sets in the same language as its powerset. In this case, $f(A)$ could either mean the image or the direct image, and these could have different values.

Exercises.

For the functions mentioned in the above examples, find the direct and inverse images of the following sets under those functions. Assume that $Y=\mathbb{N}$ and that $X=\{0,2,4,\dots \}$. Prove your claims if you want to learn.

1. $\varnothing$.
2. $\{0\}$.
3. $\{0,1,2\}$.
4. $\{0,2,4\}$.
5. $X$.

Exercises.

Suppose that $A\subseteq B$ and $f:X\to Y$. Prove that

$$f[A]\subseteq f[B]\text{ and }{f}^{-1}[A]\subseteq f^{-1}[B].$$

Reflect.

Under what conditions can you change $\subseteq$ for $=$?

Injectivity and surjectivity

Definition.

A function $f:X\to Y$ is called:

1. injective, or one-to-one if for all $x,y\in X$, $f(x)=f(y)$ implies $x=y$.
2. surjective, or onto, if $f[X]=Y$.
3. bijective if it is both injective and surjective.

Write the contrapositive statement of the first definition above. When would you use the contrapositive rather than the direct statement? Write out the second definition as a quantified statement.

Exercise.

Out of all the examples mentioned in this page, decide which ones are injective, which ones are surjective? Write a proof for each claim.

Exercise.

Let $f:X\to Y$ be a surjective function and define $x\sim y$ if $f(x)=f(y)$. Prove that $\sim$ is an equivalence relation on $X$. Where is surjectivity needed?

Conversely, show that if if $\sim$ is an equivalence relation on $X$, then there is a set $Y$ and a surjective function $f:X\to Y$ such that $f(x)=f(y)$ if and only if $x\sim y$.

Hard exercise.

I say $P$ is a partition of $X$ if $\bigcup P=X$ ($\bigcup P$ is the union over all sets that are members of $P$), $\varnothing \notin P$ and the elements of $P$ are pairwise disjoint. Prove that any quotient on $X$ is a partition of $X$.

Conversely, show that for any partition, there is an equivalence relation whose quotient is equal to the partition.