Please Login to access more options.


Today

« May 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

31

We'll look at Levi's typed solution to 27. I forgot to do this Friday last week.

Theorem (The Principle Of Mathematical Induction)

If $S$ is a subset of the natural numbers such that

  • 1 is an element of S, and
  • if $k\in S$, then $k+1\in S$

then we must have $S=\mathbb{N}$.

Problem 35: (Induction With The Sum Of The Squares Of The First $n$ Natural Numbers)

Use induction to prove that $\ds 1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}$ for every $n\in \mathbb{N}$.

Standard Induction Hint (This is the same hint for all induction problems):

Let $S$ be the set of natural numbers for which the statement $1^2+2^2+\cdots+n^2 = \frac{n(n+1)(2n+1)}{6}$ is true. We want to show that $S=\mathbb{N}$.

  1. First show that the statement is true if you let $n=1$. (Show $1\in S$.)
  2. Then assume that the statement is true if you let $n=k$ for some $k\in \mathbb{N}$.
  3. Use this assumption to then prove that the statement is true when you let $n=k+1$. (This shows if $k\in S$, then $k+1\in S$.)

You can then apply the principle of mathematical induction to claim $S=\mathbb{N}$.

We have already talked about the union and intersection of sets. Here are two more set operations that we'll need. They are the set complement and the Cartesian product. The next 4 problems have you prove some facts about these set operations.
Definition (Set Complement And Cartesian Product)

Let $A$ and $B$ be sets.

  • The complement of $B$ in $A$ is the set of elements in $A$ that are not in $B$. We can write this in set builder notation as $$A\setminus B = \{x\mid x\in A \text{ and }x\notin B\}.$$
  • The Cartesian product (or cross product, or product) of $A$ and $B$ is the set of ordered pairs $(a,b)$ where $a\in A$ and $b\in B$. We can write the product in set builder notation as $$A\times B = \{(a,b)\mid a\in A\text{ and }b\in B\}.$$
Theorem (Rules For Set Complements)

Let $A$, $B$, and $C$ be sets. Then the following statements are true.

  1. $A\setminus A = \emptyset$
  2. $A\setminus \emptyset = A$
  3. $A\setminus(B\cap C) = (A\setminus B)\cup(A\setminus C)$
  4. $A\setminus(B\cup C) = (A\setminus B)\cap(A\setminus C)$
  5. $A\setminus(B\setminus C) = (A\setminus B)\cup(A\cap C)$

Problem 37: (Set Complements Rules 3 And 4)

Prove rules 3 and 4 of Theorem (Rules For Set Complements).

Problem 38: (Set Complements Rule 5)

Prove rule 5 of Theorem (Rules For Set Complements).

Problem 39: (Distribution With Cartesian Products)

Let $A$, $B$, and $C$ be sets. Prove or disprove each statement.

  1. $(A\cap B)\times C = (A\times C)\cap(B\times C)$
  2. $(A\cup B)\times C = (A\times C)\cup(B\times C)$
We need some problems to help us practice with negations and quantifiers.

Problem 40: (Practice Finding Truth Values With Universal Quantifiers 2)

For each statement below, first write the negation. Then determine whether the statement or the negation is true, and justify your claim. In your work below, assume that $f(x)=x^2$.

  1. $\forall x\in \mathbb{R}$, $\exists y\in \mathbb{R}$ such that $\forall z\in \mathbb{R}$ we have $x+y=z$.
  2. $\forall x,y\in \mathbb{R}$, $\exists z\in \mathbb{R}$ such that $x+z=y$.
  3. $\exists x\in \mathbb{R}$ such that $\forall y\in \mathbb{Z}$, $x<y$ implies $f(x)<f(y)$.
  4. $\forall x,y\in \mathbb{R}$, if $f(x)=f(y)$ then $x=y$.

Problem 41 (More Practice With Universal Quantifiers)

For each $n\in \mathbb{N}$, define $\ds a_n = \frac{n-1}{n}$. Only one of the statements below is true. Rewrite each statement using the quantifiers $\forall$ and $\exists$. Then determine which statement is true, prove that statement is true, and then prove the other statement is false.

  1. For each real number $\varepsilon>0$, there exists $N\in \mathbb{N}$ such that for every $n\in \mathbb{N}$, if $n>N$ then $\ds \left|a_n-0\right|<\varepsilon$.
  2. For each real number $\varepsilon>0$, there exists $N\in \mathbb{N}$ such that for every $n\in \mathbb{N}$, if $n>N$ then $\ds \left|a_n-1\right|<\varepsilon$.

We use Cartesian products all the time without realizing it. When we look for relationships between two groups, we are looking at a subset of a Cartesian product. Family history involves looking at a Cartesian product. For example, we could let $A$ and $B$ both be the set of all humans that have lived on the planet. In our family tree, we often care to know when person $x$ descends from person $y$. One goal of family history is to determine all the pairs $(x,y)$ where person $x$ descends from person $y$. This is a subset of $A\times B$. Similarly, any time we start grouping objects together from two sets, we're formally stating a relationship between the two sets and looking for a subset of the Cartesian product. We call these subsets relations.

Definition (Relation Between Two Sets)

Let $A$ and $B$ be sets. A relation $\mathrm{R}$ between $A$ and $B$ is a subset of $A\times B$, so $\mathrm{R}\subseteq A\times B$. Given $a\in A$ and $b\in B$, we write $(a,b)\in\mathrm{R}$ precisely when $a$ is related to $b$.

A function is one important kind of relation that we've been studying since middle school. Here's a formal definition.

Definition (Function)

