Please Login to access more options.


Today

« June 2018 »

Sun

Mon

Tue

Wed

Thu

Fri

Sat

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

From Ben: Here is who we'll have present.
  • 50 - Emilee, Br. Woodruff
  • 52 - James
  • 53.2 -
  • 54.1 -
  • 54.2 - Brent
  • 55 - Jai
  • 56 -

The following students were absent

  • Jason
Definition (Cardinality Of A Finite Set)

If $A$ is a finite set, then the cardinality of $A$, written $|A|$, is the number of distinct elements of $A$.

Problem 50: (Induction And Cardinality Of Cartesian Products)

If $A$ and $B$ are finite sets, then we have discussed in class why the cardinality of $A\times B$ is given by $$|A\times B|=|A|\cdot |B|.$$ Use induction to prove that for every $n\in \mathbb{N}$ if $A_1, A_2, \ldots, A_n$ are finite sets, then we have $$|A_1\times A_2\times\cdots\times A_n|=|A_1|\cdot|A_2|\cdots|A_n|.$$

The first part of your proof should begin something like the following:
For each $n\in\mathbb{N}$ let $P(n)$ be the statement $$\text{"if $A_1, A_2, \ldots, A_n$ are finite sets, then we have } |A_1\times A_2\times\cdots\times A_n|=|A_1|\cdot|A_2|\cdots|A_n|."$$ We know that $P(1)$ is true because .... Now assume that for some $k\in \mathbb{N}$ that $P(k)$ is true. This means we have assumed that "if ... then ...". We must prove that "if ... then ...". We've got to prove an if-then statement is true, so we should start by assuming the antecedent is true. So assume that $A_1, A_2, \ldots, A_k, A_{k+1}$ are finite sets. We now have to show that ... is true. (Then continue your work. Clearly I've left some holes to be filled in above.)

Let's now examine a problem related to limits of sequences. Some of you noticed in the definition of a limit of a sequence that we used the word "a" instead of "the." What we will prove now is that when a sequence converges, we can talk about "the" limit of the sequence instead of just "a" limit of the sequence.

Problem 52: (A Convergent Sequence Has A Unique Limit)

Let $(a_n)$ be a convergent sequence of real numbers. Prove that $(a_n)$ converges to a unique real number.

Note: The general way to prove something is unique is to suppose that there are two of those things, and then prove they must be equal. We need to prove that if $(a_n)$ converges to both $A$ and $B$, then we must have $A=B$. The contrapositive of this statement may be easier to work with, or possibly a proof by contradiction instead.

We now turn our attention to open sets. How does the union and intersection set operation behave when working with two open sets?

Problem 53: (Unions And Intersections Of Two Opens Sets Are Open)

Let $U_1$ and $U_2$ be open sets. Show that $U_1\cup U_2$ and $U_1\cap U_2$ are open sets.

Now that we've seen that unions and intersections of two open sets are open, what happens if we have more than two open sets? We need a formal definition of how to create a union and intersection of any collection of sets.

Definition (Unions And Intersections Of Arbitrarily Many Sets)

Suppose we have a large collection of sets. Each set has been given a name of the form $A_j$ where $j$ is an element of some nonempty set $J$. We call the collection $\mathrm{A} = \{A_j\mid j\in J\}$ an indexed family of sets with index set $J$. The union and intersection of all the sets in $\mathrm{A}$ are the sets given by $$\bigcup_{j\in J}A_j = \{x\mid x\in A_j \text{ for some } j\in J\}\text{ and } \bigcap_{j\in J}A_j = \{x\mid x\in A_j \text{ for every } j\in J\}.$$ When $J=\mathbb{N}$, then we'll often write the union and intersection using the notation $$\bigcup_{n\in \mathbb{N}}A_n = \bigcup_{n=1}^\infty A_n = A_1\cup A_2\cup A_3\cup\cdots\text{ and } \bigcap_{n\in \mathbb{N}}A_n = \bigcap_{n=1}^\infty A_n = A_1\cap A_2\cap A_3\cap\cdots.$$

