## Section 4.3 Functions and Cardinality

¶Another special type of relation is a function.

###### Definition 4.3.1.

A function from a set \(A\) to a set \(B\) is a relation from \(A\) to \(B\text{,}\) where each element of \(A\) is paired with exactly one element of \(B\text{.}\) In other words, each input value results in exactly one output value.

Most of the mathematics that you have learned or will teach is based around the idea of functions. When students are asked to find a rule that defines a pattern, students are being asked to define a function. When you examine a sequence of values, you are examining a function. When you go to the Coke machine to get a soda, you are employing a function. (The input is your money. The output is the soda.) The dosage of medicine given to you when you are sick is a result of a function. The decision making process is an illustration of a function. Your daily life is a function whose domain is time and whose range is the activity you are doing at that time. They are everywhere!

You have studied functions in lots of places. Perhaps you looked at several definitions, graphical representations, the function notation, characteristics, etc. We will be looking specifically at two characteristics of functions and their applications.

###### Definition 4.3.2.

A function \(f\) from a set \(A\) to a set \(B\) is called one-to-one provided that each output results from exactly one input. That is, if \(b \in \range(f)\) with \(f(a_1)= f(a_2) = b\text{,}\) then \(a_1 = a_2\text{.}\)

A function \(f\) from a set \(A\) to a set \(B\) is called onto provided that every element of \(B\) is an element of \(\range(f)\text{.}\) That is, for every \(b \in B\text{,}\) there exists \(A \in A\) such that \(f(a) = b\text{.}\)

A function from a set \(A\) to a set \(B\) that is both one-to-one and onto is called a one-to-one correspondence or bijection.

You are probably wondering what you can possibly learn about functions that you have not already seen (maybe more than once!). We are going to use the definitions of one-to-one and onto to study sets. Primarily, we are going to study the cardinality of sets.

###### Definition 4.3.3.

The cardinality of a set \(A\) is the number of elments in the set, denoted \(|A|\text{.}\)

At first this may not seem to difficult. You simply need to count the elements in the set. However, what if your sets are infinite? Again you might be asking why this is a big deal. The answer of how many elements is in an infinite set is infinitely many, right? Would you believe that there are different sizes of infinity? This is the foundation of cardinality and the study of mathematician Georg Cantor (see Subsection 3.1.1).

###### Definition 4.3.4.

Two sets, \(A\) and \(B\) have the same cardinality if there is a one-to-one correspondence \(f\) from \(A\) to \(B\text{.}\)

A set \(A\) is finite with cardinality \(n\) provided that there is a one-to-one correspondence \(f\) from \(A\) to the set \(\{1, 2, 3, 4, ... , n\}\text{.}\)

The set of natural numbers is an infinite set with cardinality \(\aleph_0\) (aleph naught), the smallest of all infinities. We say that the set of natural numbers are countably infinite.

We are not going to spend a great deal of time discussing the sizes of infinity by name, but we are going to discuss the most common number sets to see whether they have the same cardinality as the natural numbers. Let's start with the set of whole numbers.

###### Theorem 4.3.5.

The set of whole numbers has the same cardinality as the natural numbers.

At first glance, you might be inclined to say that the set of whole numbers has one more element than the set of natural numbers and thus, it is impossible for them to be of the same “size.” Remember though that we are examining a different idea of “size”. To show that the set of whole numbers has the same cardinality as the natural numbers, we simply have to demonstrate that there is a one-to-one correspondence between the two sets.

###### Proof.

Consider the function \(f\text{,}\) mapping the set of whole numbers to the set of natural numbers, defined by \(f(w) = w + 1\text{.}\) Notice that this function maps \(0\) to \(1\text{,}\) \(1\) to \(2\text{,}\) \(2\) to \(3\) and so on. Because the function is linear, it is obviously one-to-one. Moreover, it is onto because if \(n\) is a natural number, then

(Note that since the natural numbers has a smallest element of \(1\text{,}\) the smallest value of\(n - 1\) is \(0\) which is the smallest whole number.)

Therefore, since \(f\) is a one-to-one correspondence, the set of whole numbers has the same cardinality as the set of natural numbers. Thus the set of whole numbers is also countably infinite.

###### Theorem 4.3.6.

The set of integers is countably infinite. That is, the set of integers has the same cardinality as the set of natural numbers.

You may have a bit more difficulty buying into this idea. After all, the set of natural numbers is a proper subset of the integers! How can this set possibly be the same “size” as the natural numbers? Remember, cardinality is a different way to determine “size.” The infinite sets that we are examining can not be counted in the ordinary way. Cardinality provides a tool that we can use to categorize the “size” of infinite sets.

After you get past the initial thoughts of denial, we can begin to think about how to develop the ont-to-one correspondence necessary to show that our claim is true. We know that an argument similar to the one we created for the set of whole numbers will not work because we wwould not account for any of the negative numbers. So what if we did a back and forth trick between the positive and negative integers. We know that we have even and odd natural numbers. What if we used the even to cover the positive numbers and the odds to cover the negative numbers? For example, we can send \(1\) to \(0\text{,}\) \(2\) to \(1\text{,}\) \(3\) to \(-1\text{,}\) \(4\) to \(2\text{,}\) \(5\) to \(-2\text{,}\) and so on.

###### Proof.

Consider the function \(f\text{,}\) mapping the natural numbers to the integers, defined by the following criteria.

- If \(n = 1\text{,}\) then \(f(n) = 0\text{.}\)
- If \(n\) is an even integer, then \(f(n) = n/2\text{.}\)
- If n is an odd integer and \(n \neq 1\text{,}\) then \(f(n) = -(n - 1)/2\text{.}\)

