Consider the following functions:

Let $A = \{1, 2, 3, 4\}$ and $B = \{a, b, c, d\}$, and define $f:A \rightarrow B$ by \begin{equation*} f(1) = a, f(2) = b, f(3) = c \textrm{ and } f(4) = d \end{equation*}

Let $A = \{1, 2, 3, 4\}$ and $B = \{a, b, c, d\}$, and define $g:A \rightarrow B$ by \begin{equation*} g(1) = a , g(2) = b, g(3) = a \textrm{ and } g(4) = b. \end{equation*}

The first function, $f\text{,}$ gives us more information about the set $B$ than the second function, $g\text{.}$ Since $A$ clearly has four elements, $f$ tells us that $B$ contains at least four elements since each element of $A$ is mapped onto a different element of $B\text{.}$ The properties that $f$ has, and $g$ does not have, are the most basic properties that we look for in a function. The following definitions summarize the basic vocabulary for function properties.

##### Definition7.2.1Injective Function, Injection

A function $f: A \rightarrow B$ is injective if \begin{equation*} a, b\in A, a\neq b \Rightarrow f(a) \neq f(b) \end{equation*} An injective function is called an injection, or a one-to-one function.

Notice that the condition for an injective function is logically equivalent to $f(a) = f(b) \Rightarrow a = b$ for all $a, b\in A$. This is often a more convenient condition to prove than what is given in the definition.

##### Definition7.2.2Surjective Function, Surjection

A function $f: A \rightarrow B$ is surjective if its range, $f(A)$, is equal to its codomian, $B\text{.}$ A surjective function is called a surjection, or an onto function.

Notice that the condition for a surjective function is equivalent to \begin{equation*} \textrm{For all } b \in B\textrm{, there exists } a\in A \textrm{ such that } f(a)=b.\text{.} \end{equation*}

##### Definition7.2.3Bijective Function, Bijection.

A function $f: A \rightarrow B$ is bijective if it is both injective and surjective. Bijective functions are also called one-to-one, onto functions.

The function $f$ that we opened this section with is bijective. The function $g$ is neither injective nor surjective.

##### Example7.2.4Injective but not surjective function

Let $A = \{1, 2, 3\}$ and $B = \{a, b, c, d\}$, and define $f:A \rightarrow B$ by $f(1) = b$, $f(2) = c$, and $f(3) = a$. Then $f$ is injective but not surjective.

##### Example7.2.5Characteristic Functions

The characteristic function, $\chi _S$ in Exercise 7.1.5.2 is surjective if $S$ is a proper subset of $A\text{,}$ but never injective if $\lvert A \rvert > 2$.

##### Example7.2.6Seating Students

Let $A$ be the set of students who are sitting in a classroom, let $B$ be the set of seats in the classroom, and let $s$ be the function which maps each student into the chair he or she is sitting in. When is $s$ one to one? When is it onto? Under normal circumstances, $s$ would always be injective since no two different students would be in the same seat. In order for $s$ to be surjective, we need all seats to be used, so $s$ is a surjection if the classroom is filled to capacity.

Functions can also be used for counting the elements in large finite sets or in infinite sets. Let's say we wished to count the occupants in an auditorium containing 1,500 seats. If each seat is occupied, the answer is obvious, 1,500 people. What we have done is to set up a one-to-one correspondence, or bijection, from seats to people. We formalize in a definition.

##### Definition7.2.7Cardinality.

Two sets are said to have the same cardinality if there exists a bijection between them. If a set has the same cardinality as the set $\{1,2,3,\ldots , n\}$, then we say its cardinality is $n\text{.}$

The function $f$ that opened this section serves to show that the two sets $A=\{1, 2, 3, 4\}$ and $B=\{a, b, c, d\}$ have the same cardinality. Notice in applying the definition of cardinality, we don't actually appear to count either set, we just match up the elements. However, matching the letters in $B$ with the numbers 1, 2, 3, and 4 is precisely how we count the letters.

##### Definition7.2.8Countable Set.

If a set is finite or has the same cardinality as the set of positive integers, it is called a countable set.

##### Example7.2.9Counting the Alphabet

The alphabet $\{A, B, C, . . . , Z\}$ has cardinality 26 through the following bijection into the set $\{1,2,3,\ldots ,26\}$. \begin{equation*} \begin{array}{ccccc} A & B & C & \cdots & Z \\ \downarrow & \downarrow & \downarrow & \cdots & \downarrow \\ 1 & 2 & 3 & \cdots & 26 \\ \end{array} \text{.} \end{equation*}

##### Example7.2.10As many evens as all positive integers

Recall that $2\mathbb{P}= \{b\in \mathbb{P} \mid b= 2k \textrm{ for some } k \in \mathbb{P} \}$. Paradoxically, $2\mathbb{P}$ has the same cardinality as the set $\mathbb{P}$ of positive integers. To prove this, we must find a bijection from $\mathbb{P}$ to $2\mathbb{P}$. Such a function isn't unique, but this one is the simplest: $f:\mathbb{P} \rightarrow 2\mathbb{P}$ where $f(m) = 2m$. Two statements must be proven to justify our claim that $f$ is a bijection:

• $f$ is one-to-one.