Problem 54: (Unions And Intersections Of Nested Sets)

Let $n$ be a natural number and suppose that $A_1,A_2,\ldots, A_n$ are sets. Suppose also that $A_1\supseteq A_2\supseteq A_3\supseteq \cdots \supseteq A_n$.

  1. Prove that $\ds\bigcup_{i=1}^n A_i = A_1$.
  2. Make a conjecture that simplifies $\ds\bigcap_{i=1}^n A_i$. Then prove your conjecture.
It's never a bad idea to start looking at a problem that involves arbitrary things by first considering specific examples. Make up some examples with 3 or 4 sets. What do you notice happening? Then make your conjecture and prove it.
Exercise (Induction With The Sum Of Cubes)

Prove that for every $n\in \mathbb{N}$, we have $$1^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2.$$

Click to see a solution.

Consider the set $$S=\left\{n\in\mathbb{N}\mid 1^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2\right\}.$$ We need to prove that $S=\mathbb{N}$. We proceed by induction. We know $1\in S$ because $1^3 =1$ and $\left(\frac{1(1+1)}{2}\right)^2 = (1)^2=1$. Assume for some $k\in \mathbb{N}$ that $k\in S$, which means we've assumed that $$1^3+2^3+\cdots+k^3=\left(\frac{k(k+1)}{2}\right)^2.$$ We need to prove that $k+1\in S$, which means we need to prove that $$1^3+2^3+\cdots+k^3+(k+1)^3=\left(\frac{(k+1)((k+1)+1)}{2}\right)^2.$$ We'll start with the expression $1^3+2^3+\cdots+k^3+(k+1)^3$ and modify it to obtain the right hand side of the equation above. We now compute $$\begin{align} 1^3+2^3+\cdots+k^3+(k+1)^3 &= \left(1^3+2^3+\cdots+k^3\right)+(k+1)^3 && (\text{group the first $k$ terms})\\ &= \left(\frac{k(k+1)}{2}\right)^2+(k+1)^3 && (\text{substitute using our assumption})\\ &= \frac{k^2(k+1)^2}{4}+\frac{4(k+1)^3}{4} && (\text{prepare to combine fractions})\\ &= \frac{(k+1)^2(k^2+4(k+1))}{4}&& (\text{combine and factor})\\ &= \frac{(k+1)^2(k^2+4k+4)}{4}&& (\text{expand})\\ &= \frac{(k+1)^2(k+2)^2}{4}&& (\text{factor})\\ &= \left(\frac{(k+1)((k+1)+1)}{2}\right)^2&& (\text{note $k+2=(k+1)+1$}) .\end{align}$$ This shows that if $k\in S$, then $k+1\in S$. By mathematical induction, we know that $S=\mathbb{N}$. This prove that for every $n\in \mathbb{N}$, we have $$1^3+2^3+\cdots+n^3=\left(\frac{n(n+1)}{2}\right)^2.$$

The formal principle of induction allows us to show that a set $S$ equals $\mathbb{N}$. This requires that we show $1\in S$ and if $k\in S$, then $k+1\in S$. What if the statement we wish to show is not true for every natural number, but is true for every natural number past some base case. So suppose we know that $4\in S$ and if $k\in S$ with $k\geq 4$, then $k+1\in S$. Can we conclude that $S$ contains every natural number greater than or equal to 4? If you examine the proof we used for induction, you'll find the quick answer to this question is $S$. So we now have a new form of induction.

An Alternate Form of Induction
Suppose $S$ is a set of natural numbers such that
  • $b\in S$ and
  • if $k\in S$ with $k\geq b$, then $k+1\in S$.
Then $S$ contains every integer greater than or equal to $b$.

Problem 55: (Induction And $2^n\geq n^2$)

