- Here is the list of topics that we covered.
- We did Theorem 1 in Section 6.2. Do the exercises: 1, 2, 3, 4, 7, 11, 41, 42.
-
I find the formulation of Theorem 1 in Section 6.2 unclear. To me, it is not clear what is being assumed for the equivalence to hold. Below I reformulate the theorem and present a simple proof using the Mathematical Induction. Recall that, assuming that $c_1, c_2 \in \mathbb R$ and $c_1^2 + 4 c_2 \gt 0$, the roots of the quadratic equation $x^2 - c_1 x - c_2 = 0$ are real and distinct and given by
\[
\frac{c_1 - \sqrt{c_1^2 + 4 c_2}}{2} \quad \text{and} \quad \frac{c_1 + \sqrt{c_1^2 + 4 c_2}}{2}.
\]
In the theorem below we use the following notation: For $m \in \mathbb Z$ we set
\[
{\mathbb Z}_{\geq m} = \bigl\{n \in \mathbb Z \, | \, n \geq m \bigl\}.
\]
In particular,
\[
{\mathbb Z}_{\geq 2} = \bigl\{n \in \mathbb Z \, | \, n \geq 2 \bigl\} \quad \text{and} \quad
{\mathbb Z}_{\geq 0} = \bigl\{n \in \mathbb Z \, | \, n \geq 0 \bigl\}.
\]
Theorem. Let $\bbox[lightgreen, 6px, border:2px solid green]{c_1}$ and $\bbox[lightgreen, 6px, border:2px solid green]{c_2}$ be real numbers such that $\bbox[lightgreen, 6px, border:2px solid green]{c_1^2 + 4 c_2 \gt 0}$. Let $\bbox[lightgreen, 6px, border:2px solid green]{r_1}$ and $\bbox[lightgreen, 6px, border:2px solid green]{r_2}$ be defined as \[ \bbox[lightgreen, 6px, border:2px solid green]{r_1 = \frac{c_1 - \sqrt{c_1^2 + 4 c_2}}{2}} \quad \text{and} \quad \bbox[lightgreen, 6px, border:2px solid green]{r_2 = \frac{c_1 + \sqrt{c_1^2 + 4 c_2}}{2}}. \] Let $\bbox[lightgreen, 6px, border:2px solid green]{a_0}$ and $\bbox[lightgreen, 6px, border:2px solid green]{a_1}$ be real numbers and define \[ \bbox[lightgreen, 6px, border:2px solid green]{\alpha_1 = \frac{a_0 r_2 - a_1}{r_2 - r_1}} \quad \text{and} \quad \bbox[lightgreen, 6px, border:2px solid green]{\alpha_2 = \frac{-a_0 r_1 + a_1}{r_2 - r_1}}. \] Then \[ \bbox[6px, border:2px solid gray]{ \forall n \in {\mathbb Z}_{\geq 2} \ \ a_n = c_1 \, a_{n-1} + c_2 \, a_{n-2} } \quad \text{if and only if} \quad \bbox[6px, border:2px solid gray]{\forall n \in {\mathbb Z}_{\geq 0} \ \ a_n = \alpha_1\, r_1^n + \alpha_2\, r_2^n. } \]
- Let us prove the "only if" part first. That is prove \[ \bbox[lightgreen, 6px, border:2px solid green]{ \forall n \in {\mathbb Z}_{\geq 2} \ \ a_n = c_1 \, a_{n-1} + c_2 \, a_{n-2} } \quad \Rightarrow \quad \bbox[#FFC0C0, 6px, border:2px solid red]{\forall n \in {\mathbb Z}_{\geq 0} \ \ a_n = \alpha_1\, r_1^n + \alpha_2\, r_2^n}. \]
- Assume \[ \bbox[lightgreen, 6px, border:2px solid green]{\forall n \in {\mathbb Z}_{\geq 2} \ \ a_n = c_1 \, a_{n-1} + c_2 \, a_{n-2}}. \] We use Mathematical Induction to prove \[ \bbox[#FFC0C0, 6px, border:2px solid red]{\forall n \in {\mathbb Z}_{\geq 0} \ \ a_n = \alpha_1\, r_1^n + \alpha_2\, r_2^n}. \] In some sense what I am doing here is the strong induction. But, I am casting it as Mathematical Induction. You can recast it as Strong Induction. For $n \in {\mathbb Z}_{\geq 1}$ the statement $P(n)$ is \[ { \bigl(a_{n-1} = \alpha_1\, r_1^{n-1} + \alpha_2\, r_2^{n-1} \bigr) \ \bigwedge \ \bigl(a_{n} = \alpha_1\, r_1^{n} + \alpha_2\, r_2^{n}\bigr) } \]
- Base step: Let us calculate \begin{align*} \alpha_1\, r_1^{0} + \alpha_2\, r_2^{0} & \bbox[lightgreen, 6px, border:2px solid green]{=} \alpha_1 + \alpha_2 \\ & \bbox[lightgreen, 6px, border:2px solid green]{=} \frac{a_0 r_2 - a_1}{r_2 - r_1} + \frac{-a_0 r_1 + a_1}{r_2 - r_1} \\ & \bbox[lightgreen, 6px, border:2px solid green]{=} a_0 \end{align*} and \begin{align*} \alpha_1\, r_1^{1} + \alpha_2\, r_2^{1} & \bbox[lightgreen, 6px, border:2px solid green]{=} \frac{a_0 r_2 - a_1}{r_2 - r_1} r_1 + \frac{-a_0 r_1 + a_1}{r_2 - r_1} r_2 \\ & \bbox[lightgreen, 6px, border:2px solid green]{=} a_1. \end{align*} This proves $\bbox[lightgreen, 6px, border:2px solid green]{P(1)}$.
- Inductive step: Let $\bbox[lightgreen, 6px, border:2px solid green]{k \in {\mathbb Z}_{\geq 1}}$ be arbitrary. Assume \[ \bbox[lightgreen, 6px, border:2px solid green]{ \bigl(a_{k-1} = \alpha_1\, r_1^{k-1} + \alpha_2\, r_2^{k-1} \bigr) \ \bigwedge \ \bigl(a_{k} = \alpha_1\, r_1^{k} + \alpha_2\, r_2^{k}\bigr) }. \] This is the inductive hypothesis. We need to prove \[ \bbox[lightgreen, 6px, border:2px solid green]{ \bigl(a_{k-1} = \alpha_1\, r_1^{k-1} + \alpha_2\, r_2^{k-1} \bigr) \ \bigwedge \ \bigl(a_{k} = \alpha_1\, r_1^{k} + \alpha_2\, r_2^{k}\bigr) } \quad \Rightarrow \quad \bbox[#FFC0C0, 6px, border:2px solid red]{ \bigl(a_{k} = \alpha_1\, r_1^{k} + \alpha_2\, r_2^{k} \bigr) \ \bigwedge \ \bigl(a_{k+1} = \alpha_1\, r_1^{k+1} + \alpha_2\, r_2^{k+1}\bigr) } \]
- Since $\bbox[lightgreen, 6px, border:2px solid green]{a_{k} = \alpha_1\, r_1^{k} + \alpha_2\, r_2^{k}}$ is already green, we just need to prove $\bbox[#FFC0C0, 6px, border:2px solid red]{ a_{k+1} = \alpha_1\, r_1^{k+1} + \alpha_2\, r_2^{k+1}}$.
- Since $\bbox[lightgreen, 6px, border:2px solid green]{k \in {\mathbb Z}_{\geq 1}}$, we have $\bbox[lightgreen, 6px, border:2px solid green]{k+1 \in {\mathbb Z}_{\geq 2}}$. Since we assume \[ \bbox[lightgreen, 6px, border:2px solid green]{\forall n \in {\mathbb Z}_{\geq 2} \ \ a_n = c_1 \, a_{n-1} + c_2 \, a_{n-2}}, \] by universal instantiation $\bbox[lightgreen, 6px, border:2px solid green]{a_{k+1} = c_1 \, a_{k} + c_2 \, a_{k-1}}$.
- Since we assume $\bbox[lightgreen, 6px, border:2px solid green]{ a_{k-1} = \alpha_1\, r_1^{k-1} + \alpha_2\, r_2^{k-1}}$ and $\bbox[lightgreen, 6px, border:2px solid green]{a_{k} = \alpha_1\, r_1^{k} + \alpha_2\, r_2^{k}}$ we just calculate \begin{align*} a_{k+1} & \bbox[lightgreen, 6px, border:2px solid green]{=} c_1 \, a_{k} + c_2 \, a_{k-1} \\ & \bbox[lightgreen, 6px, border:2px solid green]{=} c_1 \bigl( \alpha_1\, r_1^{k} + \alpha_2\, r_2^{k} \bigr) + c_{2} \bigl(\alpha_1\, r_1^{k-1} + \alpha_2\, r_2^{k-1} \bigr) \\ & \bbox[lightgreen, 6px, border:2px solid green]{=} \alpha_1 r_1^{k-1} \bigl( c_1 r_1 + c_2\bigr) + \alpha_2\, r_2^{k-1} \bigl( c_1 r_1 + c_1 \bigr) \\ & \bbox[lightgreen, 6px, border:2px solid green]{=} \alpha_1 r_1^{k-1} r_1^2 + \alpha_2\, r_2^{k-1} r_2^2 \\ & \bbox[lightgreen, 6px, border:2px solid green]{=} \alpha_1 r_1^{k+1}+ \alpha_2\, r_2^{k+1}, \end{align*} where at the last step we used algebra and at the one-before last step we used the fact that $r_1$ aned $r_2$ are roots of the equation $x^2 - c_1 x - c_2 = 0$. Thus $\bbox[lightgreen, 6px, border:2px solid green]{ r_1^2 = c_1 r_1+ c_2}$ and $\bbox[lightgreen, 6px, border:2px solid green]{ r_2^2 = c_1 r_2+ c_2}$ and that is what we used.
- Thus, starting at item 3 above, for arbitrary ${k \in {\mathbb Z}_{\geq 1}}$ we proved \[ { \bigl(a_{k-1} = \alpha_1\, r_1^{k-1} + \alpha_2\, r_2^{k-1} \bigr) \ \bigwedge \ \bigl(a_{k} = \alpha_1\, r_1^{k} + \alpha_2\, r_2^{k}\bigr) } \quad \Rightarrow \quad { \bigl(a_{k} = \alpha_1\, r_1^{k} + \alpha_2\, r_2^{k} \bigr) \ \bigwedge \ \bigl(a_{k+1} = \alpha_1\, r_1^{k+1} + \alpha_2\, r_2^{k+1}\bigr) }. \] That is, we proved $P(k) \Rightarrow P(k+1)$. By universal generalization we proved \[ \bbox[lightgreen, 6px, border:2px solid green]{\forall n \in {\mathbb Z}_{\geq 1} \quad P(n) \Rightarrow P(n+1)} \]
- Thus, we proved \[ \bbox[lightgreen, 6px, border:2px solid green]{P(1) \ \bigwedge \ \bigl( \forall n \in {\mathbb Z}_{\geq 1} \quad P(n) \Rightarrow P(n+1) \bigr) } \] By Mathematical Induction this implies \[ \bbox[lightgreen, 6px, border:2px solid green]{\forall n \in {\mathbb Z}_{\geq 1} \quad P(n) } \] that is \[ \bbox[lightgreen, 6px, border:2px solid green]{ \forall n \in {\mathbb Z}_{\geq 1} \ \ \bigl(a_{n-1} = \alpha_1\, r_1^{n-1} + \alpha_2\, r_2^{n-1} \bigr) \ \bigwedge \ \bigl(a_{n} = \alpha_1\, r_1^{n} + \alpha_2\, r_2^{n}\bigr) } \] In the last statement there are lot of repeated propositions. Eliminating repetitions, the last statement reads \[ \bbox[lightgreen, 6px, border:2px solid green]{ \forall n \in {\mathbb Z}_{\geq 0} \ \ a_{n} = \alpha_1\, r_1^{n} + \alpha_2\, r_2^{n} } \] This completes the proof of the "only if" part.
- Prove the "if" part as an exercise. That is prove \[ \bbox[lightgreen, 6px, border:2px solid green]{ \forall n \in {\mathbb Z}_{\geq 0} \ \ a_n = \alpha_1\, r_1^n + \alpha_2\, r_2^n } \quad \Rightarrow \quad \bbox[#FFC0C0, 6px, border:2px solid red]{ \forall n \in {\mathbb Z}_{\geq 2} \ \ a_n = c_1 \, a_{n-1} + c_2 \, a_{n-2} }. \] The proof should not be difficult, but do it right. It uses the same algebraic "tricks" that I used in the above proof.
- We did Section 4.5 today.
- Do the exercises: 1-9, 12, 14-16, 20, 21, 23, 25, 30, 31, 33, 37, 39.
- We did Section 4.3 yesterday and Section 4.4 today.
- For Section 4.3 do as many exercises as you can from 1-43.
- For Section 4.4 do the exercises: 1-13, 21, 22, 28, 29, 30.
- Here is the list of topics that we did so far with the topics on the next exam emphasised.
- Today we did Theorem 3 in Section 4.2 and I also proved Dirichlet's Approximation Theorem. The proof is based on the Pigeonhole principle you can find it here.
-
Here is a conceptually simpler proof of Theorem 3 in Section 4.2. And this proof uses the generalized Pigeonhole Principle.
- Let $n$ be a positive integer and let $a_1, a_2, \ldots,a_{n^2+1}$ be a sequence of $n^2+1$ distinct real numbers.
- We need to prove that there exists an increasing subsequence with $n+1$ terms or there exists a decreasing subsequence with $n+1$ terms.
- Thus the statement that we need to prove is of the form $\boxed{p \Rightarrow q \vee r}$. It is awkward to prove statements in which the claim includes OR. However, the statement that we need to prove is equivalent to the statement $\boxed{p \wedge \neg q \Rightarrow r}$. To see that the boxed statements are equivalent just compare their negations: the negation of the first boxed statement is $p\wedge \neg q \wedge \neg r$ and the negation of the second boxed statement is $p\wedge \neg q \wedge \neg r$; which are identical statements.
- Thus, in addition to the assumptions in the first item of the proof, we assume that all increasing subsequences of the sequence $a_1, a_2, \ldots,a_{n^2+1}$ have at most $n$ terms.
- Now we need to prove that there exists a decreasing subsequence with at least $n+1$ terms.
- For $k \in \{1,\ldots,n^2+1\}$ by $i_k$ we denote the number of terms in the longest increasing subsequence starting at $a_k$ and by $d_k$ we denote the number of terms in the longest decreasing subsequence starting at $a_k$. (Here all one term sequences are considered both increasing and decreasing. Hence $i_k$ and $d_k$ are positive integers.)
- Recall that $i_k, \ k\in \{1,\ldots,n^2+1\}$, are lengths of increasing subsequences. There are $n^2+1$ such lengths. Consider these numbers as pigeons. Since we assume that each increasing subsequence of the sequence $a_1, a_2, \ldots,a_{n^2+1}$ has at most $n$ terms, we have $i_k \leq n$ for all $k\in \{1,\ldots,n^2+1\}$. Let the numbers $\{1,\ldots,n\}$ be pigeonholes. Since we have $n^2+1$ pigeons and $n$ pigeonholes, by the generalized Pigeonhole principle there is at least one pigeonhole with at least $\bigl\lceil(n^2+1)/n \bigr\rceil = n+1$ pegeons.
- The conclusion from the previous item is that there exists a value $n_0 \in \{1,\dots,n\}$ and $n+1$ numbers $k_1,\ldots,k_{n+1} \in \{1,\ldots,n^2+1\}$ such that \[ \bbox[lightgreen, 6px, border:2px solid green]{k_1 \lt k_2 \lt \cdots \lt k_{n+1}} \quad \text{and} \quad \bbox[lightgreen, 6px, border:2px solid green]{i_{k_1} = i_{k_2} = \cdots =i_{k_{n+1}}} = n_0. \]
- Let $k,l \in \{1,\ldots,n^2+1\}$ be such that $k \lt l$. Notice the following simple implication \[ a_k \lt a_l \ \ \Rightarrow \ \ i_k \gt i_l. \] The contrapositive of the above implication is (here we use the fact that the terms of the sequence are distinct real numbers) \[ \bbox[lightgreen, 6px, border:2px solid green]{i_k \leq i_l \ \ \Rightarrow \ \ a_k \gt a_l}. \]
- Here we use the green boxed statements from items 8. and 9. to deduce \[ \bbox[lightgreen, 6px, border:2px solid green]{a_{k_1} \gt a_{k_2} \gt \cdots \gt a_{k_{n+1}}}. \] And, it should be mentioned that in our deduction we have used Modus Ponens.
- Read Section 4.2.
- Do the exercises: 3, 4, 5, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 36, 40.
- The Pigeonhole Principle: If there are $N$ pigeons and these pigeons are distributed in $k$ pigeonholes, then there is at least one hole containing at least $\bigl\lceil N/k \bigr\rceil$ pigeons.
-
Notice the following direct proof of the Pigeonhole Principle.
- Denote by $m_1$, $m_2, \ldots, m_k$ the number of pigeons in each of the $k$ holes.
- Then, by the sum rule, $N = m_1 + m_2 + \cdots + m_k$.
- Denote by $m$ the maximum number of pigeons in one hole. Then for all $j \in \{1,\ldots,k\}$ we have $m_j \leq m$. By the properties of order of integers \[ m_1 + m_2 + \cdots + m_k \leq k m. \]
- By the transitivity of inequality, from the last two items we conclude that $N \leq k m$. Consequently, since $k \gt 0$, we have $N/k \leq m$.
- Since $m$ is a positive integer, properties of the ceiling function imply \[ \left\lceil \frac{N}{k}\right\rceil \leq m . \]
- Since there is a hole with $m$ pigeons in it, we conclude: At lease one hole contains at least $\bigl\lceil N/k \bigr\rceil$ pigeons.
- Today we did counting problems from Section 4.1. Specifically, we did problems 20, 40 and 42.
- Please have in mind that all counting problems are very specific. For small sets we can just list all the possibilities and count those that are described in a problem. For slightly larger sets this would be to time consuming to do by hand. But, we can program a computer to do the count. Today in class I illustrated how one can program in Mathematica to really count the sets from the exercises. In this way we have a hands-on verification of our abstract counting.
- In class I use Mathematica version 5.2. On some campus computers we also have Mathematica version 8. These versions are not compatible. For this class I will only post version 5.2 notebooks since on in the labs there are more computers with version 5.2.
-
Here you can download the Mathematica 5.2 file that I used today. It is called 20150518.nb. Right-click on the underlined word "Here you can download"; in the pop-up menu that appears, your browser will offer you to save the file in your directory. Make sure that you save it with the exactly same name. After saving the file you can open it with Mathematica 5.2. You will find Mathematica 5.2 on many campus computers in
Start -> All Programs -> Math Applications -> Mathematica 5.2. Open Mathematica first, then open 20150518.nb from Mathematica 5.2. You can execute the entire file by the following manu sequence (in Mathematica):Kernel -> Evaluation -> Evaluate Notebook. - To evaluate a particular cell in a Mathematica file place the cursor in the cell and press Shift+Enter. There is more about how to use Mathematica 5.2 at my Mathematica page.
- If you have problems running files that I post please let me know. If you spend some time learning how to use these files you will enhance the understanding of math that you are studying.
- Here you can download the pdf printout of the Mathematica file that I used today. In this file you can find solutions of the problems that we did in class.
- On Friday we did Section 4.1. Do the exercises: As many as you can from 1-33. Also 36, 37 (the answer should involve a single formula involving n), 38-42, 47, 48, 49.
-
The basic counting rules are:
- The sum rule: For disjoint finite sets $A$ and $B$ we have $|A \cup B| = |A| + |B|$.
- The product rule: For finite sets $A$ and $B$ we have $|A \times B| = |A| \cdot |B|$.
- The inclusion-exclusion rule: For finite sets $A$ and $B$ we have $|A \cup B| = |A| + |B| - |A\cap B|$.
- The complement rule: For finite sets $A$ and $U$ we have $|A| = |U| - |U\setminus A|$.
- Usually counting requires use of several rules. One way to avoid wrong counts is to make clear which counting rules you use and make sure that the rules are used correctly. Also, it is essential to test your formula on few small examples.
- The complement rule is almost miraculous when $A$ is difficult to count, but $U$ and $U\setminus A$ are much easier to count.
- Read the first part of Section 3.4, up to Recursively defined sets and structures.
- Do the exercises: 1, 2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15, 16, 18, 19 in Section 3.4.
- We will start Section 3.3. You can skip Examples 12, 13. We covered Subsection "The well-ordering property" in more detail in Section 6 of the notes Basic propositions about the Integers. This will be useful in Math 302.
- Do the exercises: 1, 2, 3, 5, 6, 7, 8, 9, 10, 11, 15, 18, 19, 20, 24, 25, 26 (use the result from 25), 32, 36, 37, 50, 51, 53, 54, 57, 59, 62 in Section 3.3.
- On Friday I gave a rigorous proof that ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ is countably infinite. I proved that the function \[ g:\mathbb Z^+\!\!\times\!\mathbb Z^+\to \mathbb Z^+ \] defined by \[ g(s,t) = \frac{(s+t-1)(s+t)}{2}+1-t, \qquad s,t \in {\mathbb Z^+} \] is a bijection between ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ and ${\mathbb Z}^+$. To prove that $g$ is a bijection I discovered the formula for the inverse of $g$, I call it $f : {\mathbb Z}^+ \to {\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$: \begin{equation*} f(n) = \biggl( n - \frac{\bigl( R_n-1 \bigr) R_n}{2} \, , \, \frac{R_n \bigl( R_n + 1 \bigr)}{2} - n + 1 \biggr) , \qquad n \in {\mathbb Z^+}. \end{equation*} Here $R_n$ is the "repeat sequence" 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, ... which is given by the formula \[ R_n = \Bigl\lfloor \sqrt{2n} + \frac{1}{2} \Bigr\rfloor, \qquad n \in {\mathbb Z^+}. \] The all details of the reasoning are in the file ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ is countable. The content of the file ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ is countable is illustrated in this Mathematica v5.2 notebook. To give you a glimpse what is in the notebook I printed it to this large pdf file.
- The proof that the above formula for $R_n$ truly gives the repeat sequence is a solution to Exercise 12 in Section 3.2. Below is a solution to Exercise 12 in Section 3.2.
-
To solve Exercise 12 we have to answer the following question: For a given $m \in {\mathbb Z}^+$ how many positive integers $n$ satisfy the equality
$\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $?
-
By the definition of the floor function
$\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $ if and only if $ \ m \leq \sqrt{2n} + \frac{1}{2} \lt m+1$.
-
By the properties of order of real numbers
$m \leq \sqrt{2n} + \frac{1}{2} \lt m+1 \ $ if and only if $ \ m - \frac{1}{2} \leq \sqrt{2n} \lt m + \frac{1}{2}$
-
Since each term in the inequality is positive we have
$m - \frac{1}{2} \leq \sqrt{2n} \lt m + \frac{1}{2} \ $ if and only if $ \ m^2 - m + \frac{1}{4} \leq 2n \lt m^2 + m + \frac{1}{4}$
-
Since $m^2 - m$, $2n$ and $m^2 + m$ are integers we have
$m^2 - m + \frac{1}{4} \leq 2n \lt m^2 + m + \frac{1}{4} \ $ if and only if $ \ m^2 - m \lt 2n \leq m^2 + m$
-
Since $2 \gt 0$,
$m^2 - m \lt 2n \leq m^2 + m \ $ if and only if $ \ \dfrac{(m-1)m}{2} \lt n \leq \dfrac{m(m + 1)}{2}$
-
Thus, for $m, n \in {\mathbb Z}^+$ we have proved the equivalence:
$\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $ if and only if $ \ \dfrac{m(m-1)}{2} \lt n \leq \dfrac{m(m+1)}{2}$.
- Next, notice the identity \[ \dfrac{m(m+1)}{2} = \dfrac{m(m-1)}{2} + m. \] Therefore, $ \ \dfrac{m(m-1)}{2} \lt n \leq \dfrac{m(m+1)}{2} \ $ if and only if $\ n \ $ is one of $m$ integers \[ \dfrac{m(m-1)}{2} + 1, \ \dfrac{m(m-1)}{2} + 2, \ \ldots, \ \dfrac{m(m-1)}{2} + m. \]
- Finally we conclude that $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $ if and only if $\ n \ $ is one of $m$ integers \[ \dfrac{m(m-1)}{2} + 1, \ \dfrac{m(m-1)}{2} + 2, \ \ldots, \ \dfrac{m(m-1)}{2} + m. \] That is, the sequence $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor$ takes the value $m$ exactly at $m$ distinct consecutive values of $n$.
-
By the definition of the floor function
-
Here I summarize what we did from the notes
Basic properties of the Integers.
- Section 2, all propositions.
- Section 3, Propositions 3.1, 3.2, 3.3, 3.6, Corollary 3.7. $0 \lt 1$. (In class I gave a proof by contradiction.)
- Definitions 3.9 and 3.10 and Exercises 3.11 and 3.12.
- Section 4 all Propositions.
- All of Section 5.
- All of Section 6.
- Section 3.2: Do the exercises 2, 4, 5, 6, 9, 11, 12, some of 13-18, 19, 20, 21, 23. Notice that Exercises 11 and 12 are more challenging.
- Here is a shortened version of my notes on basic properties of the integers deduced from the axioms. You should understand all the proofs that are in these notes and that we did in class.
- One student gave a really nice proof of the floor problem on the exam. Recall, you were asked to prove $\forall x \in {\mathbb R}$ $\lfloor 2x \rfloor = \lfloor x \rfloor + \lfloor x +1/2 \rfloor$. Let $x \in {\mathbb R}$ be arbitrary. Consider two cases: Case 1. Assume that the integer $\lfloor 2x \rfloor$ is even, that is $\lfloor 2x \rfloor = 2m$, where $m \in {\mathbb Z}$. Then by the basic property of the floor function we have $2m \leq 2x \lt 2m+1$. Dividing by $2$ we get $m \leq x \lt m+1/2$. Therefore $\lfloor x \rfloor = m$. Also, adding $1/2$ to the inequality $m \leq x \lt m+1/2$ we get $m \leq x +1/2 \lt m+1$, which implies $\lfloor x +1/2 \rfloor = m$. Thus $\lfloor 2x \rfloor = 2m = \lfloor x \rfloor + \lfloor x +1/2 \rfloor$. Case 2. Assume that the integer $\lfloor 2x \rfloor$ is odd, that is $\lfloor 2x \rfloor = 2m+1$, where $m \in {\mathbb Z}$. Then by the basic property of the floor function we have $2m+1 \leq 2x \lt 2m+2$. Dividing by $2$ we get $m+1/2 \leq x \lt m+1$. Therefore $\lfloor x \rfloor = m$. Also, adding $1/2$ to the inequality $m+1/2 \leq x \lt m+1$ we get $m +1 \leq x +1/2 \lt m+3/2$, which implies $\lfloor x +1/2 \rfloor = m+1$. Thus $\lfloor 2x \rfloor = 2m +1 = \lfloor x \rfloor + \lfloor x +1/2 \rfloor$.
-
Here are two quantified statements that I copied from your exams. These statements are not directly related to what was assigned on the exam, but they are interesting exercises.
- $\forall\, x \ \exists\, y \ \forall\, z \quad (z \lt y) \ \vee \ (x \leq z^2)$ (the universe of discourse consists of all real numbers)
- $\exists\, x \ \forall \, y \ \exists \, z \quad (z \gt y) \ \Rightarrow \ (z^2 \gt x)$ (the universe of discourse consists of all positive real numbers)
- The axioms for the integers are posted here.
- Some basic properties of integers deduced from the axioms can be found here.
- Here is the list of topics that we did so far. In this list I emphasized some of the more important exercises.
- Today we started Section 1.8. Do the exercises 1, 2, 4, 8, 9, 10, 11, 12, 13, 14, 17, 18, 23, 25, 26, 27, 28, 29, 31, 43, 44, 45, 48, 49, 56, 58, 60(f), 65, 66 ((b) and (d) in 66 are wrong)
- Here is the formal definition of a function.
Definition Let $A$ and $B$ be nonempty sets. A function from $A$ into $B$ is a subset $F$ of the Cartesian product $A\!\times\!B$ such that
- Fun1 $\forall \, x \in A$ $\exists \, y \in B$ $(x,y) \in F$,
- Fun2 $\forall \, x \in A$ $\forall \, y_1 \in B$ $\forall \, y_2 \in B$ $\quad (x,y_1) \in F \wedge (x,y_2) \in F \ \Rightarrow \ y_1=y_2$.
- Here is the formal definition of a surjection.
Definition Let $A$ and $B$ be nonempty sets. A function $F$ from $A$ to $B$ is a surjection if
- Sur $\forall \, y \in B$ $\exists \, x \in A$ $(x,y) \in F$.
- Here is the formal definition of an injection.
Definition Let $A$ and $B$ be nonempty sets. A function $F$ from $A$ to $B$ is an injection if
- Inj $\forall \, x_1 \in A$ $\forall \, x_2 \in A$ $\forall \, y \in B$ $\quad (x_1,y) \in F \wedge (x_2,y) \in F \ \Rightarrow \ x_1=x_2$.
- Here is the complete formal definition of a bijection.
Definition Let $A$ and $B$ be nonempty sets. A bijection from $A$ into $B$ is a subset $F$ of the Cartesian product $A\!\times\!B$ such that
- Fun1 $\forall \, x \in A$ $\exists \, y \in B$ $(x,y) \in F$,
- Fun2 $\forall \, x \in A$ $\forall \, y_1 \in B$ $\forall \, y_2 \in B$ $\quad (x,y_1) \in F \wedge (x,y_2) \in F \ \Rightarrow \ y_1=y_2$.
- Sur $\forall \, y \in B$ $\exists \, x \in A$ $(x,y) \in F$.
- Inj $\forall \, x_1 \in A$ $\forall \, x_2 \in A$ $\forall \, y \in B$ $\quad (x_1,y) \in F \wedge (x_2,y) \in F \ \Rightarrow \ x_1=x_2$.
- Assume that $F$ is a bijection. Define a subset $G$ of $B\!\times\!\!A$ by \[ G = \bigl\{(y,x) \in B\!\times\!\!A \ | \ (x,y) \in F \bigr\}. \] If $A = B = \mathbb R$, then $G$ is just the reflection of $F$ across the line $y = x$.
-
Since we assume that $F$ is a bijection, this is what we know about the subset $G$ of $B\!\times\!\!A$:
- Fun1 $\forall \, x \in A$ $\exists \, y \in B$ $(y,x) \in G$,
- Fun2 $\forall \, x \in A$ $\forall \, y_1 \in B$ $\forall \, y_2 \in B$ $\quad (y_1,x) \in G \wedge (y_2,x) \in G \ \Rightarrow \ y_1=y_2$.
- Sur $\forall \, y \in B$ $\exists \, x \in A$ $(y,x) \in G$.
- Inj $\forall \, x_1 \in A$ $\forall \, x_2 \in A$ $\forall \, y \in B$ $\quad (y,x_1) \in G \wedge (y,x_2) \in G \ \Rightarrow \ x_1=x_2$.
-
Appropriate names relative to the subset $G$ of $B\!\times\!\!A$ are given in purple below. I choose purple since in class I colored the set $G$ in purple.
- Sur $\forall \, x \in A$ $\exists \, y \in B$ $(y,x) \in G$,
- Inj $\forall \, x \in A$ $\forall \, y_1 \in B$ $\forall \, y_2 \in B$ $\quad (y_1,x) \in G \wedge (y_2,x) \in G \ \Rightarrow \ y_1=y_2$.
- Fun1 $\forall \, y \in B$ $\exists \, x \in A$ $(y,x) \in G$.
- Fun2 $\forall \, x_1 \in A$ $\forall \, x_2 \in A$ $\forall \, y \in B$ $\quad (y,x_1) \in G \wedge (y,x_2) \in G \ \Rightarrow \ x_1=x_2$.
- Conclusion: For a bijection $F$ the subset a subset $G$ of $B\!\times\!\!A$ defined by \[ G = \bigl\{(y,x) \in B\!\times\!\!A \ | \ (x,y) \in F \bigr\} \] is a bijection from $B$ to $A$. This bijection $G$ is called the inverse of the bijection $F.$
- Few comments about the terminology:
- The book also uses the term one-to-one function; I prefer the synonym: injection.
- The book also uses the term onto function; I prefer the synonym: surjection.
-
bijection
Our textbook and many other books use the phrase "one-to-one correspondence" as a synonym for bijection.
Here are four reasons why "bijection" is preferable to "one-to-one correspondence":- A single word is preferable to an awkward phrase "one-to-one correspondence".
- In the setting of functions it is easy to confuse "one-to-one correspondence" with "one-to-one function". Notice that a "one-to-one function" is not necessarily a "one-to-one correspondence"
- The noun "correspondence" is not used in mathematics at an undergraduate level. Therefore, students might be wondering: what is a correspondence? is it a function or not?
- We should leave "one-to-one correspondence" to be used in informal settings. For example, here "one-to-one correspondence" is used in a preschool setting.
- We did Section 1.7 on Friday. Do the exercises 2, 3, 11, 14, 18, 19, 20, 24, 26, 27, 28, 29, 30, 31, 32, 33
- Wikipedia's Set page is relevant here:
- On Monday we will do Section 1.8 Functions
- The book does not give a formal definition of a function. Since this is a junior college level class it is appropriate that we give a formal definition of function.
-
The formal definition of a function identifies a function and its graph. The justification is that if you know the graph of a function, then you know the function, and conversely, if you know a function you know its graph. I like this definition since it takes advantage of the language that we learned in the logic part of the class. Simply stated the definition below says that a function from a set $A$ to a set $B$ is a subset $F$ of the Cartesian product $A\!\times\!B$ such that for each $x \in A$ there exists unique $y \in B$ such that $(x,y) \in F$.
Definition Let $A$ and $B$ be nonempty sets. A function from $A$ into $B$ is a subset $F$ of the Cartesian product $A\!\times\!B$ such that- $\forall \, x \in A \ \ \exists \, y \in B \quad (x,y) \in F$,
- $\forall \, x \in A \ \forall \, y \in B \ \forall \, z \in B \quad (x,y) \in F \wedge (x,z) \in F \ \Rightarrow \ y=z$.
- Here is the link to a page that gives 23 proofs that $\sqrt{2}$ is irrational.
- We did Section 1.6: Sets today. Do the exercises 1 - 21, 24, 25, 27, 28.
- Some relevant Wikipedia links:
-
There is one important aspect of proofs that I did not get to talk about in class.
- Many mathematical statements are of the form \[ p \wedge q \Rightarrow r. \] Often, proving a contrapositive is an efficient way to prove an implication. However, in this case, the contrapositive is \[ \neg r \Rightarrow (\neg p) \vee (\neg q). \] How does one prove an implication like this?. This will be explained in the next bullet.
- However, the implication $p \wedge q \Rightarrow r$ is equivalent to \[ p \wedge (\neg r) \Rightarrow (\neg q). \]
-
The easiest way to see that my claim in the preceding bullet is true is to state the negations of both implications. Here they are:
The negation of $p \wedge q \Rightarrow r$ is $\bbox[2px,border:1px solid]{p \wedge q \wedge (\neg r)}$ The negation of $p \wedge (\neg r) \Rightarrow (\neg q)$ is $\bbox[2px,border:1px solid]{p \wedge (\neg r) \wedge q}$ Since the negations are equivalent, the implications in the preceding bullet are equivalent. - Thus, $\bbox[2px,border:1px solid]{p \wedge q \Rightarrow r}$ is equivalent to $\bbox[2px,border:1px solid]{p \wedge (\neg r) \Rightarrow (\neg q)}$. I call the latter implication a partial contrapositive of the former. One more equivalent partial contrapositive of $\bbox[2px,border:1px solid]{p \wedge q \Rightarrow r}$ is $\bbox[2px,border:1px solid]{(\neg r) \wedge q \Rightarrow (\neg p)}$. These equivalences are powerful tools in proving theorems.
- For example, Problem 25 in Section 1.5 asks us to prove that the sum of an irrational number and a rational number is irrational using a proof by contradiction. This problem can be stated as an implication \[ \bigl(x \ \text{irrational} \bigr) \wedge \bigl(y \ \text{rational} \bigr) \ \Rightarrow \ \bigl(x + y \ \text{irrational} \bigr). \] Yes, we could proceed by a proof by contradiction. However, I think that proving a partial contrapositive is much more elegant: \[ \bigl(x + y \ \text{rational} \bigr) \wedge \bigl(y \ \text{rational} \bigr) \ \Rightarrow \ \bigl(x \ \text{rational} \bigr). \] The last implication should not be difficult to prove since we already proved \[ \bigl(a \ \text{rational} \bigr) \wedge \bigl(b \ \text{rational} \bigr) \ \Rightarrow \ \bigl(a+b \ \text{rational} \bigr) \] and it is not difficult to prove that \[ \bigl(c \ \text{rational} \bigr) \ \Rightarrow \ \bigl(-c \ \text{rational} \bigr) \]
- Today we started Section 1.5. Pay special attention to the "mathematical" proofs in this section. In particular pay attention how definitions are used in proofs. Remember: all definitions are biconditionals (that is "if and only if" statements), although they are not stated that way. Do the exercises 21, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 39, 40, 43, 44, 46, 49, 51, 55, 64, 65, 70.
- Please recall our discussion of the famous saying "You can fool all the people some of the time and some of the people all the time, but you cannot fool all the people all the time." from April 7. Today I have rewritten and extended this post of April 7. Your comments are welcome (about all my postings).
- A good practice with quantified statements is to look at the grids consisting of randomly colored black and white boxes.
- Let $B(j,k)$ be the following propositional function: "The box in the $j$-th row and $k$-th column is colored black". Here we assume that the rows are counted from top to bottom and the columns are counted from left to right.
- Consider grids which consist of black and white cells. For example consider the following four grids:
Further, consider the following four propositions:Grid 1 Grid 2 Grid 3 Grid 4 
- Proposition 1. $\forall j \, \exists k \ B(j,k)$
- Proposition 2. $\exists k \, \forall j \ B(j,k)$
- Proposition 3. $\exists j \, \forall k \ \neg B(j,k)$
- Proposition 4. $\forall k \, \exists j \ B(j,k)$
- Let $P(x)$ be a propositional function. The book is not very clear on how to express the proposition "there exists a unique $x$ such that $P(x)$ is true" using quantifiers. One can deduce from Example 1.4.6 that one way to do it is \[ \exists x \Bigl( P(x) \wedge \forall y \bigl( (y\neq x) \Rightarrow \neg P(y) \bigr) \Bigr) \] Since in the above proposition the first term in the conjunction does not depend on $y$ we can equivalently write it as \[ \exists x \ \forall y \ \Bigl( P(x) \wedge \bigl( (y\neq x) \Rightarrow \neg P(y) \bigr) \Bigr) \] Further, since the implication in the conjunction contains two negations it can be replaced by its contrapositive \[ \exists x \ \forall y \ \Bigl( P(x) \wedge \bigl( P(y) \Rightarrow (y = x) \bigr) \Bigr) \] However, the last displayed proposition can be simplified further. It is equivalent to \[ \exists x \ \forall y \ \bigl( P(y) \Leftrightarrow (y = x) \bigr) \] The last proposition is a simple way to express the statement "there exists a unique $x$ such that $P(x)$ is true" using quantifiers.
- Recall that the book uses the abbreviation "$p\to q$" for "If $p$, then $q$." However, a more common abbreviation is "$p\Rightarrow q$". Similarly, the book uses "$p \leftrightarrow q$" for "$p$ if and only if $q$", while a more common abbreviation is "$p \Leftrightarrow q$".
-
Recall the famous saying:
You can fool all the people some of the time and some of the people all the time, but you cannot fool all the people all the time.
Today in class it occurred to me that this saying is a nice exercise in use of quantifiers. How to write this saying as a proposition using quantifiers?-
First consider a propositional function with two variables: "$x$ can be fooled at time $t$". Abbreviate this function as $C(x,t)$. Then a formal re-statement of the famous saying is:
In this formal reformulation we ignored the subject "You" in the saying. We interpreted the saying as: "All people can be fooled some of the time and some of the people all the time, but all people cannot be fooled all the time."
$\bbox[5px,border:1px solid]{\displaystyle \Bigl( \exists t \ \forall x \ \ C(x,t) \Bigr) \bigwedge \Bigl( \exists x \ \forall t \ \ C(x,t) \Bigr) \bigwedge \Bigl( \exists x \ \exists t \ \ \neg C(x,t) \Bigr)}$ -
A different take on this saying is to replace the subject "You" with another variable; appropriately named $y$. Consider the propositional function of three variables "$y$ can fool $x$ at time $t$". Abbreviate this function as $F(y,x,t)$. Then a formal re-statement of the famous saying is:
In this formal reformulation we remove the personal aspect of "You" from the saying. So, the saying reads something like "Everybody can fool all the people some of the time and some of the people all the time, but nobody can fool all the people all the time."
$\bbox[5px,border:1px solid]{\displaystyle \Bigl(\forall y \ \exists t \ \forall x \ \ F(y,x,t) \Bigr) \bigwedge \Bigl(\forall y \ \exists x \ \forall t \ \ F(y,x,t) \Bigr) \bigwedge \Bigl(\forall y \ \exists x \ \exists t \ \ \neg F(y,x,t) \Bigr)}$
-
First consider a propositional function with two variables: "$x$ can be fooled at time $t$". Abbreviate this function as $C(x,t)$. Then a formal re-statement of the famous saying is:
- Today we did Section 1.3 and started Section 1.4. Do the exercises 1, 2, 9, 10, 16, 19, 20, 24, 25, 26, 27, 28, 29, 30, some of 31-36, 37, 38, 39, 40, 41, 42, 43, 44, 45 of Section 1.4. Exercises for Section 1.3 were listed on Thursday, April 2, 2015.
-
Here are few exercises involving quantified statements with three variables. For each statement formulate the negation and decide which one is true: the original statement or its negation. Provide a proof of your claim.
- $\forall\, a \ \forall\, b \ \exists\, c \quad cb \gt a$ (the universe of discourse consists of all real numbers)
- $\forall\, a \ \forall\, b \ \exists\, c \quad cb \gt a$ (the universe of discourse consists of all positive real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \quad (z \gt y) \ \Rightarrow \ (zx \gt 1)$ (the universe of discourse consists of all real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \quad (z \gt y) \ \Rightarrow \ (zx \gt 1)$ (the universe of discourse consists of all positive real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \quad (z \gt y) \ \Rightarrow \ (z^2 \gt x^2)$ (the universe of discourse consists of all real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \quad (z \gt y) \ \Rightarrow \ (z^2 \gt x)$ (the universe of discourse consists of all real numbers)
-
On Friday I used the example "y is a leap year" to motivate the concept of a propositional function or a predicate.
Here is the definition of the leap year from Wikipedia:
In the Gregorian calendar, the current standard calendar in most of the world, most years that are evenly divisible by 4 are leap years. In each leap year, the month of February has 29 days instead of 28. Adding an extra day to the calendar every four years compensates for the fact that a period of 365 days is shorter than a solar year by almost 6 hours. Some exceptions to this rule are required since the duration of a solar year is slightly less than 365.25 days. Years that are evenly divisible by 100 are not leap years, unless they are also evenly divisible by 400, in which case they are leap years.
-
As you can see Wikipedia's definition is quite verbose. It is an interesting exercise with propositions to write the definition of the leap year in a more formal way. Here is one way to do this:
Let $y$ stand for a particular year.
$y\ $ is a leap year if and only if $\ \ \bigl(P(y) \wedge (\neg Q(y)) \bigr) \vee R(y) \ \ $
where
$P(y)\ $ stands for: $Q(y)\ $ stands for: $R(y)\ $ stands for: $\dfrac{y}{4}\ $ is an integer. $\dfrac{y}{100}\ $ is an integer. $\dfrac{y}{400}\ $ is an integer. - In class I used this formal definition to teach Mathematica which years are leap years, which are not. I did it in Mathematica version 5.2. On some campus computers we also have Mathematica version 8. These versions are not compatible. For this class I will only post version 5.2 notebooks since there are more computers with version 5.2 on campus.
-
Here is the Mathematica 5.2 file that I used. It is called 20150403.nb. Right-click on the underlined word "Here"; in the pop-up menu that appears, your browser will offer you to save the file in your directory. Make sure that you save it with the exactly same name. After saving the file you can open it with Mathematica 5.2. You will find Mathematica 5.2 on many campus computers in
Start -> All Programs -> Math Applications -> Mathematica 5.2. Open Mathematica first, then open 20150403.nb from Mathematica 5.2. You can execute the entire file by the following manu sequence (in Mathematica):Kernel -> Evaluation -> Evaluate Notebook. - To evaluate a particular cell in a Mathematica file place the cursor in the cell and press Shift+Enter. There is more about how to use Mathematica 5.2 at my Mathematica page.
- If you have problems running files that I post please let me know. If you spend some time learning how to use these files you will enhance the understanding of math that you are studying.
- Today we talked about Section 1.2. Do the exercises 3, 4, 6, 8, 12, 13 and some of 14-29. Also do 49 and 51.
- Tomorrow we will do Section 1.3. The exercises for this section are 1, 2, 9, 11 - 19, 28, 30, 31, 33, 34, 41, 46, 47, 55, 56, 57.
- The information sheet
- The textbook loan form
- Read Section 1.1. Do the exercises 6, 7, 10, 12, 13, 15, 16, 20, 21, 22, 23, 24, 27, 30, 38, 39, 40, 41, 51-55.
- Here is a pdf file of the first few sections of the book.
- Here are 12 different ways to say: If p, then q.