Please Login to access more options.
|
Sun |
Mon |
Tue |
Wed |
Thu |
Fri |
Sat |
Definition (The Quantifiers $\forall$ and $\exists$)
- We'll use $\forall$ as shorthand in place of the phrases "for every," "for all," "for each," or any equivalent expression that suggest for every possible case. We call $\forall$ the universal quantifier.
- We'll use $\exists$ as shorthand in place of the phrases "there exists," "there is at least one," or any equivalent expression that suggest there is at least one possible case. We call $\exists$ the existential quantifier.
These symbols are used often in open discussions, presentations, and informal work. However, when publishing formal papers, it is common practice to avoid using these symbols and instead just write the words.
Problem 26: (Negating Quantifiers)
Rewrite each statement below using the quantifiers $\forall$ and/or $\exists$. Then write the negation of each statement.
- For each $x\in\mathbb{N}$ we have $x>4$.
- There exists $y\in \mathbb{R}$ such that $y\in (-3,4)$.
- For every $\varepsilon>0$, there exists a $\delta>0$ such that $0<|x-c|<\delta$ implies $\left|f(x)-L\right|<\varepsilon$.
Problem 27: (Practice Finding Truth Values With Universal Quantifiers)
Determine the truth value of each statement below. Be prepared to justify your claim.
- $\forall x\in \mathbb{R}$ and $\forall y\in \mathbb{R}$, $\exists z\in \mathbb{R}$ such that $x+y=z$.
- $\forall x\in \mathbb{R}$ and $\forall y\in \mathbb{R}$, $\exists z\in \mathbb{R}$ such that $xz=y$.
- $\forall x\in \mathbb{R}$, $\exists y\in \mathbb{R}$ such that $\forall z\in \mathbb{R}$, $z>y$ implies $z>x+y$.
- $\exists x\in \mathbb{R}$ such that $\forall y\in \mathbb{R}$, $\exists z\in \mathbb{R}$ such that $z>y$ implies $z>x+y$.
Definition (Maximum and Minimum)
Let $S\subseteq \mathbb{R}$.
- We say $m$ is a minimum of $S$ if $m$ is a lower bound for $S$ and $m\in S$. We write $\min S$ for the minimum of $S$.
- We say $m$ is a maximum of $S$ if $m$ is an upper bound for $S$ and $m\in S$. We write $\max S$ for the maximum of $S$.
Problem 28: (Minimums And Maximums Are Unique)
Prove that a minimum of set $S$, if it exists, is unique. In other words, prove that if $m_1$ and $m_2$ are both minimums of $S$, then we must have $m_1=m_2$. A similar proof will show that maximums are unique.
Problem 29: (Relation Between Minimums And Infimums)
Suppose $S$ is a set of real numbers.
- If $m$ is the minimum of $S$, must $m$ be the infimum of $S$? Prove your claim.
- If $m$ is the infimum of $S$, must $m$ be the minimum of $S$? Prove your claim.
(Similar facts hold true for the maximum and supremum of a set.)
The next theorem lists several facts about set unions and intersections that we would like to refer to from here on out.
Theorem (Union And Intersection Properties)
Let $A,B,C$ be sets. Then the following facts are true.
- $A\subseteq A$ (Every set is a subset of itself.)
- $A\subseteq A\cup B$ (A set is a subset of the union of itself and another set.)
- $A\cap B\subseteq A$ (The intersection of two sets is a subset of the first set.)
- $A\cup B = B\cup A$ (Set unions are commutative.)
- $A\cap B = B\cap A$ (Set intersections are commutative.)
- $A\cup (B\cup C)=(A\cup B)\cup C$ (Set unions are associative.)
- $A\cap (B\cap C)=(A\cap B)\cap C$ (Set intersections are associative.)
- $A\cup (B\cap C)=(A\cup B)\cap(A\cup C)$
- $A\cap (B\cup C)=(A\cap B)\cup(A\cap C)$
The last two we call the distributive laws for unions and intersections.
Take some time to prove that each of the statements above is true. The next exercise includes several of the proofs. I'll leave some for you to prepare for class.
Exercise (Union And Intersection Properties)
Prove the statements in the Union and Intersection Properties theorem.
Click to see a solution.
- To prove $A\subseteq A$, let $a\in A$. Then clearly $a\in A$ which means $A\subseteq A$ as desired.
- We now prove $A\subseteq A\cup B$. Let $a\in A$. Then clearly $a\in A$ or $a\in B$. This means that $a\in A\cup B$, which proves that $A\subseteq A\cup B$.
- We now prove $A\cap B\subseteq A$. Let $x\in A\cap B$. This means $x\in A$ and $x\in B$. In particular, notice that we know $x\in A$. This completes the proof that $A\cap B\subseteq A$.
- Let $x$ be a real number. Let $P$ be the statement $x\in A$, and let $Q$ be the statement $x\in B$. Note that the statements $P\vee Q$ and $Q\vee P$ are logically equivalent from a truth table. The rule $A\cup B=B\cup A$ immediately follows. Alternately, we can prove this fact using the standard technique. Let $y\in A\cup B$. Then we know $y\in A$ or $y\in B$. This is equivalent to $y\in B$ or $y\in A$, which means $y\in B\cup A$. Hence we've shown $A\cup B\subseteq B\cup A$. The proof that $B\cup A\subseteq A\cup B$ is similar. Thus $A\cup B= B\cup A$.
- The proof that $A\cap B=B\cap A$ is almost identical to the previous.
- This is the next problem.
- This is the next problem.
- We now prove that $A\cup(B\cap C) = (A\cup B)\cap (A\cup C)$. We first show $A\cup(B\cap C) \subseteq (A\cup B)\cap (A\cup C)$. Let $x\in A\cup (B\cap C)$. This means that $x\in A$ or $x\in B\cap C$. We must show that $x\in A\cup B$ and that $x\in A\cup C$. There are two cases, namely $x\in A$ or $x\notin A$. Suppose first that $x\in A$. Then clearly $x\in A\cup B$ and $x\in A\cup C$ as $x$ is a member of the first set in each union. This shows that $x\in (A\cup B)\cap(A\cup C)$. Now suppose $x\notin A$. This means $x\in B\cap C$ (see the third sentences in this proof). Hence we know that $x\in B$ and $x\in C$. Since $x\in B$, we now $x\in A\cup B$. Since $x\in C$, we know $x\in A\cup C$. This shows that $x\in (A\cup B)\cap(A\cup C)$ as desired. This completes the proof that $A\cup(B\cap C) \subseteq (A\cup B)\cap (A\cup C)$. To finish, we must prove $(A\cup B)\cap (A\cup C) \subseteq A\cup(B\cap C)$. Let $y\in (A\cup B)\cap (A\cup C)$. We again use two cases. Suppose $y\in A$. Then clearly $y\in A\cup (B\cap C)$ by definition of union. The only other option is $y\notin A$. Recall we assumed that $y\in (A\cup B)\cap (A\cup C)$, which means $y\in (A\cup B)$ and $y\in (A\cup C)$. This means $y\in A$ or $y\in B$, and it means $y\in A$ or $y\in C$. Since we have assumed that $y\notin A$, this means that $y\in B$, and it means that $y\in C$. Together, this gives $y\in B\cap C$, which shows that $y\in A\cup (B\cap C)$.
- Your proof should be very similar to the previous.
Problem 30: (Associative Laws For Set Unions And Intersections)
Let $A$, $B$, and $C$ be sets.
- Prove that $A\cup (B\cup C) = (A\cup B)\cup C$.
- Prove that $A\cap (B\cap C) = (A\cap B)\cap C$.
Problem 31: (The Integers Have No Limit Points)
There are three parts to this problem.
- Start by writing the definition of a limit point $p$ of a set $S$ using the quantifiers $\forall$ and $\exists$. Feel free to use set operations $\cup$ and/or $\cap$ in your definitions.
- Then write, using these quantifiers, what it means to not be a limit point.
- Finish by proving that if $p\in\mathbb{R}$, then $p$ is not a limit point of $\mathbb{Z}$. In other words, prove that $\mathbb{Z}$ has no limit points.
Problem 32: (Periodic Functions And Practice With Quantifiers)
Consider the following definition:
- Rewrite the definition above using the symbols $\exists$ and $\forall$.
- Prove that $y=\sin(x)$ is periodic over the reals.
- Finish the following: "We say that a function $y=f(x)$ is not periodic over the reals if ..."
- Prove that $y=x^2$ is not periodic over the reals.
Problem 33: (First Induction Problem)
For each $n\in \mathbb{N}$ consider the statement $$1+2+\cdots+n=\frac{n(n+1)}{2}.$$ This is infinitely many statements. How do we prove infinitely many statements are true? What follows is a proof that all of these statements are true. The proof relies on the domino problem done earlier in the semester. Part way through the proof are several different versions of how to proceed. Your job is to read the proof and the different versions, and then decide for each version if it is logically sound and clear.
| Option | Logically Sound (Y/N) | Clear (Y/N) |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 |
We'll have a discussion in class about your answers. Now for the proof.
To simplify our writing below, for each $n\in \mathbb{N}$ let $S_n$ be the statement $$1+2+\cdots+n=\frac{n(n+1)}{2}.$$ We will prove that for each $n\in \mathbb{N}$, we know that $S_n$ is a true statement. To do this, we'll refer to the domino problem we proved earlier in the semester. Imagine for a minute that we have an infinite collection of dominos numbered $1, 2, 3, \ldots$. The first domino has the statement $1=\frac{1(2)}{2}$ on it, the second domino has the statement $1+2=\frac{2(3)}{2}$ on it, the third domino has the statement $1+2+3=\frac{3(4)}{2}$ on it, and so on. For each $n\in \mathbb{N}$, domino $n$ has the statement $S_n$ on it. We now have an infinite collection of dominos, one for each natural number $n$. We will now knock over each domino when we know the statement written on that domino is true. If we can knock over every domino, then $S_n$ is true for every $n\in \mathbb{N}$.
In the domino problem, two important things happened. First, note that Jon knocked over the first domino. Second, we knew that "if the $k$th domino falls, then it knocks over the $(k+1)$st domino." We will verify these two facts are true about our dominos. The first domino clearly falls, as the statement on the first domino is $1=\frac{1(2)}{2}$, which is true. We now must prove the second condition is true, namely "if the $k$th domino falls, then it knocks over the $(k+1)$st domino."
Option 1: Click to expand.
For each $k\in \mathbb{N}$ suppose domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We then compute $$ \begin{align} \underbrace{1+2+3+\cdots + k} + (k+1) &=\frac{k(k+1)}{2}+(k+1) && \text{ (replace using the assumption) }\\ &=(k+1)\left[\frac{k}{2}+1\right] &&\text{ (factor) }\\ &=\frac{(k+1)(k+2)}{2} &&\text{(get a common denominator).} \end{align} $$ This proves that $1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}$, which means $S_{k+1}$ is a true statement. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 2: Click to expand.
Suppose for some $k\in \mathbb{N}$ that domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We then compute $$ \begin{align} \underbrace{1+2+3+\cdots + k} + (k+1) &=\frac{k(k+1)}{2}+(k+1) && \text{ (replace using the assumption) }\\ &=\frac{k^2+3k+2}{2} &&\text{ (get a common denominator) }\\ &=\frac{ (k+1)(k+2) }{2} &&\text{(factor).} \end{align} $$ This proves that $1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}$, which means $S_{k+1}$ is a true statement. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 3: Click to expand.
Suppose that domino $k$ fell where $k\in \mathbb{N}$. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We then compute $$ \begin{align} \underbrace{1+2+3+\cdots + k} + (k+1) &=\frac{k(k+1)}{2}+(k+1) && \text{ (replace using the assumption) }\\ &=(k+1)\left[\frac{k}{2}+1\right] &&\text{ (factor) }\\ &=\frac{ (k+1)(k+2) }{2} &&\text{(get a common denominator).} \end{align} $$ This proves that $1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}$, which means $S_{k+1}$ is a true statement. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 4: Click to expand.
For each $k\in \mathbb{N}$ suppose domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. Since this assumption is true for every $k\in\mathbb{N}$, it must also be true when we look at the integer $k+1$. This means that statement $S_{k+1}$ is true, which means domino $k+1$ fell as needed. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 5: Click to expand.
Suppose for some $k\in \mathbb{N}$ that domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We must prove that statement $S_{k+1}$ is true, which means we must prove $$1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}.$$ We can replace the $1+2+\cdots +k$ with $\frac{k(k+1)}{2}$ in the above equation to get $$\frac{k(k+1)}{2}+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}.$$ The left side simplifies to $\frac{k(k+1)}{2}+(k+1)=\frac{k^2+k+2k+2}{2}=\frac{k^2+3k+2}{2}$. The right side simplifies to $\frac{ (k+1) ( (k+1)+1) }{2} = \frac{ (k+1) (k+2) }{2} =\frac{k^2+3k+2}{2}.$ Since the left and right side both simplify to the same thing, then the original statement $S_{k+1}$ is true. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
Option 6: Click to expand.
Suppose for some $k\in \mathbb{N}$ that domino $k$ fell. This means statement $S_k$ is true, which means $1+2+\cdots+k=\frac{k(k+1)}{2}$ is true. We must prove that statement $S_{k+1}$ is true, which means we must prove $$1+2+\cdots+k+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}.$$ Because we know $1+2+\cdots +k=\frac{k(k+1)}{2}$ (from our assumption that $S_{k}$ is true), substitution shows that statement $S_{k+1}$ is equivalent to the statement $$\frac{k(k+1)}{2}+(k+1)=\frac{ (k+1) ( (k+1)+1) }{2}.$$ The left side of the above equation is equal to $\frac{k(k+1)}{2}+(k+1)=\frac{k^2+k+2k+2}{2}=\frac{k^2+3k+2}{2}$. This means that statement $S_{k+1}$ is equivalent to $$\frac{k^2+3k+2}{2}=\frac{ (k+1) ( (k+1)+1) }{2}.$$ This last statement is clearly true as $ (k+1) ( (k+1)+1) = (k+1)(k+2)=k^2+3k+2$. This completes the proof that statement $S_{k+1}$ is true. This shows that if statement $S_k$ is true, then statement $S_{k+1}$ must be true as well.
We conclude by referring to the domino problem. Since the first domino was knocked over, and since the $k$th domino falling implies the $(k+1)$st domino falls, then we know that every domino falls (the conclusion of the domino problem). This means that $S_n$ is a true statement for every $n\in\mathbb{N}$.
After reading the previous problem and analyzing several different proofs, we are ready to make a formal statement what we call "The principle of Mathematical Induction." The next problem asks you to prove this. If your proof looks very similar to the domino problem, then you are doing this correctly.
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 34: (Proof Of Mathematical Induction)
Use the well ordering principle to prove the principle of mathematical induction.
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}$.
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}$.
- First show that the statement is true if you let $n=1$. (Show $1\in S$.)
- Then assume that the statement is true if you let $n=k$ for some $k\in \mathbb{N}$.
- 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}$.
For more problems, see AllProblems