Final Exam Study Guide

Overview: The final exam is two hours long and will cover material from the entire course. However, it will have some emphasis on material covered since the second midterm – roughly 40-50% on the new material and 50% on the earlier material. This study guide covers only the new material and you should use it together with the first two guides to have the full picture of material to be covered.

Functions (Chapter 12 of Hammack, not including Sections 12.3 and 12.6)

You should be able to do essentially all of the problems in Sections 12.1-12.2 and 12.4-12.5 of Hammack.

Take special note of:

From Section 12.2, take special note of problems 1,2,4, 10, 11, 12, 17, 18 as well as the problems that I assigned from this section.

Again, the problems on page 238 are all relevant.

The problems in Hammack, Section 12.5 are all relevant. In addition, you should be able to prove: - that if \(f\) has an inverse, then \(f\) is bijective; and - if \(f\) is bijective then it has an inverse. See below.

Cardinality (Section 14.1 and 14.2)

Know what it means to say that two sets have the same cardinality. Know the definition of countably infinite and uncountable set. Pay particular attention:

You should be able to produce and explain these arguments.

You should be able to produce other examples of both countable and uncountable sets and explain why they are countable or not. For example, make sure you see why Figure 14.1 shows that \((0,\infty)\) and \((0,1)\) have the same cardinality and what’s involved in proving this.

In addition, the problems in 14.1 and 14.2 are relevant.

Gilbert and Vanstone

Although we have primarily followed Hammack for this portion of the course, there are useful problems in Gilbert and Vanstone and you should be able to do the following problems from Chapter 6, pp. 153-161:

Problems 1-17, 24-28, 35, 37, 38, 41, 99, 100.

Inverse functions

This section is designed to clarify the relationship between inverse functions and bijectivity.

Definition: Let \(f:A\to B\) be a function. An inverse function \(f^{-1}\) to \(f\) is a function \(f^{-1}:B\to A\) such that \(f^{-1}(f(a))=a\) for all \(a\in A\) and \(f(f^{-1}(b))=b\) for all \(b\in B\).

To test your understanding of this definition, prove that if \(f^{-1}\) is an inverse function for \(f\), then \(f\) is an inverse function for \(f^{-1}\).

Theorem: A function \(f:A\to B\) has an inverse function \(f^{-1}\) if and only if \(f\) is bijective.

Proof: Suppose first that \(f\) is bijective. As a set of ordered pairs in \(A\times B\), we have by definition: \[ f=\{(x,f(x)):x\in A\} \] Let \(h=\{(f(x),x):(x,f(x))\in f\}\) be the set of points in \(B\times A\) obtained by switching the entries of each pair in \(f\).

Step 1: \(h\) is in fact a function from \(B\) to \(A\). To check this, we need to know that every element \(b\in B\) occurs as the first element of a pair \((f(x),x)\) exactly one time. So first we check that every element of \(b\in B\) occurs at least once. For this, we need to know that, for every element \(b\in B\), there is an \(x\in A\) so that \(f(x)=b\). But since \(f\) is bijective, it is surjective, and therefore such an \(x\) exists. Next, we need to know that there is only one pair with first element \(b\). Suppose there were two – this would mean that there were \(x\) and \(y\) in \(A\) so that \((f(x),x)\) and \((f(y),y)\) both have \(b\) in the first slot, meaning that \(f(x)=b\) and \(f(y)=b\). Since \(f\) is injective, this can only happen if \(x=y\). So there is only one pair with \(b\) in the first slot. That finishes the proof of this direction. NOTICE HOW WE USE BOTH INJECTIVITY AND SURJECTIVITY

Step 2: Now we need to check that \(h\) is actually \(f^{-1}\). Given \(x\in A\), Let’s look at \(h(f(x))\). For \(f(x)\) we have the pair \((x,f(x))\). For \(h(f(x))\) we need the pair with \(f(x)\) in the first slot, but by definition that is \((f(x),x)\). So \(h(f(x))=x\). Now take \(y\in B\). Then we need to find the pair in \(h\) with \(y\) in its first slot. TO do that, we find \(y=f(x)\), and then the pair is \((y=f(x),x)\). Therefore \(h(y)=x\) and \(f(h(y))=f(x)=y\). So \(h\) satisfies \(h(f(x))=x\) and \(f(h(y))=y\) for \(x\in A\) and \(y\in B\), so \(h=f^{-1}\).

Now suppose that \(f\) has an inverse function \(f^{-1}\). We must show that \(f\) is bijective. Let’s first check that \(f\) is injective. Suppose \(u,v \in A\) and \(f(u)=f(v)\). Then \(f^{-1}(f(u))=f^{-1}(f(v))\) so \(u=v\). Thus \(f\) is injective. Next, we must show that \(f\) is surjective. For that, choose \(b\in B\). We want to find \(x\in A\) so that \(f(x)=b\). Apply \(f^{-1}\) to both sides to get \(f^{-1}(f(x))=f^{-1}(b)\). Let \(x=f^{-1}(b)\). Then \(f(x)=f(f^{-1}(b))=b\) so \(f\) is surjective, and therefore bijective.