To Infinity and Beyond. Introduction
Review of Set Theory
Functions
Countability
Cardinality
Hilbert's Grand Hotel

To Infinity and Beyond

A Review of Set Theory: Functions

by Maliha Hossain, proud member of the Math Squad

Let $f$ be a function from set $A$ to set $B$.

$\Leftrightarrow f : A \rightarrow B$

## Contents

### Onto (Surjective)

Definition The function $f$ is said to be surjective (or to map $A$ onto $B$) if $f(A) = B$; that is, if the range $F(f) = B$. If $f$ is a surjective function, we also say that $f$ is a surjection.

In other words, if for every $y$ in $B$, there exists at least one $x$ in $A$ such that $f(x) = y$, then $f$ is onto $B$.

e.g. Given that

$f(x) = x^5, \forall x \in \mathbb{R}, f : \mathbb{R} \rightarrow \mathbb{R}$

then, $f$ is onto the set R.

e.g. Given that

$f(x) = x^2, \forall x \in \mathbb{R}, f : \mathbb{R} \rightarrow \mathbb{R}$

then, $f$ is not onto the set R.

But if we define the domain of $f$ such that

$f(x) = x^2, \forall x \in \mathbb{R}, f : \mathbb{R} \rightarrow [0,\infty]$

then, $f$ is not onto.

Figures one and two show some other examples of functions, one of which is onto and one which is not.

$y = f(x) = x+5x^2+x^3, f:\mathbb{R}\rightarrow\mathbb{R}$
Fig 1: $f$ is onto since every value on the $y$-axis has at least one corresponding value on the $x$-axis

$y = f(x) = x^4, f:\mathbb{R}\rightarrow\mathbb{R}$
Fig 2: $f$ is not onto since there is no value on the $x$-axis that can produce a negative real number on the $y$-axis

### One-to-One (Injective)

Definition The function $f$ is said to be injective (or to be one-one) if whenever $x_1$ is not equal to $x_2$, then $f(x_1)$ is not equal to $f(x_2)$. If $f$ is an injective function, we also say that $f$ is a injection.

In other words, if $x_1$ and $x_2$ are in the domain of $f$ and if $f$ is one-to-one if either of the following is true

\begin{align} &\bullet x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2) \\ &\bullet f(x_1) = f(x_2) \Rightarrow x_1 = x_2 \end{align}

You may recall the informal method of checking whether functions are one-to-one using the horizontal line test. This is illustrated in the following examples in figures three and four.

$y = f(x) = x, f:\mathbb{R}\rightarrow\mathbb{R}$
Fig 3: Any arbitrary horizontal line $y = c$ intersects the function's graph only once so we can infer that $f$ is injective.

$y = f(x) = \sin(x), f:\mathbb{R}\rightarrow\mathbb{R}$
Fig 3: The $x$-axis intersects the graph of the function multiple times. It does not pass the horizontal line test. Therefore we can conclude that $f$ is not injective.

## Bijection

Definition If $f$ is both injective and surjective, then $f$ is said to be bijective. If $f$ is bijective, we also say that $f$ is a bijection

The next section of this tutorial will cover the countability of sets.

## References

• R. G. Bartle, D. R. Sherbert, "Preliminaries" in "An Introduction to Real Analysis", Third Edition, John Wiley and Sons Inc. 2000 ch. 1, sect. 1.1, pp 8.
• R. Kenney. MA 301. "An Introduction to Proof through Real Analysis", Lecture Notes. Faculty of the Department of Mathematics, Purdue University, Spring 2012

# Questions and comments

If you have any questions, comments, etc. please post them below:

• Comment / question 1

## Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett