- Here is a list of topics for the final exam.
- 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 today. For Section 4.3 do as many exercises as you can from 1-43.
- We also did most of Section 4.4 today. For Section 4.4 do the exercises: 1-13, 21, 22, 28, 29, 30.
- For me, the easiest way to internalize Pascal's identitiy \[ \binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} \] is to think of it as counting committees of $k$ people from a class of $n$ students AND ME. The following is the count of ALL such committees: \[ \text{ALL} \quad \binom{n+1}{k} \] such committees. There are two kinds of such committees: the Fist kind: ME committies on which I am a member and the Second kind: NOME committees on which I am not a member. Below are the counts of these two kinds of committees: \[ \text{ME} \quad \binom{n}{k-1} \qquad \text{NOME} \quad \binom{n}{k} \] So, Pascal's identity can be rewritten as \[ \text{ALL} = \text{ME} + \text{NOME} \] and nicknamed MENOME identity.
- 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$ such that $A\subset 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.
- Problem 1 on Assignment 2 might be easier to prove after seeing the proof below.
-
Consider the following sequence:
\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
- I wrote a list of topics for Exam 2.
- In Section 3.2 we skiped parts about infinite series since that is covered in Math 226.
- The most important formulas in Section 3.2 are related to geometric progression, arithmetic progression. We 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.
- In 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.
- In Section 3.3 you can skip Examples 10, 12, 13 and the subsection "The well-ordering property" is an alternative approach to the proof of Mathematical induction. I presented my own proof of the Mathematical Induction base on the Well Ordering Axiom.
- In Section 3.3 suggested exercises are 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 need to include a small part of Section 3.4, up to Theorem 1 on page 260. The relevant exercises here are: 1, 2, 3, 4, 5, 7, 8, 9, 12, 13, 14, 15, 16, just more induction.
- We did Section 3.2 and Section 3.3 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.
-
Notice that in class I gave a more restrictive definition of countability than what is in the textbook.
Definition A nonempty set $S$ is called countable if there exists a bijection $f: {\mathbb Z}^+ \to S.$
-
When talking about cardinality of a set I like to point out the following quadruplicity: A set can be exactly one of the following exclusive four possibilities:
- 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}^+$ and 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 three kinds.)
-
It is common to consider finite sets as being countable. Sometimes even the empty set is included in countable sets. The advantage of the above quadruplicity is that the definition of each of the classes exept the last one is simple. An alternative to the above quadruplicity would be to first introduce the dichotomy: All sets are classified in two classes
- countable sets (The definition is given below.)
- uncountable sets (These are sets which are not countable.)
- $S$ is an empty set (This is the unique set which has no elements.)
- There exists $n\in {\mathbb Z}^+$ and a bijection $f: \{1,\ldots,n\} \to S.$ Sets satisfying this condition are said to be finite.
- There exists a bijection $f: {\mathbb Z}^+ \to S.$ Sets satisfying this condition are said to be countably infinite.
- On February 14 I consturcted a bijection between $\mathbb{N}$ and $\mathbb{Z}.$ Similarly one can construct a bijection between $\mathbb{Z}^+$ and $\mathbb{Z}.$ Please do this as an exercise. This would provide a rigorous proof that ${\mathbb Z}$ is countable.
- I got completely legitimate question of an existence of an uncountable set. The most famous uncountable set is $\mathbb{R}.$ To prove this we have to use properties of real numbers. Since this is not the main focus of this class I decided to present another uncountable set $\mathcal{P}(\mathbb{Z}^+)$ for which I can give a complete proof of its uncountability. Recall $\mathcal{P}(\mathbb{Z}^+)$ is the power set of $\mathbb{Z}^+,$ that is the set of all subsets of $\mathbb{Z}^+.$
-
Proposition. There does not exist a surjection from $\mathbb{Z}^+$ onto $\mathcal{P}(\mathbb{Z}^+).$
-
Proof. Let \[ f : \mathbb{Z}^+ \to \mathcal{P}(\mathbb{Z}^+) \] be an arbitrary function from $\mathbb{Z}^+$ to $\mathcal{P}(\mathbb{Z}^+).$ We will prove that $f$ is not a surjection. To prove that $f$ is not a surjection we need to prove that there exists a subset $S$ of $\mathbb{Z}^+$ such that for all $k in \mathbb{Z}^+$ we have $f(k) \neq S.$ That is, \[ \exists\, S \in \mathcal{P}(\mathbb{Z}^+) \ \ \forall k \in \mathbb{Z}^+ \quad f(k) \neq S. \] Notice that $f(k) \in \mathcal{P}(\mathbb{Z}^+)$ for all $k \in \mathbb{Z}^+.$ We define the set $S$ as follows \[ S = \bigl\{ n \in \mathbb{Z}^+ \, | \, n \not\in f(n) \bigr\}. \] Visualize forming the set $S$ as follows: Decide whether to put $1$ in $S$ or not; look at the set $f(1)$ which is given by the function $f$; if $1 \in f(1)$ we do not put it in $S$; if $1\not\in f(1)$, then we put $1$ in $S$; now we proceed to $2$ and so on.
Now we prove the for every $k \in \mathbb{Z}^+$ we have $f(k) \neq S.$ Let $k \in \mathbb{Z}^+$ be arbitrary. We distinguish two cases. Case 1. In this case $k\in f(k).$ By the definition of $S$ in this case we have $k \not\in S.$ Hence, \[ \bigl( k\in f(k) \bigr) \wedge \bigl( k \not\in S \bigr). \] Thus, $f(k) \neq S$ in this case. Case 2. In this case $k\not\in f(k).$ By the definition of $S$ in this case we have $k \in S.$ Hence, in this case \[ \bigl( k\not\in f(k) \bigr) \wedge \bigl( k \in S \bigr) \] Thus, $f(k) \neq S$ in this case. This proves that $f(k) \neq S$. Since $k \in \mathbb{Z}^+$ was arbitrary, by universal generalization it follows that $f(k) \neq S$ for all $k \in \mathbb{Z}^+.$ This completes the proof.
- Today we discussed the importance of axioms in mathematics. We will illustrate the role of axioms in mathematics with the Axioms for the Integers; a pdf file is here. Notice that the axioms in these files are somewhat different from what I presented in class. I indicated in class that I did not like how I introduced the concept of order in the previous version. After the class Stephen (Doorenbos) told me that my logical statement of the trichotomy axiom for order was wrong. I overlooked that $p\oplus q \oplus r$ does not mean that exactly one of these three propositions is true. As an exercise construct a truth table for $p\oplus q \oplus r$, it is interesting. Therefore, instead of order in the axioms of integers I introduce the set of positive integers. Then order can be defined using the concept of a positive integer.
- Please look at my file with Basic Properties of Integers. We will discuss this next.
-
A surprising aspect of an infinite set is that there can exist a bijection between an infinite set and its proper subset. Here we demonstrate this with sets
\begin{align*}
\mathbb Z & = \{\ldots, -2, -1, 0, 1, 2, \ldots \} \\
\mathbb N & = \{0, 1, 2, \ldots \}
\end{align*}
Clearly $\mathbb N$ is a proper subset of $\mathbb Z.$ As you can see from the plot below there is a bijection from the navy blue points representing the integers onto forest green points representing the natural numbers. This bijection is indicated by blue arrows. Its formula is
\[
\forall \, z \in \mathbb Z \quad f(z) = -\frac{1}{2} + 2 \left| z + \frac{1}{4} \right|
\]
The inverse of this bijection is the function from the forest green points representing the natural numbers onto the navy blue points representing the integers. This bijection is indicated by the green arrows in the plot below. Its formula is
\[
\forall \, n \in \mathbb N \quad g(n) = (-1)^n \left\lceil \frac{n}{2} \right\rceil.
\]
Bijection between $\mathbb N$ and $\mathbb Z$
- Recall 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$.
- Recall 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$.
- Recall 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$.
-
We assume that $F$ is a bijection. Let us rephrase all four assumptions about $F$ in terms of 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\}\cup \mathbb R^+ , & \quad B & =\{0\}\cup \mathbb R^+, & \qquad \operatorname{sq} & = \bigl\{ (x,x^2) \in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ A & = \mathbb R, & \quad B & = \mathbb R, & \qquad \operatorname{cube} & = \bigl\{ (x,x^3) \in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ A & = \mathbb R, & \quad B & = \mathbb R^+, & \qquad \operatorname{exp} & = \bigl\{ (x,e^x)\in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ A & = (-\pi/2,\pi/2), & \quad B & = \mathbb R, & \qquad \operatorname{rtan} & = \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 \operatorname{rsin} & = \bigl\{ \bigl(x,\sin(x)\bigr)\in A\!\times\!\!B \ \bigl| \bigr. \ x \in A \bigr\} \\ A & = [0,\pi], & \quad B & = [-1,1], & \qquad \operatorname{rcos} & = \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\}\cup \mathbb R^+, \ B = \{0\}\cup \mathbb R^+, \ \operatorname{sq} = \bigl\{ (x,x^2) \ \bigl| \bigr. \ x \in A \bigr\} $
$A = \mathbb R, \ B = \mathbb R, \ \operatorname{cube} = \bigl\{ (x,x^3) \ \bigl| \bigr. \ x \in A \bigr\}$
$A = \mathbb R, \ B = \mathbb R^+, \ \exp = \bigl\{ (x,e^x) \ \bigl| \bigr. \ x \in A \bigr\}$
$A = (-\pi/2,\pi/2), \ B = \mathbb R, \ \operatorname{rtan} = \bigl\{ \bigl( x,\tan(x) \bigr) \ \bigl| \bigr. \ x \in A \bigr\} $
$ A = [-\pi/2,\pi/2], \ B = [-1,1], \ \operatorname{rsin} = \bigl\{ \bigl(x,\sin(x)\bigr) \ \bigl| \bigr. \ x \in A \bigr\} $
$ A = [0,\pi], \ B = [-1,1], \ \operatorname{rcos} = \bigl\{ \bigl(x,\cos(x)\bigr) \ \bigl| \bigr. \ x \in A \bigr\} $
- Below is a formal definition of a composition of two functions.
Place the cursor over the image to start the animation.
The composition at a generic point $x$
The composition at another generic point $x$
Finding a minimum of the composition
Finding a maximum of the composition
-
The animation below illustrates the maroon composition $g\circ f$ of the navy blue function $f$ and the its inverse dark green function $g$.
Place the cursor over the image to start the animation.
- 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)
- These are important functions plotted below in navy blue.
$ \operatorname{us} = \bigl\{ (x,0) \ \bigl| \bigr. x \lt 0 \bigr\} \cup \bigl\{ (x,1) \ \bigl| \bigr. x \geq 0 \bigr\} \subset \mathbb R \times \{0,1\} $
$ \operatorname{sgn}\! =\! \bigl\{ (x,-1) \bigl| \bigr. x \lt 0 \bigr\}\! \cup\! \bigl\{(0,0)\bigr\}\! \cup \! \bigl\{ (x,1) \ \bigl| \bigr. x \gt 0 \bigr\}\! \subset\! \mathbb R \! \times\! \{-1,0,1\} $
$\operatorname{floor} = \bigl\{ (x,k) \in \mathbb R\times \mathbb Z \ \bigl| \bigr. \ k\leq x \lt k+1 \bigr\}$
$\operatorname{ceiling} = \bigl\{ (x,k) \in \mathbb R\times \mathbb Z \ \bigl| \bigr. \ k-1\lt x \leq k \bigr\}$
$\operatorname{round} = \bigl\{ (x,k) \in \mathbb R\times \mathbb Z \ \bigl| \bigr. \ k-1/2\leq x \lt k+1/2 \bigr\}$
$\operatorname{abs} = \bigl\{ (x,y) \in \mathbb R\times \mathbb R \ \bigl| \bigr. \ y = x \operatorname{sgn}(x) \bigr\}$
-
It is important to define the function $\max \mathbb R \times \mathbb R \to \mathbb R$:
\[
\forall a \in \mathbb R \ \forall b \in \mathbb R \quad \max\{a,b\} = \begin{cases}
a & \ \text{if} \ b \leq a, \\[6pt]
b & \ \text{if} \ a \lt b.
\end{cases}
\]
This is a nice connection between $\max$ and the absolute value function.
- Theorem $\forall a \in \mathbb R \ \forall b \in \mathbb R \quad \max\{a,b\} = \frac{1}{2} \bigl( |a-b| + (a+b) \bigr)$
-
Here we list some important properties of the absolute value function.
- Theorem $\forall x \in \mathbb R \quad \operatorname{abs}(x) = \max\{x,-x\}$
- Theorem $\forall x \in \mathbb R \quad x \leq \operatorname{abs}(x) \ \wedge \ -x \leq \operatorname{abs}(x)$
- Theorem $\forall x \in \mathbb R \quad \operatorname{abs}(x) = \operatorname{abs}(-x)$
- Theorem $\forall x \in \mathbb R \ \forall y \in \mathbb R \quad \operatorname{abs}(xy) = \operatorname{abs}(x) \operatorname{abs}(y)$
- Theorem $\forall x \in \mathbb R \ \forall y \in \mathbb R \quad \operatorname{abs}(x+y) \leq \operatorname{abs}(x) + \operatorname{abs}(y)$
-
Here we list some important properties of the above step functions.
- Theorem $\forall x \in \mathbb R \quad \operatorname{sgn}(x) = \operatorname{us}(x) - \operatorname{us}(-x)$
- Theorem $\forall x \in \mathbb R \quad \operatorname{us}(x) = 1+\frac{1}{2}\bigl(1-\operatorname{sgn}(x) \bigr)\operatorname{sgn}(x)$
- Theorem $\forall x \in \mathbb R \quad \operatorname{ceiling}(x) = -\operatorname{floor}(-x)$
- Theorem $\forall x \in \mathbb R \quad \operatorname{floor}(x) = -\operatorname{ceiling}(-x)$
- Theorem $\forall x \in \mathbb R \quad \operatorname{round}(x) = \operatorname{floor}(x+1/2)$
- Theorem $\forall x \in \mathbb R \quad \operatorname{round}(x) = \operatorname{ceiling}\Bigl(\frac{1}{2}\operatorname{floor}(2x)\Bigr)$
- Study Section 1.8 up to Inverse Functions and Compositions of Functions and what I posted on the website. I did not assign to many exercises in Section 1.8. I hope you can do all of these 1, 2, 4, 10, 11, 12, (skip d) 13, 14 (a) (b) (c), 15, 17, 18, 23.
-
Thank you Kai, thank you very much for the question that you asked today in class. Your question was:
- $f$ is a bounded function, that is $\exists \, a \in \mathbb R$ $\exists \, b \in \mathbb R$ $\forall \, x \in \mathbb R$ $a \leq f(x) \leq b.$
- $f$ is differentiable, that is $\forall \, x \in \mathbb R$ $\exists \, y \in \mathbb R$ $f'(x) = y.$
- $\forall \, x \in \mathbb R$ $f'(x) \geq 0.$
-
This definition is quite general and there are sigmoid functions which are not injective. For example,
\[
f(x) = \begin{cases}
\sin x & \ \text{for} \ x \in (-\pi/2,\pi/2) \\[6pt]
\operatorname{sgn}(x) & \ \text{for} \ x \in \mathbb R \setminus (-\pi/2,\pi/2)
\end{cases}
\]
The graph of this function is
This function is not injective since $f(2) = f(3) = 1$ and $2 \neq 3.$
Notice that the derivative of this function is $f'(x) = \max\{0,\cos x\} \geq 0.$ -
However, most of the examples of sigmoid functions on the Wikipedia page have the property that their derivative is positive. That is, most sigmoid functions $g$ on the Wikipedia page have the property that $\forall x \in \mathbb R$ we have $g'(x) \gt 0.$
It has been proved in differential calculus that a function with a positive derivative is increasing. That is the following implication holds: \[ \forall x \in \mathbb R \ \ g'(x) \gt 0 \quad \Rightarrow \quad \Bigl( \forall x_1 \in \mathbb R \ \forall x_2 \in \mathbb R \ \ x_1 \lt x_2 \ \Rightarrow \ g(x_1) \lt g(x_2) \Bigr) \] This implication is proved using the Mean Value Theorem
We proved in class: If a function is increasing, then it is an injection.
For example, \[ g(x) = \arctan x \] is a sigmoid function. We have \[ \forall x \in \mathbb R \quad g'(x) = \frac{1}{1+x^2} \gt 0. \] Since the derivative is positive this is an increasing function and thus an injection.
However, looking on the graph of $\arctan x$ for large values of $x$ one could doubt this conclusion
The above graph suggests that \[ \arctan 999 = \arctan 1000. \] But, it follows from the the Mean Value Theorem that \[ \arctan 1000 - \arctan 999 \gt \frac{1}{1000001} \gt 0.0000009. \] Or, for an arbitrary positive integer $n$ \[ \arctan(10^n) - \arctan(10^n-1) \gt \frac{1}{1+10^{2n}} \gt \frac{9}{10^{2n+1}}. \] In general, for arbitrary positive real numbers $x_1$ and $x_2$ such that $x_1 \lt x_2$ we have \[ \arctan x_2 - \arctan x_1 \gt \frac{1}{1+x_2^2} (x_2 - x_1) \gt 0. \] -
I want to mention that the following function
\[
f(x) = \max\bigl\{ -1, \min \{1,x\} \bigr\}
\]
- 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$.
- In the above definition the set $A$ is said to be the domain of $F$ and the set $B$ is called the codomain of $F$.
- 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.
- I handed out the first assignment yesterday. The assignment is due Thursday, February 7, 2019.
- 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:
- I updated the post of Friday with the link to a page that gives 28 proofs that $\sqrt{2}$ is irrational.
- Our next topic is Section 1.6: Sets today. Do the exercises 1 - 21, 24, 25, 27, 28.
- The word set is an interesting English word. See its Merriam-Webster dictionary page. In the setting of this class we use it as a noun, close to the meaning number 2: a number of things of the same kind that belong or are used together and number 20: a group of persons associated by common interests, and, of course, number 21: a collection of elements and especially mathematical ones (such as numbers or points). In number 21 Merriam-Webster dictionary mentions that in mathematics a set is also called class. It is true, but we will not do that in this class. A synonym that we will use is family. We will often talk about sets whose members are sets. For such a set we will use the noun family.
- This is the sentence that we collectively came up with: Please set the table with our tea set. Don't forget the silverware, we have a matching set.
- Some relevant Wikipedia links:
- 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.)
- Here is the link to a page that gives 28 proofs that $\sqrt{2}$ is irrational.
- 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 January 15 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.
- For 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)
- A good practice with quantified statements is to look at 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) \] 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$."
-
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 in the Gregorian calendar, the current standard calendar in most of the world, from Wikipedia:
Every year that is exactly divisible by four is a leap year, except for years that are exactly divisible by 100, but these centurial years are leap years if they are exactly divisible by 400.
-
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. -
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:
- 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.