Spring 2012
MATH 209: Discrete mathematics
Branko Ćurgus

Thursday, May 31, 2012

---

• 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. Exercise 41 uses the notation discussed at the end (related to Exercise 11) of the post on April 20, 2012.

---

Thursday, May 24, 2012

---

• Read Section 6.1.
• Do the exercises: 3, 4, 6, 7, 9, 14, 15, 16, 17, 19, 22, 23, 24, 25, 26, 27, 40, 41, 45.

---

Tuesday, May 22, 2012

---

• Read Section 4.5.
• Do the exercises: 1-9, 12, 14-16, 20, 21, 23, 25, 30, 31, 33, 37, 39.

---

Friday, May 18, 2012

---

• Here is the assignment. It is due on Tuesday May 29, 2012.

---

Thursday, May 17, 2012

---

• 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.

---

Tuesday, May 15, 2012

---

• 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. 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.

---

Friday, May 11, 2012

---

• The second exam is on Monday. It will cover Sections 1.8, 3.2, 3.3, 3.4, 4.1, 4.2.

---

Thursday, May 10, 2012

---

• Read Section 4.2.
• Do the exercises: 3, 4, 5, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 36, 40.

---

Monday, May 7, 2012

---

• 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.

---

Thursday, May 3, 2012

---

• 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)

---

Friday, April 27, 2012

---

• Read Section 3.3. You can skip Examples 10, 12, 13. Subsection "The well-ordering property" can be useful in Math 302. Section 3.3 ends with "Why mathematical induction is valid". Notice that I gave a different argument in class and here.
• 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.
• Here are the axioms for the integers rewritten using quantifiers and logical operators learned in Chapter 1.
• Here is a proof of the principle of mathematical induction using the well-ordering axiom. I included all the details of the proof.

---

Thursday, April 26, 2012

---

