Mathematical Proof/Functions

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Introduction[edit | edit source]

In the previous chapter, we have discussed the concept of relations. There are not much restrictions on the relations. For instance, for a relation from set to set , every element of can be related to no elements of , exactly one element of , or multiple elements of . In this chapter, we will focus on a particular type of relations from set to set where every element in is related to exactly one (or an unique) element of .

You should have encountered the concept of functions before, e.g. a function defined by gives you a value of for every given value of . The functions you have encountered are likely to be in the above form, i.e. in the form of an equation. Also, the value of and are likely to be real numbers.

But we can generalize such ideas to more general situations where and are not necessarily real numbers (e.g., they can be elements of certain sets), and the functions need not be expressed by a formula like above. As a result, the concept and definition of functions discussed here may seem foreign to you, and look quite different from what you have previously learnt about functions.

Definitions[edit | edit source]

Definition. (Functions) Let and be sets. A function or mapping from set to set , written , is a relation from set to set such that for every element , there exists a unique such that .

Remark.

  • The notation "" may seem weird at the first place. However, when we think about what represents here, it becomes more natural: since is a relation from set to set , it is indeed a subset of . So, it makes sense to say is an element of .
  • However, it is much more common to write instead (and you should have seen this notation before).
  • Since is a relation, we can apply the terminologies to functions: the set is the domain of function , denoted by .
  • We also have some more terminologies for functions: The set is called the codomain of , is the image of under . Also, is referred to as the pre-image of under . Furthermore, we say that maps into .
  • From the definition, every element has an unique (or exactly one) image.
  • When the set is empty, then the only function (and also the only relation) from set to is the empty set. When set is nonempty while the set is empty, since the only relation from set to is also the empty set, but such relation does not satisfy the requirements to be a function (there does not exist such that for every ).
Clipboard

Exercise. Write down the meaning of " is not a function from to ", i.e., the negation of the definition above. (Hint: first split the unique existential quantifier into two the existence part and uniqueness part.)

Solution

First, we express the meaning of " is a function from to " using logical notations:

Then, the meaning of " is not a function from to " is:
(LHS means the existential requirement is violated, and RHS means the uniqueness requirement is violated.) In other words, the meaning is "there exists some with no image, OR there exists some with more than one image".

Example. Let and . Then,

defines a function. Graphically, it looks like

  A               B
*----*          *----*
|1*  #
|    |  #       |    |
|    |       #  |    |
|    |          |#   |
|2* # # # # # #  # *a|
|    |          |    |
|3* # # # # # #  # *b|
|    |          |    |
*----*          *----*

Here, is the image of 1 and 2 under . In other words, 1 and 2 are the pre-images of . Similarly, is the image of 3 under and 3 is the pre-image of under .

Example. Let and . Then, is not a function from to since has two images: 1 and 2. Also, is not a function from to since and have no image.

Example. It is quite common to refer, say, "" to as a "function". But, when we look at the definition of function, such saying actually has some issues, strictly speaking:

  1. What are the domain and codomain?
  2. is just an image of a real number under . The function itself should be a set.

For the first question, usually the domain and codomain are taken to be . But for some functions, becomes undefined for some values of real number . In this case, it is common to set the domain as , which is referred to as the natural domain.

For the second question, the actual function is indeed the set

This set of point in the plane is the graph of (a parabola). However, it is acceptable to have such saying for convenience.

Clipboard

Exercise. A commonly encountered function is the exponential function, which is defined by . Another one is the natural logarithm function defined by .

(a) Find the domain and codomain of the functions and .

(b) Express the functions and using sets.

Solution

(a) The domain and codomain of are both . The domain of is (when is less than or equal to zero, is undefined), and the codomain of is .

(b) and .

We should be aware that the codomain of a function is not necessarily the same as the range of a function. The following is the definition of the range of a function (same as the definition for a relation).

Definition. (Range of function) The range of a function , denoted by , is

Remark.

  • Comparing the definitions of range and codomain, we can notice that for the range, it includes all elements in the codomain that have at least one pre-image. On the other hand, the codomain is the set that contains everything into which every element can be possibly mapped.
  • When the range and the codomain of a function turn out to be the same, we call such function to be surjective. We will discuss more properties for a function later.
  • We can observe that we can actually manually set (or restrict) the codomain of function to be its range. So, even if a given function is not surjective, we can make it surjective by changing its codomain manually.

Example. Let and . Define the function by

Then,

Clipboard

Exercise. Let and be sets, and be a fixed element of . Then, the function defined by for every is called the constant function from to .

