- Some solutions from Section 4.4 as a Mathematica file are here and a pdf print-out of the same file is here.
- Some solutions from Section 4.3 as a Mathematica file are here and a pdf print-out of the same file is here.
- Some solutions from Section 4.1 as a Mathematica file are here and a pdf print-out of the same file is here.
- Here is an updated list of topics for the final exam.
- Some solutions from Section 6.1 as a Mathematica file are here and a pdf print-out of the same file is here.
- Some solutions from Section 4.5 as a Mathematica file are here and a pdf print-out of the same file is here.
- We did Section 6.1 on Tuesday. In particular we are interested in using recursions for counting. The best general example is The Tower of Hanoi. Pay special attention to Example 6 in Section 6.1. It explains how to use recursions to count bit strings of length $n$ which do not contain consecutive zeros. Do the exercises: 3, 4, 6, 7, 17, 19, 22, 23, 24, 25, 26, 27, 28, 40, 41.
- Some solutions from Section 6.1 as a Mathematica file are here and a pdf print-out of the same file is here.
- 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.4 today. For Section 4.4 do the exercises: 1-13, 21, 22, 28, 29, 30.
- Today I proved Dirichlet's Approximation Theorem. As I pointed out in class the question stated as: "State and prove Dirichlet's Approximation Theorem" could appear on the final exam.
- We did Section 4.3 today. For Section 4.3 do as many exercises as you can from 1-43.
- Today we did problems that can be solved using the Pigeonhole Principle. In particular we did problems 36 and 37 in Section 4.2.
-
Notice that problems with integers that involve the Pigeonhole Principle often require the theorem about the integers called the Division Algorithm.
Theorem (The Division Algorithm) For every $n \in \mathbb Z$ and every $m \in \mathbb Z^+$ there exist unique integers $q$ and $r$ such that \[ n = m q + r \quad \text{and} \quad r \in \{0,\ldots,m-1\}. \]Definition For $n \in \mathbb Z$ and $m \in \mathbb Z^+$ the number $r$ from the Division Algorithm is called the remainder left by $n$ when divided by $m$.
- Since the Division Algorithm is a statement about integers, it is appropriate to give a proof which uses only the Axioms of the integers. Such a proof is given in Section 7 of my notes Basic Properties of Integers. However, a simpler proof can be given using rational numbers and the fact that the function floor is defined for all real numbers. Such a proof is in the next item.
-
Proof of the Division Algorithm using the floor function.
- First recall the following characterization of the floor function. For $x \in \mathbb R$ we have \[ \lfloor x \rfloor = k \quad \Leftrightarrow \quad k \in \mathbb Z \ \wedge \ k \leq x \lt k+1. \]
- Let $n \in \mathbb Z$ and $m \in \mathbb Z^+$ be arbitrary. Then $n/m$ is a rational number and thus $n/m$ is a real number. Set \[ q = \left\lfloor \frac{n}{m} \right\rfloor \quad \text{and} \quad r = n - m q. \]
- By the characterization of the floor function $q \in \mathbb Z.$ Consequently $r\in \mathbb Z$ as well and clearly $n = mq + r.$
- Again by the characterization of the floor function \[ q \leq \frac{n}{m} \lt q+1. \] Since $m \gt 0$, multiplying the preceding expression by $m$ yields \[ m q \leq n \lt mq + m. \] Subtracting $mq$ from each term we get \[ 0 \leq n - mq \lt m. \] Since $r = n - m q$ and $r \in \mathbb Z,$ the preceding expression yields $r \in \{0,\ldots,m-1\}.$
- The previous four items prove the existence of such $q$ and $r.$
- To prove uniqueness, assume that $q', r' \in \mathbb Z$ are such that $n = m q' + r'$ and $r' \in \{0,\ldots,m-1\}.$ Since $m \gt 0$ and $r' \in \{0,\ldots,m-1\}$, dividing $n = m q' + r'$ with $m$ yields \[ q' \leq \frac{n}{m} = q' + \frac{r'}{m} \lt q' + 1. \] The preceding expression, the fact that $q' \in \mathbb Z$ and the characterization of the floor imply that $q' = \lfloor n/m \rfloor.$ Consequently, $r' = n - m \lfloor n/m \rfloor.$ This proves uniqueness.
-
On Friday I presented a different proof of Theorem 3 in Section 4.2. I believe that the proof presented below is a conceptually simpler proof of Theorem 3 in Section 4.2. 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 is a disjunction. 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 $u_k$ we denote the number of terms in the longest increasing subsequence starting at $a_k.$ For $k \in \{1,\ldots,n^2+1\}$ 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 $u_k$ and $d_k$ are positive integers.)
- Recall that $u_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 $u_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$ pigeons in it.
- 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]{u_{k_1} = u_{k_2} = \cdots = u_{k_{n+1}}} = n_0. \]
-
Let $k,l \in \{1,\ldots,n^2+1\}.$ Notice the following simple implication
\[
k \lt l \ \wedge \ a_k \lt a_l \ \ \Rightarrow \ \ u_k \gt u_l.
\]
(Why is this implication simple? The inequality $k \lt l$ tells that the term $a_k$ comes before the term $a_l$ in the given sequence. The positive integer $u_l$ tells that there exists an increasing sequence starting at $a_l$ and having $u_l$ terms. We can attach the term $a_k$ at the beginning of this increasing sequence with $u_l$ terms and we will get an increasing sequence starting at $a_k$ with $u_l+1$ terms. Since $u_k$ denotes the length of the longest increasing sequence starting at $a_k$ this proves that $u_k\geq u_l+1\gt u_l.$)
The partial contrapositive of the preceding displayed implication is \[ \bbox[lightgreen, 6px, border:2px solid green]{ k \lt l \ \wedge \ u_k \leq u_l \ \ \Rightarrow \ \ a_k \gt a_l}. \] Here we use the fact that the terms of the given sequence are distinct real numbers, that is $a_k \neq a_l.$ - Next we use the green boxed statements from item 8 and we apply $n$ times the green boxed implication in item 9 to deduce \[ \bbox[lightgreen, 6px, border:2px solid green]{a_{k_1} \gt a_{k_2} \gt \cdots \gt a_{k_{n+1}}}. \] Thus we have constructed a decreasing subsequence with $n+1$ terms.
- Tomorrow I will present a proof of Dirichlet's Approximation Theorem. The proof is based on the Pigeonhole principle you can find it here.
- Today we did few more counting problems from Section 4.1.
- 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.
-
Here you can download the Mathematica 5.2 notebook which has few problems from Section 4.1 solved using the counting methods and then the relevant sets created and counted in Mathematica. The file is called Section_4_1.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 Section_4_1.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 notebook Section_4_1.nb.
- We continued with 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 $p$ pigeons and these pigeons are distributed in $h$ pigeonholes, then there is at least one hole containing at least $\bigl\lceil p/h \bigr\rceil$ pigeons.
-
Here is a direct proof of the Pigeonhole Principle.
- Denote by $p_1$, $p_2, \ldots, p_h$ the number of pigeons in each of the $h$ holes.
- Then, by the sum rule, $p = p_1 + p_2 + \cdots + p_h$.
- Denote by $m$ the maximum number of pigeons in one hole. Then for all $k \in \{1,\ldots,h\}$ we have $p_k \leq m$. By the properties of order of integers \[ p_1 + p_2 + \cdots + p_h \leq h\, m. \]
- By the transitivity of inequality, from the last two items we conclude that $p \leq h\, m$. Consequently, since $h \gt 0$, we have $p/h \leq m$.
- Since $m$ is a positive integer, properties of the ceiling function imply \[ \left\lceil \frac{p}{h}\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 p/h \bigr\rceil$ pigeons.
- Today I handed out the second assignment. It is due at the time of the final exam.
- Today 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.
- Here is the list of topics that we did for this exam. In this list I emphasized some of the more important exercises.
- Here is a summary of the Propositions that we did from my notes Basic Properties of Integers: 2.1, 2.2, 2.4, 2.5, 2.6, 2.7, 2.8, 2.9, 3.1, 3.2, 3.6. Then we proved Corollaries: 3.7, 3.8 (do Exercises 3.11 and 3.12) then we proved Proposition 4.3 and finally we proved Theorem 5.1.
- 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.
- Today we proved that the set ${\mathcal P}(\mathbb Z^+)$ is not countable.
- We started Section 3.3. You can skip Example 12. We covered Subsection "The well-ordering property" in more detail in Section 5 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.
-
Notice that in class I gave a more restrictive definition of countability than what is in the textbook.
- an empty set (This is the unique set which has no elements.)
- a finite set (A nonempty set $S$ is called finite if there exists $n\in {\mathbb Z}^+$ a bijection $f: \{1,\ldots,n\} \to S.$)
- a countable set (A nonempty set $S$ is called countable if there exists a bijection $f: {\mathbb Z}^+ \to S.$)
- an uncountable set (A set which is nether one of the above kinds.)
- Today I gave a rigorous proof that ${\mathbb Z}$ is countable.
- Today I gave a rigorous proof that ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ is countably. 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 \frac{1}{2} + \sqrt{2n} \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. I gave a proof on April 25.
- We did Section 3.2 today. 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.
- For Section 3.3 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.
- Today we proved Proposition 4.3 which states $1=\min {\mathbb Z}^+.$ Here is the proof. Since $0\lt 1$, $1 \in {\mathbb Z}^+.$ Therefore ${\mathbb Z}^+ \neq \emptyset.$ By Axiom WO we deduce that ${\mathbb Z}^+$ has a minimum. Set $m=\min {\mathbb Z}^+.$ Then $m\in {\mathbb Z}^+$ and for all $x \in {\mathbb Z}^+$ we have $m\leq x.$ Therefore, $m\leq 1.$ Since $0\lt m$ and $m\leq 1$, Axioms OM and MO imply $m^2\leq m.$ Since $0\lt m$, Axiom OM yields $0\cdot m\lt m^2.$ Since $0\cdot m =0$ we have that $0\lt m^2.$ Thus $m^2\in {\mathbb Z}^+.$ Since $m=\min {\mathbb Z}^+$ we deduce that $m\leq m^2.$ Thus, we have proved that $m^2\leq m$ and $m\leq m^2$ implying $m=m^2.$ That is $0= m^2-m = m(m-1).$ By Axiom MZ it follows that $m=0$ or $m-1=0.$ Since $0\lt m$ disjunctive syllogism yields $m-1 = 0.$ This proves $m=1.$
- Today we also proved the Principle of Mathematical Induction. The formal statement of the Principle of Mathematical Induction is: \begin{equation*} \bbox[lightgreen, 6px, border:3px solid green]{ P(1)\wedge \Bigl( \forall \, k \ \bigl( P(k) \Rightarrow P(k+1) \bigr) \Bigr)} \color{black} \quad \Rightarrow \quad \bbox[#FFC0C0, 6px, border:3px solid red]{\forall\, n \ P(n)} \end{equation*} Here and in the proof the universe of discourse is the set $\mathbb Z^+$, the set of all positive integers.
- The logical structure of the Principle of Mathematical Induction statement is $p\wedge q\Rightarrow r.$ As is often the case, it is easier to prove the equivalent statement $p\wedge(\neg r)\Rightarrow (\neg q).$ (I call this statement the "partial contrapositive" of the original statement.)
- The partial contrapositive of the Principle of Mathematical Induction is: \begin{equation*} \bbox[lightgreen, 6px, border:3px solid green]{ P(1)\wedge \bigl( \exists \, j \ \ \neg P(j) \bigr)} \color{black} \quad \Rightarrow \quad \bbox[#FFC0C0, 6px, border:3px solid red]{ \exists \, k \ \ P(k) \wedge \bigl( \neg P(k+1) \bigr) } \end{equation*}
-
Here are the highlights of the proof. The details are in the notes.
- The proof uses the Well Ordering Axiom for the Integers, see the Axioms for the integers.
- Assume \begin{equation*} \bbox[lightgreen, 6px, border:3px solid green]{ P(1)} \ \wedge \bbox[lightgreen, 6px, border:3px solid green]{ \bigl( \exists \, j \ \ \neg P(j) \bigr)} \end{equation*} By existential instantiation let ${\color{green} c} \in \mathbb Z^+$ be such that $\bbox[lightgreen, 6px, border:3px solid green]{\neg P(c)}$ is true.
- Define the set \begin{equation*} S = \bigl\{ x \in \mathbb Z^+ \ | \ \neg P(x) \bigr\} \end{equation*} Clearly $S \neq \emptyset$ and $S \subseteq \mathbb Z^+.$ By Axiom WO the set $S$ has a minimum. Set \begin{equation*} \bbox[lightgreen, 6px, border:3px solid green]{m = \min S} \end{equation*} Since $\bbox[lightgreen, 6px, border:3px solid green]{ P(1)}$ we have $\bbox[lightgreen, 6px, border:3px solid green]{1 \not\in S}$. Since $\bbox[lightgreen, 6px, border:3px solid green]{1 \not\in S}$ and $\bbox[lightgreen, 6px, border:3px solid green]{m \in S}$ we have $\bbox[lightgreen, 6px, border:3px solid green]{1 \neq m}.$ Since $\bbox[lightgreen, 6px, border:3px solid green]{1 = \min \mathbb Z^+}$ and $\bbox[lightgreen, 6px, border:3px solid green]{m \in \mathbb Z^+},$ we have $\bbox[lightgreen, 6px, border:3px solid green]{1 \lt m}.$ Therefore $\bbox[lightgreen, 6px, border:3px solid green]{0 \lt m-1}.$ That is $\bbox[lightgreen, 6px, border:3px solid green]{m-1 \in \mathbb Z^+}.$ Since $\bbox[lightgreen, 6px, border:3px solid green]{m-1 \in \mathbb Z^+},$ $\bbox[lightgreen, 6px, border:3px solid green]{m-1 \lt m}$ and $\bbox[lightgreen, 6px, border:3px solid green]{m =\min S}$, we deduce $\bbox[lightgreen, 6px, border:3px solid green]{m-1 \not\in S}.$ Therefore $\bbox[lightgreen, 6px, border:3px solid green]{P(m-1)}$ is true. Since $\bbox[lightgreen, 6px, border:3px solid green]{m \in S}$, we have $\bbox[lightgreen, 6px, border:3px solid green]{\neg P(m)}$ is true. Therefore \begin{equation*} \bbox[lightgreen, 6px, border:3px solid green]{ P(m-1)} \ \wedge \bbox[lightgreen, 6px, border:3px solid green]{ \bigl( \neg P(m) \bigr)} \end{equation*} Consequently \begin{equation*} \bbox[lightgreen, 6px, border:3px solid green]{ \exists \, k \ \ P(k) \wedge \bigl( \neg P(k+1) \bigr) } \end{equation*} is true by setting $k = m-1.$
- Today we proved the following Propositions from my notes Basic Properties of Integers: 2.2, 2.4, 2.6, 2.7, 2.8, 2.9, 3.1, 3.2, 3.6. Then we proved Corollaries: 3.7 and 3.8
- Today we discussed the importance of the Well Ordering Axiom for Integers and we proved Proposition 2.1 and Proposition 2.5 in Basic Properties of Integers.
- This is the final list of exercises for Section 1.8: 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)
-
To illustrate the usefulness of the floor function I brought up the following sequence of positive integers:
\begin{equation*}
1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, ...
\end{equation*}
The pattern here is clear. But, is there a formula that produces this sequence? It turns out that one formula that produces this sequence is given by
\begin{equation*}
\forall \, n \in {\mathbb Z}^+ \qquad r(n) = \left\lfloor \frac{1}{2} + \sqrt{2n} \right\rfloor.
\end{equation*}
Then
\begin{equation*}
r(1) = 1, r(2) = 2, r(3) = 2, r(4) = 3, r(5) = 3, r(6) = 3, r(7) = 4, r(8) = 4, ...
\end{equation*}
Next we will prove that for every positive integer $m$ exactly $m$ consecutive positive integers $n$ satisfy the equality
$\displaystyle \left\lfloor \frac{1}{2} + \sqrt{2n} \right\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 the following $m$ integers \[ \dfrac{m(m-1)}{2} + 1, \ \dfrac{m(m-1)}{2} + 2, \ \ldots, \ \dfrac{m(m-1)}{2} + m. \]
- Putting all the above equivalences together we conclude that $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $ if and only if $\ n \ $ is one of the following $m$ integers \[ \dfrac{m(m-1)}{2} + 1, \ \dfrac{m(m-1)}{2} + 2, \ \ldots, \ \dfrac{m(m-1)}{2} + m. \]
- Thus, we have proved that for every $m \in {\mathbb Z}^+$ the sequence $r(n) = \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
- Next we will discuss some basic properties of Integers. The starting point in the study of integers are the axioms for the integers. A pdf version of this page is here.
- Some basic properties of integers deduced from the axioms can be found here.
- The complete list of exercises for Section 1.8: 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 maroon below.
- 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$.
- The above reasoning proves the following theorem:
Theorem Let $A$ and $B$ be nonempty sets. Let $F$ be a subset of the Cartesian product $A\!\times\!B$. Define the subset $G$ of $B\!\times\!\!A$ by \[ G = \bigl\{(y,x) \in B\!\times\!\!A \ | \ (x,y) \in F \bigr\}. \] Then $G$ is a bijection if and only if $F$ is a bijection.
- If $F:A\to B$ is a bijection, then the bijection $G:B\to A$ defined by \[ G = \bigl\{(y,x) \in B\!\times\!\!A \ | \ (x,y) \in F \bigr\} \] is called the inverse of the bijection $F.$
- Precalculus is full of important bijections. Below I list several bijections and you can figure out why they are important: \begin{alignat*}{2} A & = [0,+\infty), & \quad B & = [0,+\infty), & \qquad f_1 & = \bigl\{ (x,x^2) \in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ A & = \mathbb R, & \quad B & = \mathbb R, & \qquad f_2 & = \bigl\{ (x,x^3) \in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ A & = \mathbb R, & \quad B & = (0,+\infty), & \qquad f_3 & = \bigl\{ (x,e^x)\in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ A & = (-\pi/2,\pi/2), & \quad B & = \mathbb R, & \qquad f_4 & = \bigl\{ \bigl( x,\tan(x) \bigr) \in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ A & = [-\pi/2,\pi/2], & \quad B & = [-1,1], & \qquad f_5 & = \bigl\{ \bigl(x,\sin(x)\bigr)\in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ A & = [0,\pi], & \quad B & = [-1,1], & \qquad f_6 & = \bigl\{ \bigl(x,\cos(x)\bigr) \in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ \end{alignat*}
- These six bijections are plotted below in navy blue. Their inverses are plotted in maroon.
$ A = [0,+\infty), \ B = [0,+\infty), \ f_1 = \bigl\{ (x,x^2) \ \bigl| \bigr. \ x \in A \bigr\} $
$A = \mathbb R, \ B = \mathbb R, \ f_2 = \bigl\{ (x,x^3) \ \bigl| \bigr. \ x \in A \bigr\}$
$A = \mathbb R, \ B = (0,+\infty), \ f_3 = \bigl\{ (x,e^x) \ \bigl| \bigr. \ x \in A \bigr\}$
$A = (-\pi/2,\pi/2), \ B = \mathbb R, \ f_4 = \bigl\{ \bigl( x,\tan(x) \bigr) \ \bigl| \bigr. \ x \in A \bigr\} $
$ A = [-\pi/2,\pi/2], \ B = [-1,1], \ f_5 = \bigl\{ \bigl(x,\sin(x)\bigr) \ \bigl| \bigr. \ x \in A \bigr\} $
$ A = [0,\pi], \ B = [-1,1], \ f_6 = \bigl\{ \bigl(x,\cos(x)\bigr) \ \bigl| \bigr. \ x \in A \bigr\} $
- 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, 10, 11, 12, (skip d) 13, 14, 15, 17, 18, 23
- 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$.
- Few comments about the terminology:
- The synonym for injection is "one-to-one function." I much prefer the term injection.
- The synonym for surjection is "onto function." I much prefer the term surjection.
-
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 noun 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 today. 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:
- Tomorow we will do Section 1.8 Functions
- The book does not give a formal definition of a function. since this is a junior 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 28 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:
- The steps below pretend to prove that $2 = 1.$ Each line is supposed to be a logical consequence of the preceding one. But, something is wrong. Where is the error? \begin{align*} -2 & =-2 \\ 4-6 &= 1-3 \\ 4- 6 + 9/4 &= 1- 3 + 9/4 \\ 2^2- 2\cdot 2 \cdot 3/2 + (3/2)^2 &= 1- 2\cdot 1 \cdot 3/2 + (3/2)^2 \\ (2-3/2)^2 & = (1-3/2)^2 \\ 2-3/2 & = 1-3/2 \\ 2 & = 1 \end{align*}
-
Recall that on April 3 I introduced the concept of a partial contrapositive:
- $\bbox[lightgreen, 4px, border:2px solid green]{ (p \wedge q) \Rightarrow r \ \equiv \ (p \wedge \neg r) \Rightarrow (\neg q) }$ I call this a partial contrapositive. To prove it just look at the negations of both sides of the equivalence.
- Today we did 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.
- The proposition $\sqrt{2}$ is irrational is proved by contradiction in Example 21 on page 66 in the textbook. Below I will restate this proposition as an implication and prove its contrapositive.
- The proposition $\sqrt{2}$ is irrational is equivalent to the implication If $x^2 = 2$, then $x$ is irrational.
- The contrapositive of the last boxed implication is: If
$x$ is rational, then $x^2 \neq 2$.
The colored contrapositive is: If $x$ is rational, then $x^2 \neq 2$. -
Below is a proof of the contrapositive. In this proof we start with a green box. Each box that follows after this green box is a consequence of preceding green boxes. The point is that you need to understand why.
- Assume that $x$ is rational.
- Then:
There exist integers $a$ and $b$ such that $b \neq 0$, not both $a$ and $b$ are even, and $x =\dfrac{a}{b}$. - Next we consider two cases. Case I: $a$ is odd, Case II: $a$ is even.
- Consider Case I first. Assume that $a$ is odd.
- From Line 4 we deduce $a^2$ is odd.
- By Line 2 we have $b$ is an integer. This implies $2b^2$ is even.
- Since no integer is both even and odd, from Lines 5 and 6 we deduce $a^2 \neq 2b^2$.
- From Lines 2 and 7 we deduce $x^2 =\dfrac{a^2}{b^2}\neq 2$ .
(This completes the proof for Case I.) - Now consider Case II. Assume that $a$ is even.
- By Line 9 we have: There exists an integer $c$ such that $a = 2c$.
- By Line 10 we have $2c^2$ is even.
- From Lines 2 and 9 we deduce $b$ is odd.
- From Line 12 we deduce $b^2$ is odd.
- Since no integer is both even and odd, from Lines 11 and 13 we deduce $b^2 \neq 2c^2$.
- From Lines 10 and 14 we deduce $2b^2 \neq 4c^2 = a^2$.
- From Lines 2 and 15 we deduce $x^2 =\dfrac{a^2}{b^2}\neq 2$.
(This completes the proof for Case II.)
- Going back to Section 1.4, 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)$
- Again, let us go back to Section 1.4. 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) \] It seems to me that the last proposition is a simpler way to express the statement "there exists a unique $x$ such that $P(x)$ is true" using quantifiers. However, the last displayed proposition can be simplified further. It is equivalent to \[ \exists x \ \forall y \ \bigl( P(y) \Leftrightarrow (y = x) \bigr) \]
- Recall that the book uses the abbreviation "$p\to q$" for "If $p$, then $q$." However, a more common abbreviation is "$p\Rightarrow q$." So, I prefer to use "$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$."
- In 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.
-
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)
-
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.
This saying is a nice exercise in use of quantifiers. Write the above 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:
-
Before preceding with Section 1.3 I pointed out the most important logical equivalences that are really used often in proofs.
- $\bbox[lightgreen, 4px, border:2px solid green]{\neg ( p \vee q) \ \equiv \ (\neg p) \wedge (\neg q) }$ This is De Morgan's law
- $\bbox[lightgreen, 4px, border:2px solid green]{\neg ( p \wedge q) \ \equiv \ (\neg p) \vee (\neg q) }$ This is De Morgan's law
- $\bbox[lightgreen, 4px, border:2px solid green]{\neg ( p \Rightarrow q) \ \equiv \ p \wedge (\neg q) }$ This is the negation of the implication; this is how implication is commonly understood. It can be verified by a truth table.
- $\bbox[lightgreen, 4px, border:2px solid green]{ p \Rightarrow q \ \equiv \ (\neg q) \Rightarrow (\neg p) }$ The contrapositive is equivalent to the original implication. The easiest way to prove this equivalence is to look at the negations: the negation of the original proposition is $p \wedge (\neg q)$, while the negation of the original proposition is $(\neg q) \wedge p$. The last two propositions are clearly equivalent since the conjunction is commutative.
- $\bbox[lightgreen, 4px, border:2px solid green]{ (p \wedge q) \Rightarrow r \ \equiv \ (p \wedge \neg r) \Rightarrow (\neg q) }$ I call this a partial contrapositive. To prove it just look at the negations of both sides of the equivalence.
- Today we did 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.
-
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.
- 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.
- 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.