• Here are the axioms for the integers. All propositions about integers are logical consequences of these axioms. This will be clearer if you take Math 302. In Section 3.3 we do proofs by mathematical induction. The principle of mathematical induction is a consequence of the well-ordering axiom. This will be proved in class.
• Finding bijections in Exercise 32 (a) and (b) (Section 3.2) will be easier with the following observations.
  • We know that for all real numbers $x$ we have $\lfloor x \rfloor \leq x \lt \lfloor x \rfloor +1$. Therefore $0 \leq x - \lfloor x \rfloor \lt 1$. Applying this to an integer $n$ we get \[ \forall \, n \in \mathbb Z \qquad 0 \leq \frac{n}{2} - \left\lfloor \frac{n}{2} \right\rfloor \lt 1. \] Multiplying by $2$ yields \[ \forall \, n \in \mathbb Z \qquad 0 \leq n - 2\,\left\lfloor \frac{n}{2} \right\rfloor \lt 2. \] Hence \[ \forall \, n \in \mathbb Z \qquad \left( n - 2\,\left\lfloor \frac{n}{2} \right\rfloor = 0 \right) \bigvee \left( n - 2\,\left\lfloor \frac{n}{2} \right\rfloor = 1 \right). \] In plain English, the function $n \mapsto n - 2\,\left\lfloor \frac{n}{2}\right\rfloor$ takes only the values $0$ and $1$. Since we clearly have \[ n = 2\,\left\lfloor \frac{n}{2}\right\rfloor + \left( n - 2\,\left\lfloor \frac{n}{2}\right\rfloor \right) \] the number $n - 2\,\left\lfloor \frac{n}{2}\right\rfloor$ is called the remainder when $n$ is divided by $2$. It is also called "$n$ modulo $2$". In Mathematica it is denoted by Mod[n,2].
    This is useful in Exercise 32 (a).
  • Similarly \[ \forall \, n \in \mathbb Z \qquad 0 \leq \frac{n}{3} - \left\lfloor \frac{n}{3} \right\rfloor \lt 1. \] Multiplying by $6$ yields \[ \forall \, n \in \mathbb Z \qquad 0 \leq n - 3\,\left\lfloor \frac{n}{3} \right\rfloor \lt 3. \] Hence \[ \forall \, n \in \mathbb Z \qquad \left( n - 3\,\left\lfloor \frac{n}{3} \right\rfloor = 0 \right) \bigvee \left( n - 3\,\left\lfloor \frac{n}{3} \right\rfloor = 1 \right) \bigvee \left( n - 3\,\left\lfloor \frac{n}{3} \right\rfloor = 2 \right). \] In plain English, the function $n \mapsto n - 3\,\left\lfloor \frac{n}{3}\right\rfloor$ takes only the values in the set $\{0,1,2\}$. Since we clearly have \[ n = 3\,\left\lfloor \frac{n}{3}\right\rfloor + \left( n - 3\,\left\lfloor \frac{n}{3}\right\rfloor \right) \] the number $n - 3\,\left\lfloor \frac{n}{3}\right\rfloor$ is called the remainder when $n$ is divided by $3$. It is also called "$n$ modulo $3$". In Mathematica it is denoted by Mod[n,3].
    This is also useful in Exercise 32 (a).
  • Similarly \[ \forall \, n \in \mathbb Z \qquad 0 \leq \frac{n}{6} - \left\lfloor \frac{n}{6} \right\rfloor \lt 1. \] Multiplying by $6$ yields \[ \forall \, n \in \mathbb Z \qquad 0 \leq n - 6\,\left\lfloor \frac{n}{6} \right\rfloor \lt 6. \] Hence \[ \forall \, n \in \mathbb Z \qquad \left( n - 6\,\left\lfloor \frac{n}{6} \right\rfloor = 0 \right) \bigvee \left( n - 6\,\left\lfloor \frac{n}{6} \right\rfloor = 1 \right) \bigvee \cdots \bigvee \left( n - 6\,\left\lfloor \frac{n}{6} \right\rfloor = 5 \right) . \] In plain English, the function $n \mapsto n - 6\,\left\lfloor \frac{n}{6}\right\rfloor$ takes only the values in the set $\{0,1,2,3,4,5\}$. Since we clearly have \[ n = 6\,\left\lfloor \frac{n}{6}\right\rfloor + \left( n - 6\,\left\lfloor \frac{n}{6}\right\rfloor \right) \] the number $n - 6\,\left\lfloor \frac{n}{6}\right\rfloor$ is called the remainder when $n$ is divided by $6$. It is also called "$n$ modulo $6$". In Mathematica it is denoted by Mod[n,6].
    This is useful in Exercise 32 (b).
  • In general, if $d$ is a positive integer \[ \forall \, n \in \mathbb Z \qquad 0 \leq \frac{n}{d} - \left\lfloor \frac{n}{d} \right\rfloor \lt 1. \] Multiplying by $d$ yields \[ \forall \, n \in \mathbb Z \qquad 0 \leq n - d\,\left\lfloor \frac{n}{d} \right\rfloor \lt d. \] Hence \[ \forall \, n \in \mathbb Z \qquad \left( n - d\,\left\lfloor \frac{n}{d} \right\rfloor = 0 \right) \bigvee \left( n - d\,\left\lfloor \frac{n}{d} \right\rfloor = 1 \right) \bigvee \cdots \bigvee \left( n - d\,\left\lfloor \frac{n}{d} \right\rfloor = d-1 \right) . \] In plain English, the function $n \mapsto n - d\,\left\lfloor \frac{n}{d}\right\rfloor$ takes only the values in the set $\{0,1,\ldots,d-1\}$. Since clearly we have \[ n = d\,\left\lfloor \frac{n}{d}\right\rfloor + \left( n - d\,\left\lfloor \frac{n}{d}\right\rfloor \right) \] the number $n - d\,\left\lfloor \frac{n}{d}\right\rfloor$ is called the remainder when $n$ is divided by $d$. It is also called "$n$ modulo $d$". In Mathematica it is denoted by Mod[n,d].
    
• Now a solution to Exercise 32 (a).
  1. Denote by $S$ the set of all integers which are not divisible by $3$. An integer $n$ is divisible by $3$ if and only if the remainder when $n$ is divided by $3$ is $0$. An integer $n$ is not divisible by $3$ if and only if remainder when $n$ is divided by $3$ is $1$ or $2$. Formally \[ S = \left\{ n \in \mathbb Z \ \bigl| \ \left( n - 3\,\left\lfloor \tfrac{n}{3} \right\rfloor = 1 \right) \bigvee \left( n - 3\,\left\lfloor \tfrac{n}{3} \right\rfloor = 2 \right) \bigr. \right\}. \] This is reminiscent of even and odd numbers. We will establish a bijection $f: \mathbb Z\to S$ using a piecewise definition based on even and odd numbers. We define $f(n) = 3\frac{n}{2} + 1$ if $n$ is even and $f(n) = 3\frac{n-1}{2} + 2$ if $n$ is odd. Using a proof by cases one can show that this is a bijection between $\mathbb Z$ and $S$. In fact, the inverse $f^{-1}: S \to \mathbb Z$ is given by $f^{-1}(k) = 2\frac{k-1}{3}$ if $k$ gives remainder $1$ when divided by $3$ and $f^{-1}(k) = 2\frac{k-2}{3} + 1$ if $k$ gives remainder $2$ when divided by $3$. The solution ends here, but please read on.
  2. Using what we learned in three square marked items above the bijection $f$ can be written as \[ \forall n \in {\mathbb Z} \qquad f(n) = 3 \left\lfloor \frac{n}{2} \right\rfloor + n - 2 \left\lfloor \frac{n}{2} \right\rfloor + 1. \] Since $n + \lfloor n/2 \rfloor = \lfloor n + n/2 \rfloor$ we simply have \[ \forall n \in {\mathbb Z} \qquad f(n) = \left\lfloor \frac{3n}{2} \right\rfloor + 1. \] Similarly, $f^{-1}$ can be written as \[ \forall k \in S \qquad f^{-1}(k) = 2 \left\lfloor \frac{k}{3} \right\rfloor + k - 3 \left\lfloor \frac{k}{3} \right\rfloor - 1. \] Since $- \lfloor k/3 \rfloor = \lceil -k/3 \rceil$ we simply have \[ \forall k \in S \qquad f^{-1}(k) = \left\lceil \frac{2k}{3} \right\rceil - 1. \]
  3. By definition of the inverse function we have $f^{-1}\bigl(f(n) \bigr) = n$ for all integers $n$. With the above definitions of $f$ and $f^{-1}$ we must have \begin{equation} \forall n\in \mathbb Z \qquad \left\lceil \frac{2}{3} \left( \left\lfloor \frac{3n}{2} \right\rfloor + 1 \right) \right\rceil - 1 = n \end{equation}
  4. A natural question here is: Prove the proposition displayed above in item 3 directly using the definitions of floor and ceiling.
  5. Here is a proof. Let $n$ be an arbitrary integer. By definition of floor \[ \frac{3n}{2} \lt \left\lfloor \frac{3n}{2} \right\rfloor + 1 \leq \frac{3n}{2} + 1. \] Multiplying by $2/3$ we get \[ n \lt \frac{2}{3} \left( \left\lfloor \frac{3n}{2} \right\rfloor + 1 \right) \leq n + \frac{2}{3}. \] Since $2/3 \lt 1$ we have \[ n \lt \frac{2}{3} \left( \left\lfloor \frac{3n}{2} \right\rfloor + 1 \right) \lt n + 1. \] Since $n$ is an integer, the last two inequalities imply \[ \left\lceil \frac{2}{3} \left( \left\lfloor \frac{3n}{2} \right\rfloor + 1 \right) \right\rceil = n+1. \] This proves the proposition in item 3.