(a) What is the range of constant function?

(b) What is the codomain of constant function?

(c) Can the range of constant function equal its codomain?

(d) What is/are the pre-image(s) of ?

Solution

(a) The range is .

(b) The codomain is the set .

(c) Yes, if .

(d) The pre-images of are all elements of .

Example. (Identity function) Let be a set. Then the function defined by for every is called the identity function of . Every is the image of itself. The domain, codomain, and range of are all .

Remark.

  • This function is quite important in the section about inverse functions.

Example. Consider the function defined by . Find the range of the function , , and prove your answer.

The range of the function is .

Proof. To prove that , we will prove (i) ; (ii) .

Firstly, for : for every ,

On the other hand, for : for every , we choose . Then, . So, by definition, we have .


Clipboard

Exercise. Consider the function defined by . Find , and prove your answer.

Solution

We have .

Proof. First, for every ,

This shows that .

On the other hand, for every , we choose . Then, . So, we have . This shows that , and we are done.


Since the domain and codomain, in addition to the "way" of the mapping, all affect the "behaviour" and properties of a function, it is natural to incorporate all these features into the definition of equality of functions:

Definition. (Equality of functions) Let and be sets, and let and be two functions from to (notice that their domains and codomains have to be the same). Then, the functions and are said to be equal, written , if for every .

Clipboard

Exercise. Write down the meaning for two functions and to be not equal.

Solution

( and have different domain) or ( and have different codomain) or (there exists such that ).

Example. Consider the functions and defined by and . Although their "formulas" are the same, they are not equal since their codomains are different.

Clipboard

Exercise. Consider the functions and defined by and . Are the functions and equal? Why?

Solution

No.

Notice hat is undefined when (and defined for every other real number ), while is defined for every real number . Thus, the domain of is and the domain of is . So, and are not equal.

Injective, surjective and bijective functions[edit | edit source]

In this section, we will discuss some important properties that a function may possess, namely injectivity, surjectivity, and bijectivity.

Definition. (Injective function) A function is injective or one-to-one if for every , , or equivalently (contrapositive), for every , .

Remark.

  • The definition tells us that an injective function from to maps distinct elements of into distinct elements of .
  • To prove that a function is injective, it is common to use a direct proof: for every , assume , and then proceed to prove that .
Clipboard

Exercise. Write down the meaning of "a function is not injective".

Solution

There exist such that and .

Example. A function is defined by . Prove that is injective.

Proof. For every ,

Thus, is injective.


Example. A function is defined by . Prove or disprove that is injective.

Disproof. Since , is not injective.

Clipboard

Exercise. A function is defined by . Prove that is injective.

Proof

Proof. For every ,

Remark.

  • It suggests that the domain of a function is important when we determine whether a function is injective. We should not just look at the formula of the function.



Example. A function is defined by . Prove or disprove that is injective.

This time, it is not immediately clear that whether this function is injective or not. So, we may first try to prove that is injective, and see what we get: for every ,

Notice that for the last equation to imply , we need and . However, and can take any real values. Hence, this suggests us to consider and disprove that is injective. Another observation is that when , then . But to make it equal zero, we can also take . Thus, this gives us a counterexample for disproving that is injective:

Disproof. Since , is not injective.


Clipboard

Exercise. A function is defined by . Prove or disprove that is injective.

Solution

Disproof. Since , is not injective.

Remark.

  • The graph of this function is a semicircle located above the -axis.


Definition. (Surjective function) A function is surjective or onto if for every , there exists such that .

Remark.

  • The definition tells us that is surjective if every element of the codomain is the image of some element of . In other words, .
Clipboard

Exercise. Write down the meaning of " is not surjective".

Solution

There exists such that for every , .

In other words, some element of the codomain is not the image of every element of . In other words, (since by definition, we may also write this as ).

Example. A function is defined by . Prove that is surjective.

To prove that is surjective, we need to prove that for every , there exists such that , i.e., . To show this, we can see that the choices of to satisfy the requirement for different values of are different. Indeed, the choice of depend on the value of . But it is not hard to choose such with a given value of : we can just rearrange the above equation to make to be the subject of the equation:

Proof. For every , choose . Then,


Example. Prove or disprove that the function defined by is surjective.

Disproof. Take . Then, there is no such that

since has no real solution. Hence, is not surjective.

Clipboard

Exercise. Prove that the function defined by is surjective.

Proof

Proof. For every , choose (it is possible to choose such real number since ). Then,

