Summer 2013
MATH 309: Introduction to Proof in Discrete Mathematics
Branko Ćurgus

Thursday, August 15, 2013

---

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

---

Wednesday, August 14, 2013

---

• Read Section 4.4.
• Do the exercises: 1-13, 21, 22, 25, 28, 29, 30.
• Some solutions from Section 4.4 as a Mathematica file are here and a pdf print-out of the same file is here.

---

Monday, August 12, 2013

---

• Read Section 4.3.
• In Section 4.3 do as many exercises as you can from 1-43.
• Some hints: 23: There are nine positions to place women after man are placed; this can be done in C(9,5) ways. 29: This problem is tricky. Be aware of counting the same 4-permutations more than once. 35: Place 1s first. Then there are 10 spots to place 0s between 1s. 37: Consider the complement of the set. 40: First answer how many ways are there to seat six people on a straight bench. Then count how many distinct seatings on a bench lead to the identical seating around a circular table. 43: Have in mind that all six runners can tie for gold and so on.
• Some solutions from Section 4.3 as a Mathematica file are here and a pdf print-out of the same file is here.

---

Wednesday, August 7, 2013

---

• Today in class I created this Mathematica notebook. In this notebook I created a select function that can be used to create some of the sets that appear in exercises in Section 4.1.
• In July 23 post I explained how to use Mathematica notebooks. Open Mathematica first, then open the file that you downloaded from Mathematica 5.2. You can execute the entire notebook by the following manu sequence (in Mathematica): Kernel -> Evaluation -> Evaluate Notebook.
• Tomorrow we will talk about Section 4.2. Assigned exercises are: 3, 4, 5, 8, 9, 10, 13, 14, 15, 16, 18, 19, 20, 36, 40.

---

Tuesday, August 6, 2013

---

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

---

Wednesday, July 31, 2013

---

• Read the first part of Section 3.4, up to Theorem 1 on page 260.
• 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)

---

Monday, July 29, 2013

---

• Read Section 3.3. You can skip Examples 10, 12, 13. Subsection "The well-ordering property" is an alternative approach to the proof of Mathematical induction.
• 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.

---

Thursday, July 25, 2013

---

• We finished Section 3.2. I gave a rigorous proof that ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ is countable. This rigorous proof is posted here. I also proved that the set of real numbers is not countable.
• Today in class I demonstrated the bijection between ${\mathbb Z}^+$ and ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ using this Mathematica notebook. In this notebook I give an explicit formula for a bijection between ${\mathbb Z}^+$ and ${\mathbb Z}^+\!\!\times\!{\mathbb Z}^+$ and its inverse. These formulas are illustrated with appropriate graphs.
• In July 23 post I explained how to use Mathematica notebooks. Open Mathematica first, then open the file that you downloaded from Mathematica 5.2. You can execute the entire notebook by the following manu sequence (in Mathematica): Kernel -> Evaluation -> Evaluate Notebook.

---

Tuesday, July 23, 2013

---

• We started Section 3.2 on Thursday. We covered definition of a sequence, and several examples of sequences; in particular geometric progression, arithmetic progression, and examples listed in Table 1. I proved the formulas \[ \forall \, n \in \mathbb N \qquad \displaystyle \sum_{k=1}^n k \ = \ \dfrac{n(n+1)}{2} \] and \[ \forall \, n \in {\mathbb Z}^+ \ \forall \, a \in {\mathbb R} \ \forall \, d \in {\mathbb R} \quad \sum_{k=0}^n \bigl(a + k\, d\bigr) =(n+1) a + \dfrac{n(n+1)}{2}\, d = (n+1)\left( a + \dfrac{n}{2}\, d \right), \] and \[ \forall \, n \in {\mathbb Z}^+ \ \ \forall \, r \in {\mathbb R}\setminus\{0,1\} \qquad \sum_{k=0}^n a \, r^k = a \dfrac{r^{n+1} - 1}{r - 1} = a \dfrac{1-r^{n+1}}{1-r}. \] Here I use the notation $A\setminus B$ for the set difference of two sets. This notation is more common than $A-B$ used in the book.
• We will skip parts about infinite series since that is covered in Math 226.
• Read Section 3.2. Do the exercises 2, 4, 5, 6, 9, 11, 12, some of 13-18, 19, 20, 21, 23, 31, 32. Notice that Exercises 11 and 12 are more challenging. I did 12 in class.
• To solve Exercise 12 we have to answer the following question: For a given $m \in {\mathbb Z}^+$ how many positive integers $n$ satisfy the equality
  

  $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $?

  This question will be answered by the following equivalences.
  • 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 > 0$,
    

    $m^2 - m \lt 2n \leq m^2 + m \ $ if and only if $ \ \dfrac{(m-1)m}{2} \lt n \leq \dfrac{m(m + 1)}{2}$

  • Thus, for $m, n \in {\mathbb Z}^+$ we have proved the equivalence:
    

    $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $ if and only if $ \ \dfrac{m(m-1)}{2} \lt n \leq \dfrac{m(m+1)}{2}$.

  • Next, notice the identity \[ \dfrac{m(m+1)}{2} = \dfrac{m(m-1)}{2} + m. \] Therefore, $ \ \dfrac{m(m-1)}{2} \lt n \leq \dfrac{m(m+1)}{2} \ $ if and only if $\ n \ $ is one of $m$ integers \[ \dfrac{m(m-1)}{2} + 1, \ \dfrac{m(m-1)}{2} + 2, \ \ldots, \ \dfrac{m(m-1)}{2} + m. \]
  • Finally we conclude that $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor = m \ $ if and only if $\ n \ $ is one of $m$ integers \[ \dfrac{m(m-1)}{2} + 1, \ \dfrac{m(m-1)}{2} + 2, \ \ldots, \ \dfrac{m(m-1)}{2} + m. \] The conclusion is: The sequence $\bigl\lfloor \sqrt{2n} + \frac{1}{2} \bigr\rfloor$ takes the value $m$ exactly at $m$ distinct values of $n$.