• Now a solution to Exercise 32 (b).
  1. An integer $n$ is divisible by $5$ if and only if there exists an integer $m$ such that $n = 5m$. Since $5$ is not divisible by $7$, $n = 5m$ is divisible by $7$ if and only if $m$ is divisible by $7$. Therefore, $n = 5m$ is not divisible by $7$ if and only if $m$ is not divisible by $7$.
  2. In Exercise 32 (a) we established a bijection between $\mathbb Z$ and the set of integers not divisible by $3$. Here we need a bijection between $\mathbb Z$ and the set of all integers not divisible by $7$. Following the same reasoning as in the solution of Exercise 32 (a) we get that the function \begin{align} \forall n \in \mathbb Z \qquad g(n) & = 7 \left\lfloor \frac{n}{6} \right\rfloor + n - 6 \left\lfloor \frac{n}{6} \right\rfloor + 1 \\ & = n + \left\lfloor \frac{n}{6} \right\rfloor + 1 \\ & = \left\lfloor \frac{7n}{6} \right\rfloor + 1 \\ \end{align} is a bijection between $\mathbb Z$ and the set of all integers not divisible by $7$.
  3. In fact, following the same argument as in item 5 in the solution of Exercise 32 (a) one can show that the inverse of $g$ is \[ g^{-1}(k) = \left\lceil \frac{6k}{7} \right\rceil - 1, \] where $k$ is an arbitrary integer not divisible by $7$.
  4. Now it follows that the bijection between $\mathbb Z$ and the set of all integers that are divisible by $5$ and not divisible by $7$ is given by \[ \forall n \in \mathbb Z \qquad h(n) = 5\left( \left\lfloor \frac{7n}{6} \right\rfloor + 1 \right) \]

---

Monday, April 23, 2012

---

• Here is a more detailed way to approach Exercise 12 in Section 3.2. Consider the sequence defined by $r_n = \bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor$ for all $n \in {\mathbb Z}_+$. Then it is easy to calculate that \[ r_1 = 1, \ r_2 = 2, \ r_3 = 2, \ r_4 = 3, \ r_5 = 3, \ r_6 = 3, \ r_7 = 4, \ r_8 = 4, \ \ldots \] Now we might wonder: How many times this sequence takes the value $4$?
  To answer this question we have to solve the equation \[ \left\lfloor \sqrt{2n} + \frac{1}{2} \right\rfloor = 4. \] It is true that you have not encountered equations with the floor function before. However, it is not so difficult to solve this equation. By the essential properties of the floor function, the equality $\lfloor x \rfloor = 4$ is equivalent to $4 \leq x \lt 5$. Applying this to the equation that we are solving we get that the equation that we are solving is equivalent to: \[ 4 \leq \sqrt{2n} + \frac{1}{2} \lt 5. \] Since we want to solve for $n$, we subtract $1/2$ to get the equivalent expression \[ 4 - \frac{1}{2} \leq \sqrt{2n} \lt 5 - \frac{1}{2}. \] Since all the numbers in the last expression are positive, the last expression is equivalent to \[ 12 + \frac{1}{4} \leq 2n \lt 20 + \frac{1}{4}. \] Dividing by $2$ yields the equivalent expression \[ 6 + \frac{1}{8} \leq n \lt 10 + \frac{1}{8}. \] The next equivalence might be a little tricky: Since $n$ is a positive integer the last expression is equivalent to \[ 6 \lt n \leq 10. \] Clearly the last expression is equivalent to \[ (n = 7) \ \vee (n = 8) \ \vee \ (n = 9) \ \vee \ (n = 10). \] In conclusion: the equality \[ \left\lfloor \sqrt{2n} + \frac{1}{2} \right\rfloor = 4. \] is equivalent to \[ (n = 7) \ \vee (n = 8) \ \vee \ (n = 9) \ \vee \ (n = 10). \] Thus, the sequence $\{r_n\}$ takes the value $4$ exactly four times.
  You can repeat this reasoning by replacing $4$ with $5$. I hope that this will clarify the hints that I posted on Friday, April 20.

---

Friday, April 20, 2012

---