Remark.

  • It suggests that the codomain of a function is important when we determine whether a function is surjective. So, again, we should not just look at the formula of the function.



Definition. (Bijective function) A function is bijective or one-to-one correspondence if it is both injective and surjective.

Remark.

  • We should be aware that "one-to-one correspondence" (which means bijective) is different from "one-to-one" (which means injective).
  • In other words, is bijective if for every , there exists a unique such that (the existence part corresponds to the surjectivity, and the uniqueness part corresponds to the injectivity).
  • However, we usually still prove the bijectivity by proving the injectivity and surjectivity separately, similar to the case for proving "there exists a unique ..." where we prove the existence part and uniqueness part separately.
Clipboard

Exercise. Write down the meaning of " is not bijective".

Solution

is not injective or is not surjective.

Example. We have proved the function defined by is both injective and surjective. Hence, it is bijective.

Example. We have proved the function defined by is injective and the function defined by is surjective. Then, with basically the same proof, we can prove that the function defined by is both injective or surjective, and hence bijective.

Example. Prove that the function defined by is bijective.

For proving the surjective part, we need to make as the subject for the equaton :

Proof.

Injective: For every ,

Surjective: For every , choose . We then need to show that . Since (, so is defined), it suffices to show that . Let us prove it by contradiction:

Assume to the contrary that . Then, . So we arrive at a contradiction.

Then, we have


Clipboard

Exercise. Let be a set. Prove that the identity function is bijective.

Proof

Proof.

Injective: For every , .

Surjective: For every , choose . Then, .


Clipboard

Exercise. A function is defined by

Prove or disprove that is bijective.

Solution

Proof.

Injective: For every ,

Surjective: For every , choose . Then,


Clipboard

Exercise. Consider a function defined by , and another function defined by .

(a) Prove or disprove that is (i) injective; (ii) surjective.

(b) Prove or disprove that is (i) injective; (ii) surjective.

Solution
(a) (i)

Disproof. Since , is not injective.

(ii)

Disproof. Take . Then, for every , .

(b) (i)

Disproof. Since , is not injective.

(ii)

Proof. For every , choose . Then, .


Composition of functions[edit | edit source]

Let and be nonempty sets, and let and be two functions. In this section, we are going to discuss a way to create a new function from "combining" the two functions and , called their composition:

Definition. (Composition) Let and be two functions, where and are nonempty sets. Then, the composition of and , denoted by (read "g-circle-f"), is the function from to defined by

Remark.

  • We can see that the composition is obtained by first applying and then applying .

Example. Let and . Consider the functions and defined by

Then, we have and . So, the function is given by
However, is undefined, since the codomain of () is different from the domain of ().

Remark.

  • To make both and defined, we need to have and , that is, the domain (codomain) of must be equal to the codomain (domain) of .
  • In this case, is a function from to , and is a function from to . So, in order for them to be possibly equal, we need to further have .
  • But, even if , it is still possible that . Consider the following example.

Example. Let . Consider the functions and defined by

Then, and . Since, for example, , it follows that .

Remark.

  • This example shows that the composition of functions is not commutative. That is, after changing the order of the composition, the result may be different.

Although the composition of functions is not commutative, it is associative.

Theorem. (Associativity of the composition of functions) For every nonempty set , and for every function and , we have

Proof. First, since is a function from to , it follows that is a function from to . Similarly, since is a function from , it follows that is function from to .

It now remains to prove that both functions map every element into the same image in . For every ,

(a bracket for means "grouping" and first, that is, we regard as a function first. To understand this more easily, one may write instead of "" above.)

Also,

Example. Let and . Consider the functions , and defined by

Recall that we have shown that . We can further show that . Thus, and are given by

Now, let us study some results that are related to the composition, injectivity, surjectivity, and bijectivity.

Proposition. For every nonempty set and for every function and ,

(a) if and are injective, then is injective.

(b) if and are surjective, then is surjective.

Proof. For (a), assume that and are injective. Then, for every

For (b), assume that and are injective. Then, for every , since is surjective, there exists such that . For this , there must also exist such that since is surjective. It follows that for every , there exists such that

Corollary. For every nonempty set and for every function and , if and are bijective, then is bijective.

Proof. Assume that and are bijective, i.e., are injective and surjective. It follows by the above proposition that is injective and surjective, i.e., is bijective.

After knowing such results, it is natural to question that whether the converse of the above proposition holds. Indeed, the converse does not hold, and we have the following results:

Proposition. For every nonempty set and for every function and ,

(a) if is injective, then is injective.