Use induction to prove that for every $n\in \mathbb{N}$ except for $n=3$ we have $2^n\geq n^2$.

When we have shown that something holds true for two objects, we can often use use induction to prove the same fact holds true for any finite collection of those objects. The next problem has you do this.

Problem 56: (Unions And Intersections Of Finitely Many Opens Sets Are Open)

Use induction to prove for each $n\in \mathbb{N}$ if $U_1$, $U_2$, ..., $U_n$ are open sets, then $\ds \bigcup_{i=1}^n U_i$ is an open set.

A similar proof will show that for each $n\in \mathbb{N}$ if $U_1$, $U_2$, ..., $U_n$ are open sets, then $\ds \bigcap_{i=1}^n U_i$ is an open set.

Let's now return to studying functions.

Definition (Image $f(A)$ and Preimage $f^{-1}(B)$)

Consider the function $f:X\to Y$. Let $A$ be a subset of the domain $X$ and let $B$ be a subset of the codomain $Y$.

  • The image of $A$ under $f$ is the subset of $Y$ defined by $$ \begin{align} f(A) &=\{y\in Y\mid y=f(a) \text{ for some }a\in A\}\\ &=\{f(a)\mid a\in A\} .\end{align}$$ This means that $y\in f(A)$ if and only if $y=f(a)$ for some $a\in A$.
  • The preimage (or inverse image) of $B$ under $f$ is the subset of $X$ defined by $$ \begin{align} f^{-1}(B) &=\{x\in X\mid f(x)=b \text{ for some }b\in B\}\\ &=\{x\in X\mid f(x) \in B\} .\end{align}$$ This means that $x\in f^{-1}(B)$ if and only if $f(x)=b$ for some $b\in B$ if and only if $f(x)\in B$. Note that when the set $B$ contains a single element, then we write $f^{-1}(b)$ rather than $f^{-1}(\{b\})$.

We were just introduced to a new definition. We should try to apply this definition to a function we understand. The next problem has you do this.

Problem 57: (Function Notation With Sine)

Consider the function $f:\mathbb{R}\to\mathbb{R}$ defined by $f(x)=\sin x$.

  1. What are the sets $f(\mathbb{R})$ and $f([0,\pi/2))$?
  2. What are the sets $f^{-1}(0)$ and $f^{-1}([0,\pi/2))$?
  3. Find a set $A\subseteq \mathbb{R}$ so that $g:A\to \mathbb{R}$ defined by $g(x)=\sin(x)$ is injective.
  4. Find a set $B\subseteq \mathbb{R}$ so that $h:A\to B$ defined by $h(x)=\sin(x)$ is surjective.

The following theorem lists many facts that we could prove about the image and preimage of a function. We'll take some time to prove a few of them, but not all of them in class. You should be able to prove each of them for the final exam.

Theorem (Image And Preimage Properties)

Consider the function $f:X\to Y$.

  1. If $A\subseteq X$, then we have $A\subseteq f^{-1}(f(A))$.
  2. If $B\subseteq Y$, then we have $f(f^{-1}(B))\subseteq B$.
  3. If $A_1\subseteq X$ and $A_2\subseteq X$, then we have $f(A_1\cap A_2)\subseteq f(A_1)\cap f(A_2)$.
  4. If $A_1\subseteq X$ and $A_2\subseteq X$, then we have $f(A_1\cup A_2)=f(A_1)\cup f(A_2)$.
  5. If $B_1\subseteq Y$ and $B_2\subseteq Y$, then we have $f^{-1}(B_1\cap B_2)=f^{-1}(B_1)\cap f^{-1}(B_2)$.
  6. If $B_1\subseteq Y$ and $B_2\subseteq Y$, then we have $f^{-1}(B_1\cup B_2)=f^{-1}(B_1)\cup f^{-1}(B_2)$.
  7. We have $f(A)\subseteq B$ if and only if $A\subseteq f^{-1}(B)$.
  8. If $A_1\subseteq A_2\subseteq X$, then we have $f(A_1)\subseteq f(A_2)$.
  9. If $B_1\subseteq B_2\subseteq Y$, then we have $f^{-1}(B_1)\subseteq f^{-1}(B_2)$.
  10. If $B\subseteq Y$, then $f^{-1}(Y\setminus B)=X\setminus f^{-1}(B)$.