• Here is what I wrote during the first exam. Here is the histogram of the grades.
• 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). \] On Monday I will prove the formula: \[ \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.
• On Monday we will also talk about cardinality of sets and countability. Notice that we will skip parts about infinite series since that is covered in Math 226.
• 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. Here are some hints.
  • 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 < m+\frac{1}{2}$.

    This definitions rounds half-integers to the nearest larger integer. For example $\lfloor 1/2 \rceil = 1$.
  • With the notation introduced in the previous bullet, for an arbitrary $n \in {\mathbb Z}_+$ the following equivalences hold:

    by definition:	$\bigl\lfloor \sqrt{n} \bigr\rceil = q$	$\leftrightarrow$	$q - \frac{1}{2} \leq \sqrt{n} < q + \frac{1}{2}$
    by squaring positive numbers		$\leftrightarrow$	$q^2 - q + \frac{1}{4} \leq n < q^2 + q + \frac{1}{4}$
    since $n, q \in {\mathbb Z}_+$		$\leftrightarrow$	$q^2 - q < n \leq q^2 + q$
    adding $q$		$\leftrightarrow$	$q^2 < n + q \leq q^2 + 2q$
    since $n, q \in {\mathbb Z}_+$		$\leftrightarrow$	$q^2 < n + q < q^2 + 2q + 1$
    complete square		$\leftrightarrow$	$q^2 < n + q < (q + 1)^2$

    The equivalence $\bigl\lfloor \sqrt{n} \bigr\rceil = q \ $ if and only if $ \ q^2 < n + q < (q + 1)^2 $ can be used to solve Exercise 11.
  • 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} < n \leq \dfrac{q(q+1)}{2}$.

    Also notice that \[ \dfrac{q(q+1)}{2} = \dfrac{q(q-1)}{2} + q. \] Therefore, $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = q \ $ if and only if $\ n \ $ is one of $q$ integers \[ \dfrac{q(q-1)}{2} + 1, \ \dfrac{q(q-1)}{2} + 2, \ \ldots, \ \dfrac{q(q-1)}{2} + q. \]

---

Monday, April 16, 2012

---

• The exam is moved from Tuesday, April 17, 2012 to Thursday, April 19, 2012. The exam will cover Chapter 1.
• 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$.
• Read 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":
    1. 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"
    2. 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?
    3. 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.
• 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)
• Wikipedia's Function page:
  • Function

---

Friday, April 13, 2012

---

• Read Section 1.7. Do the exercises 2, 3, 11, 14, 18, 19, 20
• Wikipedia's Set page is relevant here:
  • Set

---

Thursday, April 12, 2012

---

• We started Section 1.6: Sets today. Do the exercises 1 - 21, 24, 25, 27, 28.
• Some relevant Wikipedia links:
  • Set
  • The number 1
  • The number 0
  • Integers
  • Natural numbers
  • Rational numbers
  • Real numbers

---

Monday, April 9, 2012

---

• Read Section 1.5. Pay a 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.
• 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.
  
  1. Assume that $x$ is rational.
  
  
  2. Then:
     
     There exist integers $a$ and $b$ such that $b \neq 0$, not both $a$ and $b$ are even, and $x =\dfrac{a}{b}$.
  
  
  3. Next we consider two cases. Case I: $a$ is odd,     Case II: $a$ is even.
  
  
  4. Consider Case I first. Assume that $a$ is odd.
  
  
  5. From Line 4 we deduce $a^2$ is odd.
  
  
  6. By Line 2 we have $b$ is an integer. This implies $2b^2$ is even.
  
  
  7. From Lines 5 and 6 we deduce $a^2 \neq 2b^2$.
  
  
  8. From Lines 2 and 7 we deduce   $x^2 =\dfrac{a^2}{b^2}\neq 2$ .
     
     (This completes the proof for Case I.)
  
  
  9. Now consider Case II. Assume that $a$ is even.
  
  
  10. By Line 9 we have: There exists an integer $c$ such that $a = 2c$.
  
  
  11. By Line 10 we have $2c^2$ is even.
  
  
  12. From Lines 2 and 9 we deduce $b$ is odd.
  
  
  13. From Line 12 we deduce $b^2$ is odd.
  
  
  14. From Lines 11 and 13 we deduce $b^2 \neq 2c^2$.
  
  
  15. From Lines 10 and 14 we deduce $2b^2 \neq 4c^2 = a^2$.
  
  
  16. From Lines 2 and 15 we deduce $x^2 =\dfrac{a^2}{b^2}\neq 2$.
      
      (This completes the proof for Case II.)
  
  

---

Tuesday, April 5, 2012

---