(b) if is surjective, then is surjective.

Proof. For (a), assume that is injective. Then, for every ,

For (b), assume that is surjective. Then, for every , there exists such that . So, we now can show that is surjective: for every , we can choose , and then we have .

Remark.

  • It follows that if is bijective, then is injective and is surjective.
  • For (a), with the assumption, may or may not be surjective. Also, for (b), may or may not be injective.

To summarize the results, we have the following table:

Summary
(given)
injective injective injective/not injective
surjective surjective surjective/not surjective
bijective injective surjective
Clipboard

Exercise. Disprove that for every nonempty set and for every function and ,

(a) if is injective, then is injective.

(b) if is surjective, then is surjective.

Solution
(a)

Disproof. Take , and take the functions and defined by .

Then, the function is given by , which is injective, since for every , . However, the function is not injective since .

(b)

Disproof. Take , and take the functions and defined by .

Then, the function is given by , which is surjective, since for every , there exists such that . However, the function is not surjective, since, for example, take . Then, for every , .


Example. Consider two arbitrary functions and such that the function is given by

What properties do the functions and possess?

Solution. First, we claim that is bijective.

Proof.

Injective: for every , .

Surjective: for every , choose . Then, .

Then, we can conclude that is injective and is surjective by the above proposition.

Clipboard

Exercise. Consider the function satisfying for every . Prove or disprove that is (i) injective; (ii) surjective.

Solution

(i) and (ii):

Proof. First, notice that , and we have proved that is bijective. So, by the above proposition, is injective and surjective.


Inverse functions[edit | edit source]

Recall that a function is a special relation from set to set satisfying some requirements. Also, recall that given a relation from to , the inverse relation is defined to be

We know that the inverse relation is always a relation itself. However, is the inverse relation of a function always a function from to itself? The answer is, indeed, no. Consider the following example.

Example. Let and . Consider the function defined by

Then, the inverse relation (we are not calling it inverse function) of , denoted by , is
We can then see that this inverse relation is not a function from to , since the element has two images: 1 and 2.

Of course, when the inverse relation of a function turns out to be also a function from to , it is natural to define it as the inverse function of :

Definition. (Inverse function) Let and be sets, and let be a function. The inverse function of the function is the inverse relation of , denoted by , provided that is a function from to .

Remark.

  • Since given a relation from to , it has a unique (or exactly one) inverse relation from to (according to the definition), it follows that the inverse function of a function , if exists, is unique.

We are then interested in knowing under what conditions the inverse relation is a function from to , so that the inverse function exists.

First, in order for to be a function from to , we must have . So, we need to ensure that every element of is related to some elements in , so that when we "reverse" the ordered pairs in to get , there is at least one image for every . This means , i.e., needs to be surjective.

Of course, we also need to ensure that there is a unique image for every . Under the condition that is surjective, there is at least one image for every already. So, it remains to ensure that there is at most one image for every .

To ensure this, we need the function to be injective, since, if is injective, then every element of has at most one pre-image. So, when we "reverse" the ordered pairs in to get , every element of has at most one image.

From this discussion, we know that if is a function from to , then has to be injective and surjective, i.e. bijective. This shows that the bijectivity of is the necessary condition for the existence of the inverse function. Is it also the sufficient condition? It turns out that the bijectivity of is actually the necessary and sufficient condition for the existence of the inverse function:

Theorem. Let be a function. Then its inverse relation is a function from to (i.e., the inverse function of exists) if and only if the function is bijective.

Proof.

"" direction: Assume that is a function from to . Then, we will proceed to prove that is injective and surjective:

Injective: For every , first assume . Then, . By definition of inverse relation, we have . Since is a function from to , we have by definition .

Surjective: For every , since is a function from to , there exists a unique such that . This means by definition of inverse relation that , i.e., .

"" direction: Assume that is bijective. Then, we will proceed to prove that is a function from to . That is, we need to ensure that for every element , there exists a unique such that .

Existence: For every , since is surjective, there exists such that , i.e. . Hence, . This shows that for every , there exists such that .

Uniqueness: Assume , in addition to . So, we have , i.e., . Since is injective, we have .

Hence, from this theorem, we know that it is only meaningful to talk about inverse function of when is bijective. If is not bijective, then its inverse function does not exist at all, and it is meaningless to talk about it. The following theorem further suggests that the inverse function must also be bijective.

Theorem. If the function is bijective, then its inverse function is also bijective.

Proof. Assume that is bijective. Then, is a function from to . Then, we will show that it is injective and surjective.

