- Read Section 6.2 up to Linear nonhomogenous recurrence relations with constant coefficients on page 419.
- Do the exercises: 1, 2, 3, 7, 11, 12, 41, 42.
- Read Section 4.5.
- Do the exercises: 1-9, 12, 14-16, 20, 21, 23, 25, 30, 31, 33, 37, 39.
- Read Section 4.4.
- Do the exercises: 1-13, 21, 22, 28, 29, 30.
- Some solutions from Section 4.3 as a Mathematica file are here and a pdf print-out of the same file is here.
- And, from yesterday read Section 4.3.
- In Section 4.3 do as many exercises as you can from 1-43.
- Some hints: 23: There are nine positions to place women after man are placed; this can be done in C(9,5) ways. 29: This problem is tricky. Be aware of counting the same 4-permutations more than once. 35: Place 1s first. Then there are 10 spots to place 0s between 1s. 37: Consider the complement of the set. 40: First answer how many ways are there to seat six people on a straight bench. Then count how many distinct seatings on a bench lead to the identical seating around a circular table. 43: Have in mind that all six runners can tie for gold and so on.
- Read Section 4.2.
- Do the exercises: 3, 4, 5, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 36, 40.
- Read 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.
-
Here is a solution to Exercise 11 in Section 3.2. It is always a joy to revisit a beautiful exercise.
-
Exercise 11 uses the nearest integer function. If $x \in \mathbb R$ the book uses the notation $\{x\}$ to denote the nearest integer to $x$. This notation is easy to confuse with the singleton set. One of the suggested notations on Wikipedia is $\lfloor x \rceil$. In this hint we use the following definition of $\lfloor x \rceil$:
$\lfloor x \rceil = m$ if and only if $m \in {\mathbb Z}$ and $m- \frac{1}{2} \leq x \lt m+\frac{1}{2}$.
- The first step towards solving Exercise 11 is to characterize the equality $\bigl\lfloor \sqrt{n} \bigr\rceil = q$. Here $n, q \in {\mathbb Z}^+$. With the notation introduced in the previous bullet, the following equivalences hold:
by definition: $\bigl\lfloor \sqrt{n} \bigr\rceil = q$ $\Leftrightarrow$ $q - \frac{1}{2} \leq \sqrt{n} \lt q + \frac{1}{2}$ by squaring positive numbers
$\Leftrightarrow$ $q^2 - q + \frac{1}{4} \leq n \lt q^2 + q + \frac{1}{4}$ since $n, q \in {\mathbb Z}_+$
$\Leftrightarrow$ $q^2 - q \lt n \leq q^2 + q$ adding $q$
$\Leftrightarrow$ $q^2 \lt n + q \leq q^2 + 2q$ since $n, q \in {\mathbb Z}_+$
$\Leftrightarrow$ $q^2 \lt n + q \lt q^2 + 2q + 1$ complete square
$\Leftrightarrow$ $q^2 \lt n + q \lt (q + 1)^2$ -
To summarize, for all $n \in {\mathbb Z}^+$ and all $q \in {\mathbb Z}^+$ we have proved that the following three statements are equivalent
- $\bigl\lfloor \sqrt{n} \bigr\rceil = q$
- $q^2-q+1 \leq n \leq q^2+q$
- $q^2 \lt n + q \lt (q + 1)^2$
- Let $q \in {\mathbb Z}^+$. Denote by $S_q$ the finite set of consecutive integers that appears in II. That is \[ S_q = \bigl\{q^2-q+1, q^2-q+2, \ldots, q^2+q-1, q^2+q \bigr\}. \] Denote by $T_q$ the finite set of consecutive integers that appears in III. That is \[ T_q = \bigl\{q^2+1, q^2+2, \ldots, q^2+2q-1, q^2+2q \bigr\}. \] Notice that $S_q$ has $2q$ elements since $q^2+q - (q^2-q) = 2q$. Notice also that the set $T_q$ has $2q$ elements since $q^2+2q - q^2 = 2q$.
- Consider the function \[ f(n) \ = \ n + \bigl\lfloor \sqrt{n} \bigr\rceil, \qquad n \in {\mathbb Z}^+. \] Next we will prove that $f$ is a bijection between $S_q$ and $T_q$.
- Let $n \in S_q$; $n \in S_q$ is equivalent to II. Thus, by II $\Rightarrow$ I, we conclude $\bigl\lfloor \sqrt{n} \bigr\rceil = q$. By II $\Rightarrow$ III we conclude \[ f(n) = n + \bigl\lfloor \sqrt{n} \bigr\rceil = n + q \in T_q. \] This proves that $f$ maps $S_q$ into $T_q$.
- Now we will prove that $f$, as a function on $S_q$, is an injection. Let $m,n \in S_q$ and $m \lt n$. Then, by II $\Rightarrow$ I we conclude $\bigl\lfloor \sqrt{m} \bigr\rceil = q$ and $\bigl\lfloor \sqrt{n} \bigr\rceil = q$. Therefore, \[ f(m) = m + \bigl\lfloor \sqrt{m} \bigr\rceil = m + q \lt n + q = n + \bigl\lfloor \sqrt{n} \bigr\rceil = f(n). \] This proves that $f$, as a function on $S_q$, is an injection.
- Now we will prove that $f$, as a function from $S_q$ to $T_q$, is a surjection. Let $p \in T_q$. Set $n = p-q$. Then $p=n+q \in T_q$. Thus III holds. By III $\Rightarrow$ II we conclude $n \in S_q$. By III $\Rightarrow$ I, we conclude $\bigl\lfloor \sqrt{n} \bigr\rceil = q$. Therefore, \[ f(n) = n + \bigl\lfloor \sqrt{n} \bigr\rceil = n + q = p. \] This proves that $f$, as a function from $S_q$ to $T_q$, is a surjection.
-
To complete the solution we observe that the union of all sets $S_q$ is ${\mathbb Z}^+$ and the union of all sets $T_q$ is the set ${\mathbb Z}^+$ without the complete squares. This is illustrated in the table below:
$q$ $S_q$ $T_q$ $f(n)$ $1$ $\{1,2\}$ $\{2,3\}$ $n+1$ $2$ $\{3,4,5,6\}$ $\{5,6,7,8\}$ $n+2$ $3$ $\{7,8,9,10,11,12\}$ $\{10,11,12,13,14,15\}$ $n+3$ $4$ $\{13,14,\ldots,19,20\}$ $\{17,18,\ldots,23,24\}$ $n+4$ $5$ $\{21,22,\ldots,29,30\}$ $\{26,27,\ldots,34,35\}$ $n+5$ $\vdots$ $\vdots$ $\vdots$ $\vdots$ $q$ $\{q^2-q+1,\ldots,q^2+q\}$ $\{q^2+1,\ldots,q^2+2q\}$ $n+q$
-
Exercise 11 uses the nearest integer function. If $x \in \mathbb R$ the book uses the notation $\{x\}$ to denote the nearest integer to $x$. This notation is easy to confuse with the singleton set. One of the suggested notations on Wikipedia is $\lfloor x \rceil$. In this hint we use the following definition of $\lfloor x \rceil$:
- 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, (if you have taken Math 204 do 18, 19)
- On Friday I solved Exercise 12 in Section 3.2. Exercise 12 requires us to prove that the sequence $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor \ $ with $n \in {\mathbb Z}^+$ has the values 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, ....
-
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 values of $n$.
-
By the definition of the floor function
- On Friday I also proved that the Principle of Mathematical Induction follows from the Well Ordering Axiom. This proof is the last section in the file with some basic properties of integers.
- Read Section 3.3. You can skip Examples 10, 12, 13. Subsection "The well-ordering property" can 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.
- We finished Section 3.2. I did not cover anything about uncountable sets. But, I did give a rigorous proof that ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ is countable. This rigorous proof is posted here.
- Today in class I demonstrated the bijection between ${\mathbb Z}^+$ and ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ using this Mathematica notebook. In this notebook I give an explicit formula for a bijection between ${\mathbb Z}^+$ and ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ and its inverse. These formulas are illustrated with appropriate graphs.
-
In January 11 post I explained how to use Mathematica notebooks.
Open Mathematica first, then open the file that you downloaded from Mathematica 5.2. You can execute the entire notebook by the following manu sequence (in Mathematica):
Kernel -> Evaluation -> Evaluate Notebook. - Earlier in class I mentioned The On-Line Encyclopedia of Integer Sequences
- In particular 1,2,2,3,3,3,4,4,...
- I updated the file with some basic properties of the integers deduced from the axioms.
- We started Section 3.2 today. We covered definition of a sequence, and several examples of sequences; in particular geometric progression, arithmetic progression, and examples listed in Table 1. I proved the formulas \[ \forall \, n \in \mathbb N \qquad \displaystyle \sum_{k=1}^n k \ = \ \dfrac{n(n+1)}{2} \] and \[ \forall \, n \in {\mathbb Z}^+ \ \forall \, a \in {\mathbb R} \ \forall \, d \in {\mathbb R} \quad \sum_{k=0}^n \bigl(a + k\, d\bigr) =(n+1) a + \dfrac{n(n+1)}{2}\, d = (n+1)\left( a + \dfrac{n}{2}\, d \right), \] and \[ \forall \, n \in {\mathbb Z}^+ \ \ \forall \, r \in {\mathbb R}\setminus\{0,1\} \qquad \sum_{k=0}^n a \, r^k = a \dfrac{r^{n+1} - 1}{r - 1} = a \dfrac{1-r^{n+1}}{1-r}. \] Here I use the notation $A\setminus B$ for the set difference of two sets. This notation is more common than $A-B$ used in the book.
- We will skip parts about infinite series since that is covered in Math 226.
- Read Section 3.2. Do the exercises 2, 4, 5, 6, 9, 11, 12, some of 13-18, 19, 20, 21, 23, 31, 32. Notice that Exercises 11 and 12 are more challenging.
- I updated the file with some basic properties of the integers deduced from the axioms.
- The axioms for the integers are posted here.
- Some basic properties of integers deduced from the axioms can be found here.
-
Let $A$ and $B$ be two nonempty sets. The set of all functions $f: A \to B$ from $A$ to $B$ is denoted by $B^A$.
The reason for this notation is that if the set $A$ has $m$ elements and the set $B$ has $n$ elements,
then the set $B^A$ has $n^m$ elements. You can easily see that this is true for small sets.
For example if $A=\{\bigcirc,\square\}$ and $B=\{1,2,3\}$ then we can list all the functions from $A$ to $B$ in a table:
$f_1$ $f_2$ $f_3$ $f_4$ $f_5$ $f_6$ $f_7$ $f_8$ $f_9$ $\boldsymbol\bigcirc$ $1$ $1$ $1$ $2$ $2$ $2$ $3$ $3$ $3$ $\boldsymbol\square$ $1$ $2$ $3$ $1$ $2$ $3$ $1$ $2$ $3$ -
In class I proved that for an arbitrary nonempty set $A$ there exist a bijection between the power set of
$A$ and the set $\{0,1\}^A$. Before presenting a formal proof look at one example.
Consider $A=\{\blacktriangle,\diamond,\bullet,\star\}$. The table below indicates what the bijection should be.
The top part of the table contains sixteen functions in $\{0,1\}^A$;
the bottom part contains the subsets of $A$ that are related to the functions above them.
While reading the proof below you should refer to the preceding table for an illustration.$f_1$ $f_2$ $f_3$ $f_4$ $f_5$ $f_6$ $f_7$ $f_8$ $f_9$ $f_{10}$ $f_{11}$ $f_{12}$ $f_{13}$ $f_{14}$ $f_{15}$ $f_{16}$ $\blacktriangle$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $1$ $1$ $1$ $1$ $1$ $1$ $1$ $1$ $\diamond$ $0$ $0$ $0$ $0$ $1$ $1$ $1$ $1$ $0$ $0$ $0$ $0$ $1$ $1$ $1$ $1$ $\bullet$ $0$ $0$ $1$ $1$ $0$ $0$ $1$ $1$ $0$ $0$ $1$ $1$ $0$ $0$ $1$ $1$ $\star$ $0$ $1$ $0$ $1$ $0$ $1$ $0$ $1$ $0$ $1$ $0$ $1$ $0$ $1$ $0$ $1$ s u b s e t$\emptyset$ $\{\star\}$ $\{\bullet\}$ $\left\{\begin{array}{c}\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ $\{\diamond\}$ $\left\{\begin{array}{c}\!\!\diamond\!\!\\\!\!\star\!\!\end{array}\right\}$ $\left\{\begin{array}{c}\!\!\diamond\!\!\\\!\!\bullet\!\!\end{array}\right\}$ $\left\{\begin{array}{c}\!\!\diamond\!\!\\\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ $\{\blacktriangle\}$ $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\star\!\!\end{array}\right\}$ $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\bullet\!\! \end{array}\right\}$ $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\! \end{array}\right\}$ $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\!\\\!\!\star\!\! \end{array}\right\}$ $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\!\\\!\!\bullet\!\! \end{array}\right\}$ $\left\{\begin{array}{c}\!\!\blacktriangle\!\!\\\!\!\diamond\!\!\\\!\!\bullet\!\!\\\!\!\star\!\! \end{array}\right\}$ -
Proposition. For an arbitrary nonempty set $A$ there exist a bijection between the power set of $A$ and the set $\{0,1\}^A$.
-
Proof. First we define a function $\Phi$ from ${\mathcal P}(A)$ to $\{0,1\}^A$. Let $X$ be an arbitrary subset of $A$. We need to define $\Phi(X)$ as a function from $A$ to $\{0,1\}$. For an arbitrary $a \in A$ we define \[ \bigl(\Phi(X)\bigr)(a) = \begin{cases} 0 & \ \text{if} \quad a \not\in X, \\[7pt] 1 & \ \text{if} \quad a \in X. \end{cases} \] Clearly, $\Phi(X) \in \{0,1\}^A$. (For example, in the above table, if $X = \{\blacktriangle,\bullet,\star\}$, then $\Phi(X) = f_{12}$.)
Next we prove that $\Phi$ is a surjection. Let $f \in \{0,1\}^A$ be arbitrary. We need to define $X \subseteq A$ such that $\Phi(X) = f$. We define $X = \{x \in A \ | \ f(a) = 1 \}$. With this $X$ we need to prove that $\Phi(X) = f$, that is $\bigl(\Phi(X)\bigr)(a) = f(a)$ for all $a \in A$. We distinguish two cases: Case 1: $f(a) = 1$ and Case 2: $f(a) = 0$. (These two cases cover all possibilities since $f(a) \in \{0,1\}$.) Case 1. Assume $f(a) = 1$. Then $a \in X$, and by the definition of $\Phi(X)$ we have $\bigl(\Phi(X)\bigr)(a) = 1$. Thus, in this case $\bigl(\Phi(X)\bigr)(a) = f(a)$. Case 2. Assume $f(a) = 0$. Then $a \not\in X$, and by the definition of $\Phi(X)$ we have $\bigl(\Phi(X)\bigr)(a) = 0$. Thus, in this case $\bigl(\Phi(X)\bigr)(a) = f(a)$. This proves that $\Phi$ is a surjection.
It remains to prove that $\Phi$ is an injection. Let $X, Y$ be arbitrary subsets of $A$ such that $X \neq Y$. We need to prove $\Phi(X) \neq \Phi(Y)$. Since $X \neq Y$ there exists $a \in A$ such that $a \in X$ and $a \not\in Y$ or there exists $b \in A$ such that $b \not\in X$ and $b \in X$. If there exists $a \in A$ such that $a \in X$ and $a \not\in Y$, then $\bigl(\Phi(X)\bigr)(a) = 1$ and $\bigl(\Phi(Y)\bigr)(a) = 0$, hence $\Phi(X) \neq \Phi(Y)$ in this case. If there exists $b \in A$ such that $b \not\in X$ and $b \in Y$, then $\bigl(\Phi(X)\bigr)(b) = 0$ and $\bigl(\Phi(Y)\bigr)(b) = 1$, hence $\Phi(X) \neq \Phi(Y)$ in this case as well. This completes the proof.
A different way to prove this proposition would be to define the function $\Psi: \{0,1\}^A \to {\mathcal P}(A)$ by \[ \Psi(f) = \bigl\{a \in A \,|\, f(a) = 1 \bigr\}, \quad f \in \{0,1\}^A, \] and prove that $\Psi$ is the inverse of $\Phi$. That is, prove that
$\forall \, X \in {\mathcal P}(A) \quad \Psi\bigl(\Phi(X)\bigr) = X$ and $\forall \, f \in \{0,1\}^A \quad \Phi\bigl(\Psi(f)\bigr) = f$.
One could make a claim that the boxed propositions above are obvious. However, it would take some writing to prove them formally.
-
- Today we discussed, among other things, two important equivalences involving the functions floor and ceiling. I state them formally below.
- Here are two equivalent statements involving the floor function:
$\forall x\in {\mathbb R} \ \ \forall k \in {\mathbb Z} \quad x \geq k \ \Leftrightarrow \ \lfloor x \rfloor \geq k$
$\forall x\in {\mathbb R} \ \ \forall k \in {\mathbb Z} \quad x \lt k \ \Leftrightarrow \ \lfloor x \rfloor \lt k$
- First, we prove the implication $\forall x\in {\mathbb R}$ and $\forall k \in {\mathbb Z}$ we have $x \lt k$ $\Rightarrow$ $\lfloor x \rfloor \lt k$.
Proof. Let $x \in {\mathbb R}$ and $k \in {\mathbb Z}$ be arbitrary. Assume $x \lt k$. Recall that by the definition of floor we have $\lfloor x \rfloor \leq x$. The last two green boxes and the transitivity property of inequality imply $\lfloor x \rfloor \lt k$. This completes the proof.
-
Second, we prove the implication $\forall x\in {\mathbb R}$ and $\forall k \in {\mathbb Z}$ we have $\lfloor x \rfloor \lt k$ $\Rightarrow$ $x \lt k$.
Proof. Let $x \in {\mathbb R}$ and $k \in {\mathbb Z}$ be arbitrary. Assume $\lfloor x \rfloor \lt k$. Then $k - \lfloor x \rfloor \gt 0$; that is, $k - \lfloor x \rfloor$ is a positive integer. Since $1$ is the smallest positive integer, we have $k - \lfloor x \rfloor \geq 1$. Therefore $\lfloor x \rfloor + 1 \leq k$. By the definition of floor we have $x \lt \lfloor x \rfloor + 1$. The last two green boxes and the transitivity property of inequality imply that $x \lt k$. This completes the proof.
- First, we prove the implication $\forall x\in {\mathbb R}$ and $\forall k \in {\mathbb Z}$ we have $x \lt k$ $\Rightarrow$ $\lfloor x \rfloor \lt k$.
- Here are two equivalent statements involving the ceiling function:
$\forall x\in {\mathbb R} \ \ \forall k \in {\mathbb Z} \quad x \leq k \ \Leftrightarrow \ \lceil x \rceil \leq k$
$\forall x\in {\mathbb R} \ \ \forall k \in {\mathbb Z} \quad x \gt k \ \Leftrightarrow \ \lceil x \rceil \gt k$
- Read 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, 44, 45, 48, 49, 56, 58, 60(f), 65, 66 ((b) and (d) in 66 are wrong)
-
Here I state a formal definition of function. This definition 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$.
- While reading Section 1.8. Pay attention to the following concepts.
- function, domain, codomain, range,
- one-to-one function (I prefer the synonym: injection)
- onto function (I prefer the synonym: surjection)
-
bijection
A comment on terminology:
Our textbook and many other books use the synonym phrase "one-to-one correspondence".
Here are three reasons why "bijection" is preferable to "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.
- inverse function
- composition of functions
- Table 1 with the basic properties of the floor and ceiling functions.
- Wikipedia's Function page:
- Read Section 1.7. 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:
- Here is the link to a page that gives 23 proofs that $\sqrt{2}$ is irrational. However, the proof that I gave below is not included.
- We started Section 1.6: Sets yesterday. Do the exercises 1 - 21, 24, 25, 27, 28.
- Some relevant Wikipedia links:
- 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.)
- Read 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.
-
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 \ \ \ cb \gt a$ (the universe of discourse consists of all real numbers)
- $\forall\, a \ \forall\, b \ \exists\, c \ \ \ cb \gt a$ (the universe of discourse consists of all positive real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \ \ \ z \gt y \Rightarrow zx \gt 1$ (the universe of discourse consists of all real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \ \ \ z \gt y \Rightarrow zx \gt 1$ (the universe of discourse consists of all positive real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \ \ \ z \gt y \Rightarrow z^2 \gt x^2$ (the universe of discourse consists of all real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \ \ \ z \gt y \Rightarrow z^2 \gt x$ (the universe of discourse consists of all real numbers)
- 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) \]
- 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$".
- Read 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.
- A good practice with quantified statements with two variables 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". In this statement 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 statements:Grid 1 Grid 2 Grid 3 Grid 4 
- Statement 1. $\forall j \, \exists k \ B(j,k)$
- Statement 2. $\exists k \, \forall j \ B(j,k)$
- Statement 3. $\exists j \, \forall k \ \neg B(j,k)$
- Statement 4. $\forall k \, \exists j \ B(j,k)$
- 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.
-
In class 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 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 20130111.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 20130111.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 started did Section 1.2. Do the exercises 1-13 and most 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.