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