Injective: For every , first assume . Then, . Thus, . It follows that since is a function.

Surjective: For every , since is a function, there exists a unique such that , i.e., , and hence , i.e., .

Remark.

  • Notice that in the proof, we do not make use of the bijectivity of to prove the injectivity and surjectivity of . Indeed, we just use the definition of function to prove them. The bijectivity of serves only one purpose: ensuring that the inverse function exists.

Another common definition of inverse function is that the inverse function of , denoted by , is a function satisfying

It turns out that these two definitions of inverse function are indeed (logically) equivalent. Consider the following theorem.

Theorem. Let and be two functions such that and . Then, is bijective and equals the inverse function of , .

Proof. Let us first prove that is bijective.

Injective: For every ,

Surjective: For every , choose . Then,

Now, let us prove that . Since is bijective, the inverse function exists. Then, since the domain and codomain of the inverse function is and respectively by definition, and have the same domain and codomain. It now remains to show that for every . Since is surjective, for every , there exists such that . This means . Now, we have for every ,

The converse of the above theorem is also true. More precisely, if is bijective, and thus its inverse function exists, then we have and . (Details are left to the following exercise.) Hence, the two definitions are actually logically equivalent, in the sense that

  • by the above theorem, the conditions in the alternative definition imply the conditions in our definition.
  • by the above remark, the conditions in our definition imply the conditions in the alternative definition.

It then follows that the function satisfying and is unique, since the inverse function is unique.

Clipboard

Exercise. Let be a function. Prove that if is bijective, and thus its inverse function exists, then we have and .

Proof. First, since is a function from to , it follows that is a function from to , and is a function from to .

Then, for every , there exists a unique such that , and hence . So,

Also, for every ,


Here, we will introduce an approach to find a formula for the inverse function. But this approach does not always work.

Example. Recall that we have proved that the function defined by is bijective. So, its inverse function exists. Determine the inverse function .

Solution. We have for every , . Hence,

Thus, the inverse function is given by

In this approach, we use some algebraic manipulation to find the inverse function. However, such method is not always possible. For instance, the function defined by is bijective, but its inverse function is given by (indeed, defined to be) . In this case, such inverse function cannot be obtained by such algebraic manipulation.

Clipboard

Exercise. Consider the function defined by

(a) Prove that is bijective.

(b) Determine the formula for inverse function, .


Solution
(a)

Proof.

Injective: For every ,

Surjective: For every , choose . Then,

(b) Since for every , we have

But the codomain of the inverse function is . So we should choose the positive square root as the formula, i.e.,

Remark.

  • It turns out that, in this case the function is equal to its inverse function .


Image sets and preimage sets[edit | edit source]

The concepts discussed in this section are the generalizations of the concepts of image and pre-image.

Definition. (Image (set) and preimage (set)) Let and be sets, and let be a function.

(a) Suppose . The image (set) of is the set

(b) Suppose . The preimage (set) of is the set

Remark.

  • Notice that the "" used in the notation for the preimage set is not referring to the inverse function. The preimage set of still makes sense even if the function is not bijective. However, the inverse function does not exist if the function is not bijective.
  • In other words, the image set contains the image of every element . So, it is a set of images, and hence the name.
  • On the other hand, the preimage set contains the pre-images of every element . That is, the preimage set is the set of elements in mapped into by .
  • Special case: suppose and . Then, the image set of is the set containing image of under : , and the preimage of set is the set containing the preimages (if any) of under .

Graphically, the image set looks like:

   A              B
*------*       *------*
|      |       |      |
|  . X |       | f(X) |
|.###. |       |  .   |
|.###.--------->.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

The preimage set looks like

   A              B
*------*       *------*
|f-1(Y)|       |      |
|  .   |       |  Y   |
|.###. |       |  .   |
|.###.<---------.###. |
|.###. |       |.###. |
|  .   |       |  .   |
*------*       *------*

Example. Let and . Consider the function defined by

Then,

Remark.

  • Notice that is not bijective, but it is still meaningful to consider the preimage sets of . For instance, we have , but "" has no meaning since does not exist at all.
  • We can observe that but . So, in general. Also, we can notice that after "applying" the image set and then preimage set on a set , it seems that we may get some set that is larger than .
  • On the other hand, we can see that but . So, in general. Also, it seems that we get some set that is smaller than .
  • Such kind of results turns out to be true in general (see the following theorem).
Clipboard

Exercise. Consider a function . Find (a) ; (b) ; (c) ; (d) .

Solution

(a) .

(b) .