Proof: Let $a, b \in \mathbb{P}$ and assume that $f(a) = f(b)$. We must prove that $a = b$. \begin{equation*} f(a) = f(b) \Longrightarrow 2a = 2b \Longrightarrow a = b. \end{equation*}

• $f$ is onto.

Proof: Let $b \in 2\mathbb{P}$. We want to show that there exists an element $a \in \mathbb{P}$ such that $f(a) = b$. If $b \in 2\mathbb{P}$, $b = 2k$ for some $k \in \mathbb{P}$ by the definition of $2\mathbb{P}$. So we have $f(k) = 2k = b$. Hence, each element of 2$\mathbb{P}$ is the image of some element of $\mathbb{P}\text{.}$

Another way to look at any function with $\mathbb{P}$ as its domain is creating a list of the form $f(1),f(2), f(3), \ldots$. In the previous example, the list is $2, 4, 6, \ldots$. This infinite list clearly has no duplicate entries and every even positive integer appears in the list eventually.

A function $f:\mathbb{P}\to A$ is a bijection if the infinite list $f(1), f(2), f(3), \ldots$ contains no duplicates, and every element of $A$ appears on in the list. In this case, we say the $A$ is countably infinite, or simply countable

Readers who have studied real analysis should recall that the set of rational numbers is a countable set, while the set of real numbers is not a countable set. See the exercises at the end of this section for an another example of such a set.

We close this section with a theorem called the Pigeonhole Principle, which has numerous applications even though it is an obvious, common-sense statement. Never underestimate the importance of simple ideas. The Pigeonhole Principle states that if there are more pigeons than pigeonholes, then two or more pigeons must share the same pigeonhole. A more rigorous mathematical statement of the principle follows.

##### Example7.2.12A duplicate name is assured

Assume that a room contains four students with the first names John, James, and Mary. Prove that two students have the same first name. We can visualize a mapping from the set of students to the set of first names; each student has a first name. The pigeonhole principle applies with $n = 1$, and we can conclude that at least two of the students have the same first name.

# Subsection7.2.1Exercises for Section 7.2¶ permalink

##### 1

Determine which of the functions in Exercise 1 of Section 7.1 are one- to-one and which are onto.

##### 2

1. Determine all bijections from the $\{1, 2, 3\}$ into $\{a, b, c\}$.

2. Determine all bijections from $\{1, 2, 3\}$ into $\{a, b, c, d\}$.

##### 3

Which of the following are one-to-one, onto, or both?

1. $f_1:\mathbb{R} \rightarrow \mathbb{R}$ defined by $f_1(x) = x^3 - x$.

2. $f_2 :\mathbb{Z} \rightarrow \mathbb{Z}$ defined by $f_2(x)= -x + 2$.

3. $f_3:\mathbb{N} \times \mathbb{N}\to \mathbb{N}$ defined by $f_3(j, k) =2^j3^k$.

4. $f_4 :\mathbb{P} \rightarrow \mathbb{P}$ defined by $f_4(n)=\lceil n/2\rceil$, where $\lceil x\rceil$ is the ceiling of $x\text{,}$ the smallest integer greater than or equal to $x\text{.}$

5. $f_5 :\mathbb{N} \rightarrow \mathbb{N}$ defined by $f_5(n)=n^2+n$.

6. $\text{ }f_6:\mathbb{N} \rightarrow \mathbb{N} \times \mathbb{N}$ defined by $f_6(n)= (2n, 2n+1)$.

##### 4

Which of the following are injections, surjections, or bijections on $\mathbb{R}\text{,}$ the set of real numbers?

1. $f(x) = -2x$.

2. $g(x) = x^2- 1$.

3. $h(x)=\left\{ \begin{array}{cc} x & x < 0 \\ x^2 & x\geq 0 \\ \end{array} \right.$

4. $q(x)=2^x$

5. $r(x) =x^3$

6. $s(x) = x^3-x$

##### 5

Suppose that $m$ pairs of socks are mixed up in your sock drawer. Use the Pigeonhole Principle to explain why, if you pick $m + 1$ socks at random, at least two will make up a matching pair.

##### 6

In your own words explain the statement “The sets of integers and even integers have the same cardinality.”

##### 7

Let $A =\text{ }\{1, 2, 3, 4, 5\}$. Find functions, if they exist that have the properties specified below.

1. A function that is one-to-one and onto.

2. A function that is neither one-to-one nor onto.

3. A function that is one-to-one but not onto.

4. A function that is onto but not one-to-one.

##### 8

1. Define functions, if they exist, on the positive integers, $\mathbb{P}\text{,}$ with the same properties as in Exercise 7 (if possible).

2. Let $A$ and $B$ be finite sets where $|A|=|B|$. Is it possible to define a function $f:A \rightarrow B$ that is one-to-one but not onto? Is it possible to find a function $g:A \rightarrow B$ that is onto but not one-to-one?

##### 9

1. Prove that the set of natural numbers is countable.

2. Prove that the set of integers is countable.

3. Prove that the set of rational numbers is countable.

##### 10

1. Prove that the set of finite strings of 0's and 1's is countable.

2. Prove that the set of odd integers is countable.

3. Prove that the set $\mathbb{N}\times \mathbb{N}$ is countable.

##### 11

Use the Pigeonhole Principle to prove that an injection cannot exist between a finite set $A$ and a finite set $B$ if the cardinality of $A$ is greater than the cardinality of $B\text{.}$