- Read 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.
- I need to curve the scores on Exam 2. To help me with that I ask you to repeat a part of Exam 2 as homework. Here is a modified version of Exam 2 that is due on Thursday. I will combine two grades to get decent grades for Exam 2.
- We did Section 4.1 today.
- 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. This section requires a lot of practice.
- As we discovered in class today Exercise 18 (g) and (h) are interesting. My answer to (g) is 729. One counts separately two digit numbers and three digit numbers with distinct digits. My answer to (h) is 369. Again, you count separately two digit numbers and three digit numbers. For three digit numbers, you use the sum rule to the counts of numbers ending with 0, 2, 4, 6, and 8.
- Exam 2 is moved to Monday, August 6, 2012. It will cover Sections 1.8 (Functions), 3.2 (Sequences and summations), 3.3 (Mathematical induction), 3.4 (Recursive definitions). Also, on Wednesday, July 18, I posted a proof of the division algorithm theorem.
- Since this is a rigorous math class I gave a rigorous proof of the principle of Mathematical induction yesterday. My proof differs from the argument in the book. I think that my proof is more complete. Here is my proof. The proof uses the well-ordering axiom. I included all the details of the proof.
- 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)
-
I was asked to post old exams from my previous 209 classes. Here they are:
- Exam 1 Winter 2011.
- Exam 1 Spring 2012.
- Exam 2 Winter 2011.
- Exam 2 Spring 2012.
- Exam 3 Winter 2011.
- Final Exam Winter 2011.
- Final Exam Spring 2012.
- We finished Section 3.2. Today I proved that the set of real numbers between $0$ and $1$ is not countable. Denote this set by $\mathbb I$, that is ${\mathbb I} = \bigl\{ x \in {\mathbb R} \, | \, (0 \lt x) \, \wedge \, (x \lt 1) \bigr\}$. The set ${\mathbb I}$ is commonly denoted as $(0,1)$. Sometimes it is called the open unit interval in $\mathbb R$. I proved \[ \forall\, f: {\mathbb Z}_+ \to {\mathbb I} \quad \exists \, y \in {\mathbb I} \quad \forall \, n \in {\mathbb Z}_+ \quad f(n) \neq y. \] Or in simple English, there does not exist a surjection from ${\mathbb Z}_+$ onto ${\mathbb I}$. Consequently, there does not exist a bijection from ${\mathbb Z}_+$ onto ${\mathbb I}$. This implies that $\mathbb I$ is not countable.
- 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 went over all the details of my post of July 24 related to Exercise 11 of Section 3.2. It turns out to be a beautiful exercise. Who would expect that the inverse of the function $\ a(n) = n + \bigl\lfloor \sqrt{n} \bigr\rceil$ defined for all $n \in {\mathbb Z}_+\ $ is the function $a^{-1}(p) = p - \bigl\lfloor \sqrt{p} \bigr\rfloor$ defined for all non-square positive integers $p$.
-
We gave the definition of a countable set and proved that the following sets are countable:
- the set ${\mathbb Q}_+$ of all positive rational numbers, (a non-rigorous proof)
- the set ${\mathbb Z}$ of all integers; we gave a rigorous proof involving the bijection $f: {\mathbb Z}_+ \to {\mathbb Z}$ and its inverse given by \[ f(n) = (-1)^n \left\lfloor \frac{n}{2} \right\rfloor, \ \ n \in {\mathbb Z}_+, \qquad f^{-1}(z) = 2\, | z | + {\rm us}(-z), \ \ z \in {\mathbb Z}, \]
- the set of all positive non-square integers (a rigorous proof).
-
This is a good opportunity to advertise the unit step function (I called it $\rm us$ above):
\[
{\rm us}(x) = \begin{cases}0, & x \lt 0, \\[6pt] 1, & x \geq 0. \end{cases}
\]
- Here is the Mathematica 5.2 file that I used today. It is called 20120725.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. To evaluate particular cells in Mathematica, place the cursor in a cell and press Shift+Enter.
-
Here is a solution to Exercise 11.
-
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}$.
- Step 1. 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:
To summarize, we have proved that \[ \forall\, n \in {\mathbb Z}_+ \ \ \forall\, q \in {\mathbb Z}_+ \qquad \bigl\lfloor \sqrt{n} \bigr\rceil = q \quad \Leftrightarrow \quad q^2 \lt n + q \lt (q + 1)^2. \]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$ - Step 2. The second step towards solving Exercise 11 is to characterize the equality $\bigl\lfloor \sqrt{p} \bigr\rfloor = r$. Here $p, r \in {\mathbb Z}_+$. The following equivalences hold:
Denote by ${\mathbb S}$ the set of all positive squares, that is \[ {\mathbb S} = \bigl\{x \in {\mathbb Z}_+ \, | \, \exists\,y \in {\mathbb Z}_+ \ \ x = y^2 \bigr\}. \] It is easy to see that $\ p\ $ is a square if and only if $p = \bigl\lfloor \sqrt{p} \bigr\rfloor^2$. That is $p \in {\mathbb S}$ if and only if $p = \bigl\lfloor \sqrt{p} \bigr\rfloor^2$. The contrapositive of the last equivalence is $p \not\in {\mathbb S}$ if and only if $p \gt \bigl\lfloor \sqrt{p} \bigr\rfloor^2$. Together with the equivalence established at the beginning of this step this yields \[ \forall\, p \in {\mathbb Z}_+ \ \ \forall\, r \in {\mathbb Z}_+ \qquad (p \not\in {\mathbb S}) \, \wedge \,\bigl( \bigl\lfloor \sqrt{p} \bigr\rfloor = r \bigr) \quad \Leftrightarrow \quad r^2 \lt p \lt (r + 1)^2. \]by definition: $\bigl\lfloor \sqrt{p} \bigr\rfloor = r$ $\Leftrightarrow$ $r \leq \sqrt{p} \lt r + 1$ by squaring positive numbers
$\Leftrightarrow$ $r^2 \leq p \lt (r+1)^2$ - Now we can solve Exercise 11. Let $n, p \in {\mathbb Z}_+$. The following equivalences hold:
To summarize, we have just proved the following equivalence: \[ \forall\, n \in {\mathbb Z}_+ \ \ \forall\, p \in {\mathbb Z}_+ \qquad n + \bigl\lfloor \sqrt{n} \bigr\rceil = p \quad \Leftrightarrow \quad \bigl(p \not\in {\mathbb S}\bigr) \ \wedge \ \bigl( n = p - \bigl\lfloor \sqrt{p} \bigr\rfloor \bigr). \] The last equivalence proves that the function $\ a(n) = n + \bigl\lfloor \sqrt{n} \bigr\rceil$ defined for all $n \in {\mathbb Z}_+\ $ is a bijection between the sets $\ {\mathbb Z}_+\ $ and $ \ {\mathbb Z}_+\!\!\setminus\!{\mathbb S}$. The inverse function of the function \[ a : \ {\mathbb Z}_+\ \to \ {\mathbb Z}_+\!\!\setminus\!{\mathbb S} \] is the function \[ a^{-1} : \ {\mathbb Z}_+\!\!\setminus\!{\mathbb S}\ \to \ {\mathbb Z}_+, \qquad a^{-1}(p) = p - \bigl\lfloor \sqrt{p} \bigr\rfloor, \quad p \in {\mathbb Z}_+\!\!\setminus\!{\mathbb S}. \]$n + \bigl\lfloor \sqrt{n} \bigr\rceil = p$ $\Leftrightarrow$ $\bigl(\bigl\lfloor \sqrt{n} \bigr\rceil = q\bigr) \, \wedge \, \bigl( n+q = p \bigr) $ by the final equivalence in Step 1
$\Leftrightarrow$ $\bigl(q^2 \lt p \lt (q+1)^2\bigr) \, \wedge\, \bigl( n+q = p \bigr)$ by the final equivalence in Step 2
$\Leftrightarrow$ $(p \not\in {\mathbb S}) \, \wedge \,\bigl( \bigl\lfloor \sqrt{p} \bigr\rfloor = q \bigr) \wedge\, \bigl( n+q = p \bigr) $ by substitution
$\Leftrightarrow$ $ (p \not\in {\mathbb S}) \, \wedge\, \bigl( n+\bigl\lfloor \sqrt{p} \bigr\rfloor = p \bigr) $ by algebra
$\Leftrightarrow$ $ (p \not\in {\mathbb S}) \, \wedge\, \bigl( n = p - \bigl\lfloor \sqrt{p} \bigr\rfloor \bigr) $
-
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$:
-
Here is a hint for Exercise 12.
-
To solve Exercise 12, for arbitrary $n \in {\mathbb Z}_+$ prove the equivalence:
$\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = q \ $ if and only if $ \ \dfrac{q(q-1)}{2} \lt n \leq \dfrac{q(q+1)}{2}$.
-
To solve Exercise 12, for arbitrary $n \in {\mathbb Z}_+$ prove the equivalence:
- 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.
- Today I will prove few simple consequences of the axioms of $\mathbb Z$.
-
Cancelation property for addition.
- Proposition. $\forall \, a \in {\mathbb Z} \ \forall \, b \in {\mathbb Z} \ \forall \, c \in {\mathbb Z} \quad a+c=b+c \ \Rightarrow \ a=b$.
-
Proof. In this proof we refer to the axioms abbreviations
here.
- Let $a, b, c \in {\mathbb Z}$. Assume $a+c=b+c$.
- Let $a, b, c \in {\mathbb Z}$. Assume $a+c=b+c$.
- We will continue with Section 3.2. Before continuing I want to prove the theorem called the division algorithm.
- First recall our notation. By ${\mathbb Z}$ we denote the set of all integers and ${\mathbb Z}^+$ denotes the set of all positive integers.
- The basic properties of ${\mathbb Z}$ are given as the axioms of ${\mathbb Z}$. You can find the axioms of ${\mathbb Z}$ here. All other familiar properties of ${\mathbb Z}$ can be deduced from the axioms. Tomorrow I will post some examples of proofs of simple propositions about integers using axioms.
- Here is the division algorithm theorem:
- Theorem. Let $n$ be an integer and let $d$ be a positive integer. Then there exist unique integers $q$ and $r$ such that \[ n = dq + r \ \ \ \wedge \ \ \ 0 \leq r \lt d. \]
- Before proceeding with a proof let us state the theorem using quantifiers: \[ \forall\, n \in {\mathbb Z} \ \forall\, d \in {\mathbb Z}^+ \ \exists\, q \in {\mathbb Z} \ \exists\, r \in {\mathbb Z} \quad \bigl(n = dq + r \bigr) \, \wedge\, \bigl(0 \leq r \lt d \bigr) \]
-
Proof. Let $n \in {\mathbb Z}$ and let $d \in {\mathbb Z}^+$.
Step 1. Define the set \[ S = \Bigl\{ k \in {\mathbb Z} \ \bigl| \bigr. \ \bigl(k \geq 0\bigr) \wedge \bigl(\exists \, j \in {\mathbb Z} \quad k = n - dj\bigr) \Bigr\}. \] Step 2. We want to apply the well ordering axiom to $S$. Since the well ordering axiom (WO) is an implication we need to verify its three assumptions.- By the definition of $S$ we have $S \subset {\mathbb Z}$.
-
Here we prove that $S$ is a nonempty set. We distinguish two cases for $n$: $n \geq 0$ and $n \lt 0$.
- If $n \geq 0$, then $n \in S$ since $n = n - d\cdot 0 \geq 0$. That is we can take $j=0$.
- Now assume that $n \lt 0$. Then $-n \gt 0$. Now $-n \gt 0$ and $d \geq 1$, implies $-nd \geq -n$. Adding $n$ to both sides of $-nd \geq -n$ we get $n-d n \geq n-n =0$. Hence $k = n - d n \in S$, since we can take $j = n$. In each case we identified an integer in $S$, so $S$ is always a nonempty set.
- By the definition of $S$ all integers in $S$ are nonnegative. By the Well ordering axiom of ${\mathbb Z}$ the set $S$ has a minimum. Denote that minimum by $r$. The integer $r$ has the following two properties: $r \in S$ and $r \leq k$ for all $k \in S$.
Step 3. Since $r \in S$, we have $r \geq 0$ and there exists $q \in {\mathbb Z}$ such that $r = n - dq$. Hence we proved that there exist integers $r$ and $q$ such that $n = dq+r$ and $r \geq 0$.
Step 4. It remains to prove that $r \lt d$. Consider the integer $r-d$. As $d \gt 0$ we have $r-d \lt r$. Since $x \in S$ implies $r \leq x$, the contrapositive of the last implication yields $r-d \not\in S$. By the definition of $S$, $r-d \not\in S$ means \begin{equation} \label{eqvee} \bigl(r-d \lt 0 \bigr) \ \vee \ \bigl( \forall \, j \in {\mathbb Z} \ \ r-d \neq n-dj\bigr). \end{equation} However, we have \[ r-d = n-dq -d = n -d(q+1). \] That it the following is true: \begin{equation} \label{eqnot} \exists \, j \in {\mathbb Z} \qquad r-d = n-dj. \end{equation} Since the proposition in \eqref{eqnot} is the negation of the second proposition in the disjunction in \eqref{eqvee}, the disjunctive syllogism, \eqref{eqvee} and \eqref{eqnot} yield $r-d \lt 0$. That is $r \lt d$.
Step 5. Here we prove the uniqueness of $q$ and $r$. Assume $q, q^{\prime}, r, r^{\prime} \in \mathbb Z$ and \begin{equation} \label{eq4} n = dq + r \quad \wedge \quad 0 \leq r \lt d \quad \wedge \quad n = dq^{\prime} + r^{\prime} \quad \wedge \quad 0 \leq r^{\prime} \lt d. \end{equation} From \eqref{eq4} it follows that $0 \leq r \lt d$ and $-d \lt -r^{\prime} \leq 0$. Adding the last two expressions we get \begin{equation} \label{eq4a} -d \lt r-r^{\prime} \lt d. \end{equation} From \eqref{eq4} it follows that $r = n-dq$ and $r^{\prime} = n - d q^{\prime}$. Substituting the last two equalities in \eqref{eq4a} we get \[ -d \lt -dq + dq^{\prime} \lt d. \] Since $d \gt 0$ the last displayed relation yields \[ -1 \lt -q + q^{\prime} \lt 1. \] Since $-q + q^{\prime} \in \mathbb Z$ the last displayed relation yields $-q + q^{\prime} =0$. That is $q^{\prime} = q$. Consequently, using $r = n-dq$ and $r^{\prime} = n - d q^{\prime}$, we get \[ r^{\prime} = n - dq^{\prime} = n - dq = r. \] - Now that the proof is finished we might wonder if there is a formula for $q$. Substituting $r = n - dq$ in $0 \leq r \lt d$ we get \[ 0 \leq n-dq \lt d. \] Since $d \gt 0$, dividing the last displayed relation by $d$ gives \[ 0 \leq \frac{n}{d} - q \lt 1. \] Adding $q$ to each term of the last relation yields \[ q \leq \frac{n}{d} \lt q+1. \] Now recall that $q \in \mathbb Z$. By the definition of the floor function the last displayed relation yields a formula for $q$ and consequently a formula for $r$: \[ q = \left\lfloor \frac{n}{d} \right\rfloor, \qquad r = n - d \left\lfloor \frac{n}{d} \right\rfloor. \]
- 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 \ \to \ 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:
- We almost finished Section 1.6: Sets today. 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 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.
- 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.
- 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, 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.
-
I was asked to comment on Problem 41 Section 1.3. In this problem we are given two propositional functions $P(x)$ and $Q(x)$ with the same universe of discourse and we are asked whether the propositions $\forall\, x \ \bigl(P(x) \to Q(x) \bigr)$ and $\bigl(\forall\, x \ P(x) \bigr) \to \bigl(\forall\, y \ Q(y) \bigr)$. Call the first proposition $a$ and the second one $b$. Below I will analyze the relationship between $a$ and $b$.
- As the first step towards understanding of these two propositions I state their negations. The negation of $a$, that is $\forall\, x \ \bigl(P(x) \to Q(x) \bigr)$, is $\exists\, x \ \bigl(P(x) \wedge \neg Q(x) \bigr)$. The negation of $b$, that is $\bigl(\forall\, x \ P(x) \bigr) \to \bigl(\forall\, y \ Q(y) \bigr)$, is $\bigl(\forall\, x \ P(x) \bigr) \wedge \bigl(\exists \, y \ \neg Q(y) \bigr)$.
- Next I look at the negations: $\neg b$ is $\bigl(\forall\, x \ P(x) \bigr) \wedge \bigl(\exists \, y \ \neg Q(y) \bigr)$ and $\neg a$ is $\exists\, z \ \bigl(P(z) \wedge \neg Q(z) \bigr)$. The proposition $\neg b$ says that $P(x)$ is true for all $x$ and there exist at least one $y$ such that $\neg Q(y)$ is true. Setting $z = y$ we see that then $\bigl(P(z) \wedge \neg Q(z) \bigr)$ is true, that is $\exists\, z \ \bigl(P(z) \wedge \neg Q(z) \bigr)$ is true. Hence $\neg a$ is true. In other words we proved that $\neg b \to \neg a$ is true.
- Next I ask whether $\neg a \to \neg b$ is true. It is not difficult to see that $\neg a \to \neg b$ is not true. For example consider the propositional functions $P(x)$ $x > 0$ and $Q(x)$ $x \neq 1$. Then $\exists\, z \ \bigl(P(z) \wedge \neg Q(z) \bigr)$ is true. Just take $z = 1$. However, $\bigl(\forall\, x \ P(x) \bigr)$ is not true. Hence $\bigl(\forall\, x \ P(x) \bigr) \wedge \bigl(\exists \, y \ \neg Q(y) \bigr)$ is not true.
- With the same example $P(x)$ $x > 0$ and $Q(x)$ $x \neq 1$ the proposition $\forall\, x \ \bigl(P(x) \to Q(x) \bigr)$ is not true (just take $x=1$) and the proposition $\bigl(\forall\, x \ P(x) \bigr) \to \bigl(\forall\, y \ Q(y) \bigr)$ is true since both $\bigl(\forall\, x \ P(x) \bigr)$ and $\bigl(\forall\, y \ Q(y) \bigr)$ are false.
-
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 \to zx \gt 1$ (the universe of discourse consists of all real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \ \ \ z \gt y \to zx \gt 1$ (the universe of discourse consists of all positive real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \ \ \ z \gt y \to z^2 \gt x^2$ (the universe of discourse consists of all real numbers)
- $\forall\, x \ \exists\, y \ \forall\, z \ \ \ z \gt y \to z^2 \gt x$ (the universe of discourse consists of all real numbers)
- 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.
- Read 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.
- 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". 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 reviewed Section 1.1 and Section 1.2. I forgot to introduce the concept of a tautology. A tautology is a compound proposition that is true for all possible values of its components. The simplest tautology is $(\neg p) \vee p$. Another example is: $\bigl((p \to q) \wedge (q \to r) \bigr) \to (p\to r)$.
-
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 \wedge (\neg q) \bigr) \vee r \ \ $
where
$p\ $ stands for: $q\ $ stands for: $r\ $ 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 20120621.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 20120621.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 posted please let me know. If you spend some time learning how to use these files you will enhance the understanding of math that we are studying and also learn the basics of these software packages.
- Today we 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.
- Here is a pdf file of the first few sections of the book.