(c) .

(d) .

Proposition. Let and be sets, and let be a function. Then,

(a) for every subset .

(b) for every subset .

Proof. (a) For every subset , we have . So, for every ,

(b) For every subset , we have . So, for every , assume . Then, for some . But means . So, we have .

Clipboard

Exercise. Propose an additional assumption on the function so that (a) under this assumption; (b) under this assumption. Then, prove them. (Hint: the assumption is either " is injective" or " is surjective". Construct some simple examples of injective/surjective functions to make your choice.)

Solution

(a) The assumption is " is injective".

Proof. It suffices to show that , since another subset inclusion is immediate by the proposition above. For every ,

(b) The assumption is " is surjective".

Proof. It suffices to show that . For every , assume . Then, since is surjective, for some . This means since . Combining this with the previous equation, we have for some . Thus, by the definition of image set.


Clipboard

Exercise. Prove or disprove that (a) if , then ; (b) if , then .

Solution
(a)

Proof. Assume . Then by definition of image set, .

(b)

Disproof. Take , , and the function defined by . Then, take and . After that, we have , but .


Cardinalities of sets[edit | edit source]

Recall that a set is finite if it contains a finite number of elements, i.e., or for some . On the other hand, a set is infinite if it is not finite. Previously, we have studied cardinalities of finite sets, and we have left cardinalities of infinite sets undefined. But, it turns out that we can define cardinalities of infinite sets in a more complicated way, using bijective functions.

It may now seem that we can write something like for an infinite set . But it turns out that this is not quite meaningful, and as we shall see, infinite sets can have different cardinalities, or different "sizes". That is, there are different sizes of infinity! (in some sense).

To motivate the definition for the cardinalities of infinite sets, let us first consider a simple example of finite sets.

Example. Let and . We can then clearly observe that , just by counting the number of elements contained by each of them. Alternatively, we can pair off the elements of and in this way:

More precisely, such pairing defines a bijective function given by

This example suggests that for two finite (nonempty) sets and , they have the same cardinality if there exists a bijective function from to (or from to . One such function is given by the inverse function of the bijective function from to .) This leads us to the following definition:

Definition. Two (finite or infinite) sets and have the same cardinality (or are numerically equivalent), written , if and are both empty, or there exists a bijective function from to .

Remark.

  • If two sets have different cardinalities, then we write . Having different cardinalities means ( is nonempty or is nonempty) and (for every function from to , the function is not bijective). (The latter one, in other words, means there does not exist bijective function from to .)
  • It does not matter for the bijective function to be from to , or from to . Since existence of one of them implies the existence of another one, by considering the inverse function.
  • For finite sets (including empty set), this definition is a bit redundant since we can simply count the number of elements in a finite set. But for infinite sets, this definition is the basis for comparing their cardinalities or "sizes".
  • From this definition, we also know that a finite set and an infinite set cannot have the same cardinality, since there must not exist a bijective function from from a finite set to an infinite set (one can show this using proof by contradiction).

Example. Let be the set of all even integers, i.e., . Prove that and are numerically equivalent.

Proof. Define a function by . Now, it remains to prove that it is bijective.

Injective: For every , .

Surjective: For every , choose . Then, .

Clipboard

Exercise. Let be the set of all odd integers.

(a) Prove that and are numerically equivalent.

(b) Prove that and are numerically equivalent.

Solution
(a)

Proof. Define a function by . Now, it remains to prove that it is bijective.

Injective: For every , .

Surjective: For every , choose . Then, .

(b)

Proof. Define a function by . Now, it remains to prove that it is bijective.

Injective: For every , .

Surjective: For every , choose . Then, .



The result in this example may seem strange and counter-intuitive, since seems to be twice as large as , and is a proper subset of , but they turn out to have the same cardinality. Such phenomenon is actually quite common when we deal with the cardinalities of infinite sets.

Fortunately, the numerical equivalence has some nice properties: reflexivity, symmetry and transitivity:

Theorem. For every set ,

  • (reflexivity) is numerically equivalent to .
  • (symmetry) If is numerically equivalent to , then is numerically equivalent to .
  • (transitivity) If is numerically equivalent to , and is numerically equivalent to , then is numerically equivalent to .

Proof.

Reflexivity:

Case 1: is empty. Then, .

Case 2: is nonempty. Then, consider the identity function . We have shown that it is bijective.

Symmetry:

Case 1: and are both empty. Then, must be numerically equivalent to .

Case 2: One of is empty, and another is nonempty. Then, must not be numerically equivalent to , and the result follows.