1. I did not mention this in class, but it is worth mentioning: If the propositional functions $P(x)$ and $Q(y)$ have the same universe of discourse, then the propositions \[ \bigl(\forall x \ P(x) \bigr) \wedge \bigl(\forall y \ Q(y) \bigr), \quad \forall x \ \bigl( P(x) \wedge Q(x) \bigr), \quad \forall x \ \forall y \ \bigl( P(x) \wedge Q(y) \bigr) \] are all equivalent. Each of these propositions says that all the values of both functions $P(x)$ and $Q(y)$ ($x, y$ in the universe of discourse) are true.
2. Similarly, if the propositional functions $P(x)$ and $Q(y)$ have the same universe of discourse, then the propositions \[ \bigl(\exists x \ P(x) \bigr) \vee \bigl(\exists y \ Q(y) \bigr), \quad \exists x \ \bigl( P(x) \vee Q(x) \bigr) \quad \exists x \ \exists y \ \bigl( P(x) \vee Q(y) \bigr) \] are all equivalent. Each of these propositions says that among the propositions $P(x)$ and $Q(y)$ ($x, y$ in the universe of discourse) there at least one which is true.
3. On Tuesday I posted several different ways of stating "there exists a unique $x$ such that $P(x)$ is true" ($\exists ! x \ P(x)$, for short) using quantifiers. I will prove below that the following two statements are equivalent: \[ \exists x \ \forall y \ \Bigl( P(x) \wedge \bigl( P(y) \to (y=x) \bigr) \Bigr), \qquad \exists x \ \forall y \ \bigl( P(y) \leftrightarrow (y=x) \bigr). \]
4. In this item we observe that for arbitrary $x$ in the universe of discourse \[ P(x) \ \leftrightarrow \ \forall y \ \bigl( (y=x) \to P(y) \bigr). \] It might be easier to see the equivalence if we restate the last biconditional using the negations \[ \neg P(x) \ \leftrightarrow \ \exists y \ \bigl( (y=x) \wedge \neg P(y) \bigr). \] For completeness I mention that here the universe of discourse for $y$ is the same as the universe of discourse for $x$.
5. Now I will prove the equivalence stated in 3. The proof consists of four equivalences which together prove the equivalence stated in 3. Each equivalence should be clear based on today's items 1 and 4.
   
   First, today's item 1 implies that the proposition \[ \exists x \ \forall y \ \Bigl( P(x) \wedge \bigl( P(y) \to (y=x) \bigr) \Bigr) \] is equivalent to \[ \exists x \ \Bigl( P(x) \wedge \Bigl( \forall y \ \bigl( P(y) \to (y=x) \bigr) \Bigr) \Bigr). \] Second, today's item 4 implies that the last proposition is equivalent to \[ \exists x \ \Bigl( \Bigl( \forall y \ \bigl( (y=x) \to P(y) \bigr) \Bigr) \wedge \Bigl( \forall y \ \bigl( P(y) \to (y=x) \bigr) \Bigr) \Bigr). \] Third, today's item 1 implies that the last proposition is equivalent to \[ \exists x \ \forall y \ \Bigl( \bigl( (y=x) \to P(y) \bigr) \wedge \bigl( P(y) \to (y=x) \bigr) \Bigr). \] Fourth, the definition of biconditional implies that the last proposition is equivalent to \[ \exists x \ \forall y \ \bigl( P(y) \leftrightarrow (y=x) \bigr). \]
6. In the book there are several exercises which use the proposition "there exist exactly two values of the variable $x$ such that $P(x)$ is true". One way to express this proposition using quantifiers is the following proposition \[ \exists x \ \exists y \ \forall z \ \Bigl( (x\neq y) \wedge \Bigl( P(z) \leftrightarrow \bigl((z=x) \vee (z=y) \bigr)\Bigr) \Bigr). \]

---

Tuesday, April 3, 2012

---

• We did Section 1.4 today. Do the exercises 1, 2, 9, 10, 16, 19, 20, 24, 25, 26, 27, 28, 29, 30, some of 31-36, 37, 38, 41, 42, 43, 44, 45.
• 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) \to \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) \to \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) \to (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) \]

---

Friday, March 30, 2012

---

• Read Section 1.3 over the weekend. The exercises for this section are 1, 2, 9, 11 - 19, 28, 30, 31, 33, 34, 41, 46, 55, 56, 57. Try some of the exercises, then do all on Monday.

---

Thursday, March 29, 2012

---

• Today we did Section 1.2. Do the exercises 1-13 and most of 14-29. Also do 49 and 51.
• 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 20120329.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 20120329.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.

---

Tuesday, March 27, 2012

---

• 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.

---