Let $A$ and $B$ be sets. A function $f$ from $A$ into $B$, written $f:A\to B$, is a relation between $A$ and $B$ (so $f\subseteq A\times B$) such that for every $x\in A$, there exists a unique $y\in B$ such that $(x,y)\in f$. When $f$ is a function from $A$ into $B$, we'll use the notation $y=f(x)$ or $f(x)=y$ rather than the more cumbersome notation $(x,y)\in f$ used for sets.

Problem 42: (Which Relations Are Functions)

In each number below, you are given a relation $\mathrm{R}$ between a set $A$ and a set $B$. Prove that the relation is a function from $A$ into $B$ or give a counter example to show that the relation is not a function from $A$ into $B$.

  1. Let $\mathrm{R}$ be the relation between $\mathbb{N}$ and $\mathbb{Z}$ given by $(n,m)\in \mathrm{R}$ if and only if $n^2=m$.
  2. Let $\mathrm{R}$ be the relation between $\mathbb{N}$ and $\mathbb{Z}$ given by $(n,m)\in \mathrm{R}$ if and only if $n=m^2$.
  3. Let $\mathrm{R}$ be the relation between $\mathbb{R}\times\mathbb{R}$ and $\mathbb{R}$ given by $((x,y),z)\in \mathrm{R}$ if and only if $x+y=z$.
  4. Let $\mathrm{R}$ be the relation between $\mathbb{R}\times\mathbb{R}$ and $\mathbb{R}$ given by $((x,y),z)\in \mathrm{R}$ if and only if $x/y=z$.
Definition (Domain And Codomain)

Let $A$ and $B$ be sets and let $f$ be a function from $A$ into $B$, so we have $f:A\to B$.

  • We call the set $A$ the domain of $f$.
  • We call the set $B$ the codomain of $f$.
Definition (Injective, Surjective, And Bijective)

Let $D$ and $R$ be sets and let $f$ be a function from $D$ into $R$, so we have $f:D\to R$.

  • We say that $f$ is injective (or one-to-one) if and only if for every $a,b\in D$ we have $f(a)=f(b)$ implies $a=b$.
  • We say that $f$ is surjective (or onto) if and only if for every $y\in R$ there exists an $x\in D$ such that $y=f(x)$.
  • We say that $f$ is bijective if and only if the function $f$ is both injective and surjective.

Problem 43: (Practice With Injective And Surjective)

For each function below, state the domain and codomain, determine if the function is injective, and then determine if the function is surjective.

  1. Let $f:\mathbb{R}\to\mathbb{R}$ be defined by $f(x)=x^2$.
  2. Let $f:[0,\infty)\to\mathbb{R}$ be defined by $f(x)=x^2$.
  3. Let $f:\mathbb{R}\to [0,\infty)$ be defined by $f(x)=x^2$.
  4. Let $f:[0,\infty)\to[0,\infty)$ be defined by $f(x)=x^2$.

As always, remember to justify each claim you make.

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

Problem 44: (Induction With Sum Of Odds)

Notice that $$ \begin{align} 1&=1 \\ 1+3&=4 \\ 1+3+5&=9 \\ 1+3+5+7&=16 \\ 1+3+5+7+9&=25. \end{align} $$ Make a conjecture about the sum of odd numbers by giving a general formula for what you see above. Then prove that your formula is valid by using mathematical induction.

Problem 45: (Relationships Between Subsets, Infimums, And Supremums)

Suppose that $S$ and $T$ are nonempty bounded subsets of $\mathbb{R}$ and that $S\subseteq T$. Prove that $$\inf T \leq \inf S \leq \sup S\leq \sup T.$$

Definition (Epsilon Neighborhoods And Deleted Neighborhoods)

Given $\varepsilon>0$, an $\varepsilon$-neighborhood of the real number $x$ is the interval $$N_{\varepsilon}(x) = (x-\varepsilon,x+\varepsilon) = \{y\in \mathbb{R}\colon |x-y|<\varepsilon\}.$$ A deleted $\varepsilon$-neighborhood of $x$ is the same interval minus the point $x$, which we'll write as $$N^*_{\varepsilon}(x) = N_{\varepsilon}(x)\setminus\{x\} = (x-\varepsilon,x)\cup(x,x+\varepsilon) = \{y\in \mathbb{R}\colon 0<|x-y|<\varepsilon\}.$$

Problem 46: (Practice With Neighborhoods)

Consider the interval $S=(1,8)$.

  1. Find real numbers $x$ and $\varepsilon$ so that $S=N_\varepsilon(x)$.
  2. Find real numbers $x$ and $\varepsilon$ so that $N_\varepsilon(x)$ is a proper subset of $S$.
  3. For every $x\in S$, give a formula for $\varepsilon$ so that $N_\varepsilon(x)\subseteq S$. Your choice of $\varepsilon$ will depend on $x$.
Definition (Interior Point, Open Set, Closed Set)

Let $S\subseteq \mathbb{R}$.

  • We say that $x$ is an interior point of $S$ if and only if there exists an $\varepsilon>0$ such that $N_\varepsilon(x)\subseteq S$.
  • The interior of $S$ is the collection of interior points of $S$.
  • We say that $S$ is an open set if and only if for every $x\in S$ there exists an $\varepsilon>0$ such that $N_\varepsilon(x)\subseteq S$ (so every point in $S$ is an interior point, or equivalently $S$ equals the interior of $S$).
  • We say that $S$ is a closed set if and only if the complement $\mathbb{R}\setminus S$ is open.

Problem 47: (Open Intervals Are Open Sets)

Prove that if $a$ and $b$ are real numbers such that $a<b$, then the interval $S=(a,b)$ is an open set.

Problem 48: (Closed Intervals Are Closed Sets)

Prove that if $a$ and $b$ are real numbers such that $a<b$, then the interval $ S=[a,b] $ is a closed set.

For more problems, see AllProblems