Case 3: Both and are nonempty. Then, assume is numerically equivalent to . This means there exists a bijective function . Now, consider its inverse function , which is bijective. So, is numerically equivalent to .

Transitivity:

Case 1: are empty. Then, must be numerically equivalent to .

Case 2: Some of are empty, and some are nonempty. Then, it is impossible for to be numerically equivalent to and to be numerically equivalent to . The result follows.

Case 3: are nonempty. Then, assume is numerically equivalent to and is numerically equivalent to . Then, there exist bijective functions and . Thus, their composition is bijective. Hence, and are numerically equivalent.

Now, let us focus on the set , and consider the (infinite) sets having the same cardinality as . We give a special name for such sets:

Definition. (Denumerable sets) A set is denumerable if is numerically equivalent to , i.e., there exists a bijective function .

Remark.

  • Again, the bijective function can be from to , and it does not matter.
  • By the reflexivity of numerical equivalence, itself is denumerable.
  • Since is an infinite set, to be numerically equivalent to it, the set must be infinite. That is, being an infinite set is a necessary (but not sufficient) condition for it to be denumerable.
  • The existence of such bijective function allows us to list out the denumerable set as an infinite list . Thus, we can list out the elements of as , i.e., can be expressed as .
  • Conversely, assuming for every (to ensure injectivity), then we can define a function by , which is bijective, based on the above infinite list.
  • The cardinality of is denoted by , or (read "aleph-zero" or "aleph-naught"). So, the cardinality of every denumerable set is .

Using this definition, we can further define another property of a set:

Definition. (Countable sets) A set is countable if it is either finite or denumerable. A set that is not countable is uncountable.

Remark.

  • Intuitively, we can still "count" the elements in a denumerable set. Also, we can clearly count the elements in a finite set. Hence, we call them as countable sets.
  • From this definition, we know that countably infinite sets are exactly the same as denumerable sets. In some other places, the term "countably infinite sets" is used instead of "denumerable sets".
  • Also, from this definition, we know that a set that is uncountable is necessarily infinite.

Example. Prove that the set is denumerable.

To prove this, we need to construct a bijective function . So, we should have a one-to-one corresponding pairing between positive integers and integers.

Idea: we can label the integers as an infinite "queue":

From this, we get an infinite "queue" of integers: .

Proof. The following pairing suggests a way to construct a bijective function :

More precisely, we can define the function by
Then, it remains to prove that this function is bijective.

Injective: For every ,

Case 1: and are both even. Then, .

Case 2: and are both odd. Then, .

Case 3: and have different parities. Then, it is impossible to have , since is nonnegative, while is negative. The result follows.

Surjective: For every ,

Case 1: is nonnegative. Then, choose , which is even. So, we have .

Case 2: is negative. Then, choose , which is odd. So, we have .



Remark.

  • The function above can also be defined using a single formula:

  • This result is again quite weird, since , but .
  • By the transitivity and symmetry of numerical equivalence, the set of all even integers and the set of all odd integers are also denumerable.
Clipboard

Exercise. Let be the set of all multiples of 3. Prove or disprove that is denumerable.

Solution

Proof. Let us first prove that is numerically equivalent to . Define the function by . We now prove that is bijective:

Injective: For every , .

Surjective: For every , choose . Then, .

Then, since is numerically equivalent to , it follows that is numerically equivalent to . Thus, is denumerable.


We now know that and have the same cardinality. It is then natural to consider the set of all rational numbers, . It appears that is much larger than , so it may seem that should no longer be denumerable, and be uncountable. But it turns out that is also denumerable.

Example.

(a) Prove that the set of all positive rational numbers, is denumerable.

(b) Hence, prove that the set of all rational numbers, is denumerable.

Solution.

(a) First, consider the following diagram:

This diagram arranges all rational numbers in an infinite array. Then, we obtain an infinite list of all rational numbers, following the arrows in the diagram:

Proof. Using the above infinite list, we can then define a bijective function :

In other words, the one-to-one corresponding pairing is
In particular, we skip for the function, since this number is the same as . So, to ensure the injectivity of the function , we need to skip such repeated rational number. (The red numbers in the above diagram are the repeated rational numbers, and we have to skip them all in the definition of the function.) Such function is bijective (since for every , there exists a unique such that ), and so is denumerable.


(b)

Proof. Since is denumerable, we are allowed to write . Similarly, we can write the set of all negative rational numbers as . Hence, we can write the set of all rational numbers as