Problem 58: (Image And Preimage Properties 1 And 2)

Prove properties 1 and 2 for images and preimages. So prove for a function $f:X\to Y$ both of the following.

  1. If $A\subseteq X$, then $A\subseteq f^{-1}(f(A))$.
  2. If $B\subseteq Y$, then $f(f^{-1}(B)\subseteq B$.

Then give an example of a function $f:X\to Y$ and subsets $A\subseteq X$ and $B\subseteq Y$ where $A\neq f^{-1}(f(A))$ and $B\neq f(f^{-1}(B))$.

Problem 59: (Image And Preimage Property 3)

Prove property 3 for images. So let $f:X\to Y$. Then prove that

  • If $A_1\subseteq X$ and $A_2\subseteq X$, then we have $f(A_1\cap A_2)\subseteq f(A_1)\cap f(A_2)$.

Finish by proving that if $f$ is injective, then equality holds.

Problem 60: (Image And Preimage Property 6)

Prove property 6 for preimages. So let $f:X\to Y$. Then prove that

  • If $B_1\subseteq Y$ and $B_2\subseteq Y$, then we have $f^{-1}(B_1\cup B_2)=f^{-1}(B_1)\cup f^{-1}(B_2)$.

Problem 61: (Image And Preimage Property 7)

Prove property 7 for preimages. So let $f:X\to Y$. Then prove that

  • We have $f(A)\subseteq B$ if and only if $A\subseteq f^{-1}(B)$.

Problem 62: (The Union And Intersection Of Infinitely Many Open Sets)

For each $n\in\mathbb{N}$, let $A_n = \left(0,1+\frac{1}{n}\right)$.

  1. What are the sets $\ds \bigcup_{n=1}^\infty A_n$ and $\ds \bigcap_{n=1}^\infty A_n$?
  2. Prove your claims.

Problem 63: (The Union And Intersection Of Infinitely Many Closed Sets)

For each $x$ such that $3<x<4$, let $A_x = [2,x]$.

  1. State an interval that equals each of $\ds \bigcup_{3<x<4} A_x$ and $\ds \bigcap_{3<x<4} A_x$.
  2. Prove your claims.
Definition (Function Composition)

Consider the functions $f:A\to B$ and $g:C\to D$. When $B\subseteq C$, then we know for each $a\in A$ that $f(a)\in B\subseteq C$. Since $f(a)\in C$, we can compute the quantity $g(f(a))$. If $B\subseteq C$, then we define the composition of $g$ and $f$ to be the new function $g\circ f : A\to D$ defined by $$(g\circ f)(a) = g(f(a)).$$

Problem 64: (The Composition Of Surjective Functions Is Surjective)

Let $A$, $B$, and $C$ be sets, and consider the functions $f:A\to B$ and $g:B\to C$. Prove that if both $f$ and $g$ are surjective, then $g\circ f$ is surjective.

Exercise (Unions And Intersections Of Opens Sets)

Prove each of the following:

  1. The union of any collection of open sets is open.
  2. The intersection of finitely many open sets is open.

Click to see a solution.

Let's first prove that the union of any collection of open sets is open. Let $J$ be a set and for each $j\in J$ let $U_j$ be an open set. This gives us a way to talk about an arbitrary collection of open sets. We must prove that $\ds\bigcup_{j\in J}U_j$ is an open set. So pick $\ds x \in \bigcup_{j\in J}U_j$. Since $x$ is an element of this union, we know that $x\in U_j$ for some $j\in J$. Since $U_j$ is an open set, we know we can pick $\varepsilon>0$ such that $N_\varepsilon (x)\subseteq U_j$. Since we know $U_j\subseteq \ds\bigcup_{j\in J}U_j$, this means $N_\varepsilon(x)\subseteq \ds\bigcup_{j\in J}U_j$. Since this entire argument holds for any $x\in \ds\bigcup_{j\in J}U_j$, we have shown that $\ds\bigcup_{j\in J}U_j$ is an open set.

We now prove that the intersection of finitely many open sets is open. One way to prove this is to refer to a previous problem where we used induction to prove this is true. Here is another proof. Let $n\in\mathbb{N}$ and suppose $U_1, U_2, \ldots, U_n$ are open sets. Let $x\in \ds\bigcap_{i=1}^n U_i$. To complete this proof, we must produce a postive $\varepsilon$ and prove that $N_{\varepsilon}(x)\subseteq \ds\bigcap_{i=1}^n U_i$. Pick $i\in\{1,2,\ldots,n\}$. Because $x\in \ds\bigcap_{j=1}^n U_j$, we know that $x\in U_i$. We assumed that $U_i$ is open, which means we can pick $\varepsilon_i$ such that $N_{\varepsilon_i}(x)\subseteq U_i$. Since the argument above holds for each relevant $i$, we pick $\varepsilon_i$ for each relevant $i$ so that $N_{\varepsilon_i}(x)\subseteq U_i$. Now comes the key part, namely we let $\varepsilon$ be the smallest of these positive values, which gives $$\varepsilon = \min\{\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n \}.$$ Clearly $\varepsilon>0$ by construction. In addition, because of how we defined $\varepsilon$, we know $N_{\varepsilon}(x)\subseteq N_{\varepsilon_i}(x)$ for each relevant $i$. This fact, together with the fact that $N_{\varepsilon_i}(x)\subseteq U_i$ for each relevant $i$, means we know $N_{\varepsilon}(x)\subseteq U_i$ for each relevant $i$. This fact proves that $N_{\varepsilon}(x)\subseteq \ds\bigcap_{i=1}^n U_i$, as needed. Our proof is complete (and should look very similar to the proof for two open sets).

Notice that the min function in the proof above can fail to produce a positive $\varepsilon$ if there is an infinite number of open sets. There is no guarantee that a minimum will even exist when a set has infinitely many elements. The problem before this exercise clearly shows us that the intersection of infinitely many sets does not have to be open, as we proved $\ds\bigcap_{n=1}^\infty \left(0,1+\frac{1}{n}\right) =(0,1] $.

Problem 65: (The Composition Of Injective Functions Is Injective)

Let $A$, $B$, and $C$ be sets, and consider the functions $f:A\to B$ and $g:B\to C$. Prove that if both $f$ and $g$ are injective, then $g\circ f$ is injective.

Problem 66: (Triangle Inequality)

For any real numbers $u$ and $v$, let $d(u,v)$ be the distance between $u$ and $v$, which means $d(u,v)=|u-v|=|v-u|$.

  1. Let $a,b,c\in\mathbb{R}$. Prove that $d(a,b)\leq d(a,c)+d(c,b)$.
  2. Let $x,y\in\mathbb{R}$. Use the previous result to prove that $|x+y|\leq |x|+|y|$.
Both facts above we call the triangle inequality. Both facts basically state that the distance from point $A$ to point $B$ is less than or equal to the distance traveled if you take the shortest route from $A$ to $B$ that must also pass through a third point $C$. Equality holds if $C$ is already on the shortest path from $A$ to $B$, otherwise the distance must increase.

We have two directions we can head. We can study inverses of functions next (proving that a function has an inverse if and only if it is bijective), or we can study limits more (working with more complicated sequences, and then general theorems about sequences in general). We'll chat about this as we get closer to it.

For more problems, see AllProblems