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: We'll start today letting you ask any questions you have about the Marble Problem.

I'd love to have each of you have something to present today. Here is who we'll have present.

  • 52 -
  • 53.2 -
  • 56 -
  • 57 -
  • 58.1 -
  • 58.2 -
  • 59 -
  • 60 -
  • 61 -

The following students were absent

Exercise (The Marble Problem)

This problem is here to answer Jai's question about why we need $k\geq 1$ and not just $k>1$ (or equivalently $k\geq 4$ and not just $k>4$) in our induction hypothesis. Why must we include the base case in our induction hypothesis. This problem is an adaption of problem 10.15(a) on page 104 of Lay's book "Analysis - With an Introduction to Proof."

Consider the following conjecture.

For each $n\in\mathbb{N}$, let $P(n)$ be the statement, "Any collection of $n$ marbles consists of marbles of the same color." then $P(n)$ is true for all $n\in\mathbb{N}$.

Find the flaw in the following proof.

We know that $P(1)$ is true because any collection of 1 marble consists of marbles of the same color, namely the color of the only marble. Now assume, for some $k\in\mathbb{N}$ with $k>1$ that $P(k)$ is true. This means that any collection of $k$ marbles must consist of marbles of the same color. Consider a collection $C$ of $k+1$ marbles. Pick one of those marble (say marble $x$) and remove it. We now have a collection $C\setminus\{x\}$ that has $k$ marbles. By our induction hypothesis, we know that these marbles must all have the same color.
Note that $k>1$ means $k+1\geq 3$. So there are at least 2 marbles left in $C\setminus\{x\}$. Pick two of them and call them marbles $y$ and $z$. Note that the marbles $x$, $y$, and $z$ are 3 different marbles.
Currently, we know that $y$ and $z$ must have the same color. Now add back marble $x$ and remove marble $y$. This leaves us with the collection $C\setminus\{y\}$ which has $k$ marbles. By our induction hypothesis, all of these marbles must have the same color, which means marbles $x$ and $z$ must have the same color. We now know that $y$ and $z$ have the same color, and we know that $x$ and $z$ have the same color. This means that $x$ and $y$ must have the same color as well. In particular, this means that all the marbles in the collection $C$ must have the same color (the color of marble $z$). This completes the proof that any collection of $k+1$ marbles must have the same color. By induction, we conclude that for any $n\in\mathbb{N}$, any collection of $n$ marbles consists of marbles of the same color.

Click to see a solution. Make sure you have an answer before you reveal this.

The flaw is that we assumed for some $k>1$ that statement $P(1)$ is true. We don't know $P(k)$ is true for any $k>1$, so we have made a faulty assumption. Any conclusion we draw from this faulty assumption is vacuously true. What????? Statement $P(2)$ is false. Statement $P(2)$ does not follow from statement $P(1)$, precisely because there are not 3 different marbles in a bag with only two marbles. Pick one marble out of the bag, and you definitely have a collection with one marble of the same color. Put that marble back in and pull out the other, and statement $P(1)$ is still true. However, you don't have a third marble sitting around to compare to the ones you pulled out. Note that $P(1)$ does not imply $P(2)$, and in fact statement $P(2)$ is flat out false. The implication "if $P(2)$ then $P(3)$" is vacuously true. The implication "if $P(k)$ then $P(k+1)$" is vacuously true for every $k>1$. The implication is flat out false if $k=1$. We failed to prove that $P(k)$ implies $P(k+1)$ for every integer $k\geq 1$. We succeeded with just about all of them, but missed the one case when $k=1$.

Here's another way to explain it. Suppose you have a line of infinitely many dominoes. You have set the dominoes up so that if domino $k$ falls (for some $k>1$), then domino $k+1$ falls. Reread the previous sentence for several values of $k$.

  • if domino 2 falls, then domino 3 falls.
  • if domino 3 falls, then domino 4 falls.
  • if domino 4 falls, then domino 5 falls.
  • ...

A natural question should arise, "Does domino 2 fall if domino 1 falls?" By omitting $k=1$ from our induction assumption, we don't know if this is true or not. Now, suppose Sally comes by and knocks over the first domino. Do all the dominoes fall? We don't know. Did domino 1 knock over domino 2, or is domino 2 still standing? Who knows? The problem doesn't tell us, so we can't say anything. The induction process stops at the second domino.

When we make our induction assumption, we say "For some $k\in \mathbb{N}$ (which means $k\geq 1$)". If the base case is $n=4$, then we must say "For some $k\geq 4$ with $k\in\mathbb{N}$". Failing to include the base case in our assumption (using just $k>4$) will lead to us missing the second domino in our chain, which is the same problem as the marble dilemma above. We would know the 4th domino falls, but not if the 5th falls, and so we can't say anything about whether or not the 6th domino and beyond fell.

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.

When we have shown that something holds true for two objects, we can often 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.
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 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.

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