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 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$.
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}$.
Exercise (Implications Versus Universal Quantifiers)
Consider the two statements below.
- For every $x\in \mathbb{N}$, we have $x\geq 4$.
- If $x\in \mathbb{N}$, then we have $x\geq 4$.
Are these two statements logically equivalent? Explain.
Click to see a solution.
The answer here is complicated, though the best answer is probably, "NO." The answer depends on context, as described below.
If your initial answer was "yes", then good job; however, you made an assumption. As mathematicians, we have been trained from our past to assume that when a variable appears before us, then we will assume the unknown variable takes on any possible value that makes sense in the problem. Since we see $x\geq 4$, this means at some point we are comparing $x$ with the real number 4, so $x$ is possibly any real number. Since $x\in\mathbb{N}$ appears as well, we also assume that $x$ is a natural number. At this point, the second statement becomes
- For every $x\in \mathbb{R}\cap \mathbb{N}$, if $x\in \mathbb{N}$, then we have $x\geq 4$.
Since $\mathbb{R}\cap \mathbb{N}=\mathbb{N}$, we can rewrite this as
- For every $x\in\mathbb{N}$, if $x\in \mathbb{N}$, then we have $x\geq 4$.
Then notice that since $x\in \mathbb{N}$, the phrase after "if" is always true. This means that "If TRUE, then we have $x\geq 4$" is equivalent to "we have $x\geq 4$", which means we can rewrite the second statement as
- For every $x\in\mathbb{N}$, we have $x\geq 4$.
This now matches exactly the first statement. Notice that to obtain this conclusion, we had to make an assumption.
If your initial answer was "no", then great job. Note that $x\in\mathbb{N}$ is an open sentence, as we cannot determine the truth value of this sentence unless we know more information. The phrase "For every $x\in \mathbb{N}$, we have $x\geq 4$" fully describes which $x$ to consider - no assumptions must be made. The phrase "If $x\in \mathbb{N}$, then we have $x\geq 4$," does not provide any indication of what $x$ may or may not be, and hence the truth value cannot be determined without more information (possibly an assumption). The latter phrase can occur in many different contexts, and its truth value depends on the context. Consider each of the examples below.
- Suppose $x\in \mathbb{R}$. The sentence "If $x\in \mathbb{N}$, then we have $x\geq 4$," is false, because $x=1$ provides a counterexample.
- Suppose $x\in [3.5,\infty)$. The sentence "If $x\in \mathbb{N}$, then we have $x\geq 4$," is true because if we require both $x\in [3.5,\infty)$ and $x\in \mathbb{N}$, then we definitely have that $x\geq 4$.
- Suppose $x$ is irrational. The sentence "If $x\in \mathbb{N}$, then we have $x\geq 4$," is true because it is impossible for $x$ to be irrational and to have $x\in \mathbb{N}$ at the same time. Since the condition after the "if" part of the implication is false, then the entire implication is true.
Notice that the truth value of our implication depends entirely on the context. The truth value of, "For every $x\in \mathbb{N}$, we have $x\geq 4$," does not depend on any context, as the context is fully provided.
Consider as a last example the following paragraphs.
- Suppose $x\geq 3.5$. For every $x\in \mathbb{N}$, we have $x\geq 4$.
- Suppose $x\geq 3.5$. If $x\in \mathbb{N}$, then we have $x\geq 4$.
What is the difference? The first example tells me to let $x\geq 3.5$. Then the words "For every $x\in \mathbb{N}$" tell me to disregard, for a moment, the fact that we already assumed $x\geq 3.5$. Instead, we now let $x$ represent any natural number, and then claim that this always implies $x\geq 4$. The second sentence of this paragraph is false (as $x$ might equal 1), and is completely independent from the first sentence. Once the second sentence ends, we continue assuming $x\geq 3.5$. Now consider the second paragraph. Again we start by letting $x\geq 3.5$. However this time we don't forget this assumption when we continue reading. Instead, we use this choice of $x$ to determine the truth value of our implication, resulting in a true implication. The implication depends on the surrounding context, where as the fully quantified statement does not.
In conclusion, the two sentences are NOT logically equivalent.
For more problems, see AllProblems