• You can find more about this integer sequence here. This is just one of many integer sequences featured at The On-Line Encyclopedia of Integer Sequences.
• Here is the Mathematica 5.2 file that I used. It is called 20130723.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 20130723.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 that cell and press Shift+Enter. There is more about how to use Mathematica 5.2 at my Mathematica page.
  • If you have problems running files that I post please let me know. If you spend some time learning how to use these files you will enhance the understanding of math that you are studying.

---

Tuesday, July 16, 2013

---

• The axioms for the integers are posted here.
• Some basic properties of integers deduced from the axioms can be found here.
• This is the LaTeX file that I used to produce BasicPropositionsZ.pdf (the pdf file in the item above). Right-click on the underlined word "This"; 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, BasicPropositionsZ.TeX.
• I encourage you to learn LaTeX. LaTeX is a document preparation system which is widely used by mathematicians. In fact it is the standard for professional mathematical publications. It is completely free.
• There is an abundance of information about LaTeX on the web. Here are a few sites to start with.
  • Introduction from LaTeX project site.
  • LaTeX for Complete Novices by Nicola L. C. Talbot.
  • LaTeX help from NASA.
  • A LaTeX introduction from Tobias Oetiker site (a pdf file).
• If you have a problem with any aspect of LaTeX ask me or any LaTeX enthusiast. LaTeX community is very willing to help you to discover this amazing tool. Also, keep on googleing and you will find a site that will answer your question.

---

Tuesday, July 9, 2013

---

• Read Section 1.8. Do the exercises 1, 2, 4, 8, 9, 10, 11, 12, 13, 14, 17, 18, 23, 25, 26, 27, 28, 29, 31, 44, 45, 48, 49, 56, 58, 60(f), 65, 66 ((b) and (d) in 66 are wrong)
• Here I state a formal definition of function. This definition identifies a function and its graph. The justification is that if you know the graph of a function, then you know the function, and conversely, if you know a function you know its graph. I like this definition since it takes advantage of the language that we learned in the logic part of the class. Simply stated the definition below says that a function from a set $A$ to a set $B$ is a subset $F$ of the Cartesian product $A\!\times\!B$ such that for each $x \in A$ there exists unique $y \in B$ such that $(x,y) \in F$.
  
  Definition. Let $A$ and $B$ be nonempty sets. A function from $A$ into $B$ is a subset $F$ of the Cartesian product $A\!\times\!B$ such that
  • $\forall \, x \in A \ \ \exists \, y \in B \quad (x,y) \in F$,
  • $\forall \, x \in A \ \forall \, y \in B \ \forall \, z \in B \quad (x,y) \in F \wedge (x,z) \in F \ \Rightarrow \ y=z$.
• While reading Section 1.8. Pay attention to the following concepts.
  • function, domain, codomain, range,
  • one-to-one function (I prefer the synonym: injection)
  • onto function (I prefer the synonym: surjection)
  • bijection
    A comment on terminology:
    Our textbook and many other books use the synonym phrase "one-to-one correspondence".
    Here are three reasons why "bijection" is preferable to "one-to-one correspondence":
    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.
  • composition of functions
  • inverse function
  • Table 1 with the basic properties of the floor and ceiling functions.
• Wikipedia's Function page:
  • Function

---

Monday, July 8, 2013

---

• 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:
  • Set

---

Wednesday, July 3, 2013

---

• 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
• Here is the link to a page that gives 23 proofs that $\sqrt{2}$ is irrational. However, the proof that I give below is not included.
• 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.
  
  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. Since no integer is both even and odd, 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. Since no integer is both even and odd, 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.)
  
  

---

Monday, July 1, 2013

---

• 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)
• We started 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(a) (state and prove the contrapositive), 23, 24, 25 (use a variation of the contrapositive), 26, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 39, 40, 43, 44, 46, 49, 51, 55, 64, 65, 70.

---

Thursday, June 27, 2013

---

• Today we did 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 is a practical example of usage of predicates to decide if a year is a leap year.
  • 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 clear that this definition uses only three predicates involving a year as a variable. These predicates are: $P(y)$ is "$y$ is divisible by $4$.   $Q(y)$ is "$y$ is divisible by $100$.   $R(y)$ is "$y$ is divisible by $400$. It is an interesting exercise use these predicates to write the definition of the leap year in a 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.

  • This formal definition can be implemented on a computer, provided that a computer knows logical operations and can decide whether a number is an integer or not.

---

Wednesday, June 26, 2013

---

• 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.
• We also started 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.

---

Tuesday, June 25, 2013

---

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

---