Note that this function is one-to-one. We can examine the graph to verify, if necessary. Also the function is onto. To see this, let \(x\) be any integer. If \(x\) is \(0\text{,}\) then we know \(f(1) = 0\text{.}\) If \(x\) is positive, then \(f(2x) = 2x/2 = x\text{.}\) Notice that \(2x\) is an even natural number. If \(x\) is negative, then

Notice \(-2x+1\) is an odd natural number. Thus in all three cases, \(x\) is mapped to by some natural number and \(f\) is onto. Therefore, \(f\) is a one-to-one correspondence and the set of integers have the same cardinality as the set of natural numbers, and is thus a countably infinite set.

###### Theorem 4.3.7.

The set of rational numbers is countably infinite. That is, the set of rational numbers has the same cardinality as the set of natural numbers.

This set is a bit harder to work with than the previous ones because the process of listing the rational numbers is difficult. We will eliminate some of the difficulty by working only with positive rational numbers. You should be able to explain how to adapt the solution to the complete set once you see the pattern.

Consider Figure 4.3.8. Notice that eventually, if the process was allowed to continue indefinitely, all rational numbers would be listed. Some numbers however are represented more than once. In order to preserve the one-to-one requirement, we need to eliminate any numbers that are equivalent to a rational number previously listed. The image below has made that adjustment.

Now we are going to develop our map. Unlike previous examples, we are not going to state our rule but we are going to let a picture do the talking. Remember that all we have to do is to demonstrate a one-to-one onto function.

So \(1\) will map to \(1\text{,}\) \(2\) to \(1/2\text{,}\) \(3\) to \(2/1\text{,}\) \(4\) to \(3/1\text{,}\) \(5\) to \(1/3\text{,}\) etc. Notice that each rational number will eventually be the output for our function and will be the output for exactly one natural number. Thus, we have created a one-to-one correspondence between the natural numbers and the positive rational numbers. We can easily extend this idea by sending the even natural numbers to the positive rational numbers and the odd natural numbers to the negative rational numbers to show that there is a one-to-one correspondence from the natural numbers to the set of all rational numbers. Therefore, the set of rational numbers is countably infinite.

###### Theorem 4.3.10.

The set of real numbers is not countably infinite. That is, the set of real numbers does not have the same cardinality as the set of natural numbers.

The real numbers will provide an example of a set that is “larger” than the set of natural numbers, whole numbers, integers, and rational numbers. To demonstrate, we will actually show that even the interval (0, 1) is not countable infinite. In other words, the set of numbers greater than zero and less than one cannot be put into a one-to-one correspondence with the set of natural numbers. To show that this is true, we will use a proof by contradiction.

We have to clear up a couple points before we begin. Frist, you whould realize that every number in the interval \((0, 1)\) can be written as an infinite decimal. For example,

Also recall from our discussions with geometric sequences and series, we discussed that \(0.99999\ldots = 1\text{.}\) You can prove this using the fact that \(0.9999\ldots\) is a geometric series with \(r = 1/10\) and \(a = 9/10\text{.}\) Since \(r \lt 1\text{,}\) the infinite sum of the series is \(S=1/(1-r)\text{.}\) With this in mind, anytime that we have this situation occur (a infinite number of repeating \(9\)'s), we are going to assume that we will equate this number with its equivalency in terms of repeated zeros. For example,

This will ensure that our function is one-to-one.

###### Proof.

Consider the interval \((0,1)\) and assume to the contrary that this set of numbers in countable infinite. Since the set is countable infinite, every number in the set can be listed in a one-to-one correspondence with the natural numbers. So we can say that there is a first element which maps to \(1\text{,}\) a second element which maps to \(2\text{,}\) so on and so forth. In order to list these values in an ordered way, let's call the first number \(a_1\) and denote it as

where \(d_{11}\) is the digit in the first number in our list and in the first position beyond the decimal, \(d_{12}\) is the digit in the first number in the list and in the second position beyond the decimal, etc.

Then the second number in the list would look like

where \(d_{21}\) is the digit in the second number in our list and in the first position beyond the decimal, \(d_{22}\) is the digit in the second number in the list and in the second position beyond the decimal, etc.

In general then, the ith number in the list would look like

where \(d_{i1}\) is the digit in the \(i\)th number in our list and in the first position beyond the decimal, \(d_{i2}\) is the digit in the \(i\)th number in the list and in the second position beyond the decimal, etc.

We now have the following list of all numbers that are in the interval \((0, 1)\text{,}\)

The key here is the realization that based on our assumption, every single number in the interval \((0, 1)\) is represented somewhere in this list. This is where we will obtain our contradiction.

Consider the number

where \(d_j\) is the \(j\)th digit beyond the decimal and is determined based on the following criteria:

If \(d_{jj} \neq 5\text{,}\) then \(d_j = 5\text{;}\) otherwise, \(d_j = 2\text{.}\)Notice that this means that by definition of the number \(d\text{,}\) \(d_1 \neq d_{11}\) and so the number \(d\) is not the number \(a_1\text{.}\) Similarly \(d \neq a_2\) because \(d_2 \neq d_{22}\text{.}\) Continuing this line of thought, \(d\) is not the same as any number in this list because \(d_j \neq d_{jj}\) for any natural number \(j\text{.}\) Thus \(\) is a number between \(0\) and \(1\) that is not in our list. This contradicts our assumption that there exists a one-to-one correspondence between the set of numbers greater than \(0\) and less than \(1\) and the set of natural numbers. Therefore the set of numbers in the interval \((0, 1)\) is not countably infinite

We say then that the set of numbers in the interval \((0, 1)\) is uncountable and thus, so is the set of real numbers.

### Exercises 4.3.1 Exercises

###### 1.

Show that the set of even numbers is countably infinite.