More precisely, we can define a function by
(similar to the function for proving that is denumerable) In other words, the one-to-one corresponding pairing is
This function can be proved to be bijective (very similar proof as in the proof for is denumerable, but we now consider the indexes of ""), and hence is denumerable.


So, we have proved that . It turns out that even if seems much larger than and , it still has the same cardinality as them. A natural question then arises: is there any uncountable set at all? The answer is yes, and the best known example is the set of all real numbers, . In other words, there does not exist a bijective function from to . Since is uncountable, this suggests that the "size" of is different from the "size" of , i.e., there are different sizes of infinity (in some sense).

Example.

(a) Let with . Construct a bijective function

(b) Using the bijective function in (a), prove that for every with and .

(c) Prove that the open interval is uncountable.

(d) Prove that for every with . (Hint: You can use without proof the fact that the tangent function is bijective.)

Solution.

(a) Define a function by

Now, we prove that is bijective.

Proof.

Injective: For every ,

.

Surjective: For every , choose . Then,

(b)

Proof. By (a), we can construct a bijective function , and also a bijective function . These mean and . Then, by the symmetry and transitivity of numerical equivalence, we have .


(c) One can use the Cantor's diagonal argument to prove it.

(d)

Proof. Since the tangent function is bijective, we have . Also, from part (b), we have for every with , . The result then follows from the transitivity of numerical equivalence.


Remark.

  • Part (d) says in particular . So, this implies that is uncountable, since if it is countable (i.e., denumerable in this case) and , then it means is denumerable, causing a contradiction.

The following results may be useful for comparing denumerable or uncountable sets.

Proposition. Every infinite subset of a denumerable set is denumerable.

Example. Let be the set of all prime numbers. Prove that is denumerable.

Proof. Recall that we have proved there are infinitely many prime numbers. Then, since is an infinite subset of (which is denumerable), it follows that is denumerable.


Clipboard

Exercise. Prove that the set is denumerable.

Proof

Proof. Since the set is an infinite subset of , and is denumerable, it follows that is denumerable.


Example. Prove that for every finite subset of , . (This means that no matter we "take away" how many elements from , as long as the number of elements taken away is finite, then the cardinality is not affected.)

Proof. First, we have , and is denumerable. So, it remains to prove that is infinite. We prove it by contradiction.

Assume to the contrary that is finite. Since is also finite, we have

is finite, contradicting to the fact that is infinite.


Proposition. Let and be sets such that . If is uncountable, then is uncountable.

Remark.

  • Using this result, we can give an alternative proof that is uncountable (we have is uncountable and ).

Example. Prove that is uncountable for every with .

Proof. Since and is uncountable, we conclude that is uncountable.


Remark.

  • Notice that this just says that is uncountable. It does not imply that . As we will see, two uncountable sets may have different cardinalities.

Proposition. If and be denumerable sets, then is denumerable.

Proposition. If and are denumerable sets, then is denumerable.

Clipboard

Exercise. Prove or disprove that if and are denumerable sets, then is denumerable.

Solution

Disproof. Take to be the set of all even numbers and to be the set of all odd numbers. Then, , which is not denumerable.


Example.

  • is denumerable.
  • is denumerable.
Clipboard

Exercise. Prove or disprove each of the following statements:

(a) For every nonempty set , .

(b) The set of all irrational numbers, is uncountable. (Hint: use proof by contradiction)

(c) Every infinite subset of is uncountable.

(d) For every set , if , and are denumerable, then is denumerable.

(e) is uncountable.

(f) The set is denumerable.


Solution
(a)

Proof. Define a function by

It now remains to prove that is bijective.

Injective: For every ,

Surjective: For every , choose . Then,

(b)

Proof. Assume to the contrary that is countable. Since is infinite, this means is denumerable. Also, since is denumerable, it follows that

is denumerable, contradicting to the fact that is uncountable.

(c)

Disproof. Consider the set . Then, define the function by

It remains to prove that is bijective.

Injective: For every , .

Surjective: For every , choose . Then, .

(d)

Proof. Assume and are denumerable. Since and is denumerable, it remains to prove that is infinite. But since is denumerable, and hence infinite, and also , must be infinite. We are done.

(e)

Disproof. Let be the set . Define a function by

It now remains to prove that is bijective.

Injective: For every , .

Surjective: For every , choose . Then, ( must be ).

(f)

Proof. For every , the only real number such that is . Thus, we can express the set as

Then, we can define a function by
It now remains to prove that is bijective.

Injective: For every , .

Surjective: For every , choose . Then, .