# Mathematical Proof/Functions

## 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.

- From the definition, every element has an

- 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 ).

**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.)

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

**Example.**
Let and . Then,

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:

- What are the domain and codomain?
- 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*

**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.

(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

**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 ?

(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 ,

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

We have .

**Proof.**
First, for every ,

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 .

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

( 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.

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

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 .

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

There exist such that and .

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

**Proof.**
For every ,

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

**Disproof.**
Since , is not injective.

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

**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 ,

*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.

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

**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, .

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

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

**Exercise.**
*Prove* that the function defined by is surjective.

**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.

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

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

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

**Proof.**

**Injective**: For every , .

**Surjective**: For every , choose . Then, .

**Exercise.**
A function is defined by

**Proof.**

**Injective**: For every ,

**Surjective**: For every , choose . Then,

**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.

**Disproof.**
Since , is not injective.

**Disproof.**
Take . Then, for every , .

**Disproof.**
Since , is not injective.

**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

*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

**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 ,

Also,

**Example.**
Let and .
Consider the functions , and defined 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

*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 ,

**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:

(given) | ||
---|---|---|

injective | injective | injective/not injective |

surjective | surjective | surjective/not surjective |

bijective | injective | surjective |

**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.

**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 .

**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

*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.

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

(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

*function*always a

*function*from to itself? The answer is, indeed, no. Consider the following example.

**Example.**
Let and . Consider the function defined by

*inverse relation*(we are

*not*calling it inverse function) of , denoted by , is

*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

**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.

**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,

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,

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.

**Exercise.**
Consider the function defined by

(b) Determine the formula for inverse function, .

**Proof.**

**Injective**: For every ,

**Surjective**: For every , choose . Then,

(b) Since for every , we have

**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*

*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

**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).

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

(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 ,

**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.)

(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.

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

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

**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