{ "cells": [ { "cell_type": "markdown", "metadata": { "button": false, "deletable": true, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "# MTH 225: Methods of Proof\n", "\n", "## Part 2: Direct proofs of conditional statements\n", "\n", "### Overview \n", "\n", "In the first segment on methods of proof, we learned about how mathematical knowledge is discovered and added to the knowledge base of the discipline. For _abstract_ discoveries -- truths that apply to entire sets of objects aat a time without depending on specific instances -- the means of solidifying knowledge consist in __proof__. This is a clear, logical, persuasive argument that an abstract statement is always true. We talked about what a proof _isn't_ -- for example a list of examples does not constitute a proof, nor does an abstract argument that isn't sufficiently clear or convincing. In this lesson we begin to learn what a proof _is_, and how to write one. We'll begin with the simplest possible kind of mathematical proposition to prove, the _conditional statement_ which has the form __If $A$, then $B$__. The method we will learn is called _direct proof_ and it follows directly (see what I did there?) from the truth table from a conditional statement. \n", "\n", "### Learning Objectives\n", "\n", "__Basic:__\n", "\n", "+ Identify the _hypothesis_ and _conclusion_ of a conditional statement. \n", "+ Explain the overall strategy of a direct proof of a conditional statement. \n", "+ State the assumption that would be made in a direct proof of a conditional statement. \n", "+ Explain what would need to be shown in a direct proof of a conditional statement, once the initial assumption has been made. \n", "+ Write out the first step of a direct proof past the initial assumption using a rigorous mathematical definition of the objects involved. \n", "\n", "__Advanced:__\n", "\n", "+ Critique a complete direct proof, finding all errors and points at which it could be improved. \n", "+ Construct a complete and correct direct proof of a conditional statement. \n", " \n", "\n", "### Background\n", "\n", "We've seen what a proof of an abstract mathematical proposition _isn't_. It is not a list of examples; nor is it an unclear and poorly written argument. But what _is_ a proof? Well, a proof is a convincing and persuasive argument that explains exactly why a general, asbtracted conjecture is always true. But there is more than way that such an argument can look. \n", "\n", "Sometimes a proof is an argument based on using pre-existing knowledge used in a clever way: \n", "\n", "__Theorem:__ For any positive integer $n$, we have\n", "$$\\sum_{i=0}^n \\left( {\\begin{array}{*{20}c} n \\\\ i \\\\ \\end{array}} \\right) = 2^n$$\n", "\n", "__Proof:__ The Binomial Theorem states that for any $x$ and $y$, \n", "$$(x+y)^n = \\sum_{i=0}^n \\left( {\\begin{array}{*{20}c} n \\\\ i \\\\ \\end{array}} \\right) x^{n-i}y^i$$\n", "To get the result in the theorem statement, just plug in $x=1$ and $y=1$. On the left side of the Binomial Theorem we get $(1+1)^n = 2^n$. On the right side, we get \n", "$$\\sum_{i=0}^n \\left( {\\begin{array}{*{20}c} n \\\\ i \\\\ \\end{array}} \\right) 1^{n-i}1^i = \\sum_{i=0}^n \\left( {\\begin{array}{*{20}c} n \\\\ i \\\\ \\end{array}} \\right)$$\n", "This is what we wanted to show, so we are done. $\\square$\n", "\n", "_Aside:_ Once a conjecture has been proven, we call it a __theorem__ (sometimes \"proposition\"). And in a proof of a theorem we often put some kind of symbol at the end to tell the reader we are done; here, I used a square $\\square$. \n", "\n", "So that's a clever use of the Binomial Theorem to prove an interesting result. But it may leave you with a very important question: _How do we know that the Binomial Theorem is true?_ That's a good question because we want to ask _Why is this true?_ for _any_ mathematical result we meet. Technically we should treat the proof above as a _tentative_ proof, contingent on our finding a proof for the Binomial Theorem. \n", "\n", "At other times a proof uses _definitions of terms_ and puts them together in logical ways to derive something new. For example, here's an important pair of definitions: \n", "\n", "__Definition:__ An integer $n$ is said to be _even_ if there is an integer $k$ such that $n = 2k$. An integer $n$ is said to be _odd_ if there is an integer $k$ such that $n = 2k+1$. \n", "\n", "For example, $48$ is even because $48 = 2 \\cdot 24$; and $77$ is odd because $77 = 76 + 1 = 2\\cdot 38 + 1$. \n", "\n", "Using these definitions of even and odd numbers, we can prove a result we have taken for granted for a long while: \n", "\n", "__Theorem:__ An even number times an odd number is an even number. \n", "\n", "__Proof:__ Suppose $a$ is even and $b$ is odd. Then there exist integers $x$ and $y$ such that $a = 2x$ and $b = 2y+1$. Multiplying these together gives us: \n", "$$ab = (2x)(2y+1) = 2(2xy + x)$$\n", "Since $x$ and $y$ are integers, $2xy + x$ is also an integer. Therefore we have expressed $ab$ as $2c$ where $c$ is an integer. Hence $ab$ is even. $\\square$\n", "\n", "Note the structure of this second proof. We started off by making an _assumption_: That we have two integers, and they are called $a$ and $b$ with $a$ even and $b$ odd. In other words we begin by assuming we have the information needed to argue the result. Then, we used the definition of even and odd to _rewrite the objects involved in a different form_ -- for example, $a = 2x$ for some integer $x$. Then we _progressed logically_ by making mathematical steps and using definitions again to arrive at our result, and we _clearly state when we have finished_. \n", "\n", "Questions for you to consider about this proof: \n", "\n", "+ Are you convinced? \n", "+ Suppose the second line had read: \"Then there exists an integer $x$ such that $a = 2x$ and $b = 2x+1$.\" Would this have been a problem? \n", "+ Can you justify the two equals signs in the middle, centered line? Why are both of those equalities true?\n", "+ Why did we have to say something about $2xy+x$ being an integer? Was that necessary? \n", "\n", "Now consider this proposition: \n", "\n", ">For every $n \\in \\mathbb{Z}$, if $n$ is even then $n^2$ is even. \n", "\n", "This is a special kind of proposition because it is a __conditional statement__ or \"if-then\" statement. These are very common in mathematics and in CS, and we can use some of our logic knowledge to help in constructing a proof. \n", "\n", "First, recall that the __hypothesis__ of a conditional statement is the \"if\" part; and the \"then\" part is called the __conclusion__. Here, \"$n$ is even\" is the hypothesis and \"$n^2$ is even\" is the conclusion. \n", "\n", "Second, recall the truth table of a conditional statement \"If $p$, then $q$\": \n", "\n", "| $p$ | $q$ | $p \\rightarrow q$ | \n", "|:--: |:--:| :-----------------:|\n", "| 1 | 1 | 1 | \n", "| 1 | 0 | 0 | \n", "| 0 | 1 | 1 | \n", "| 0 | 0 | 1 | \n", "\n", "Whenever the hypothesis of a conditional statement is false, the conditional statement is true. Therefore, _if we are trying to prove that a conditional statement is true, we can ignore any situation in which the hypothesis is false_ because the conditional statement is true automatically in that case. That is: __We can assume that the hypothesis is true__ when proving a conditional statement. \n", "\n", "A proof of a conditional statement can therefore proceed as follows: \n", "\n", "1. Assume that the hypothesis is true. \n", "2. Use definitions, previously proven results, etc. to rewrite the objects in the hypothesis. \n", "3. Continue to use definitions and prior results to rewrite expressions in different forms and use logic to arrive at the conclusion. \n", "\n", "An argument of this form is called a __direct proof__ of a conditional statement. Here is an example, broken up line by line with justification provided for each line so you can see the flow of the argument. \n", "\n", "__Theorem:__ For every $n \\in \\mathbb{Z}$, if $n$ is even then $n^2$ is even. \n", "\n", "__Proof:__\n", "\n", "1. Assume that $n$ is an even integer. [_Justification: Assuming the hypothesis_] \n", "2. Then there is an integer $k$ such that $n = 2k$. [_Justification: Definition of \"even\"_]\n", "3. Squaring $n$ gives $n^2 = (2k)(2k)$. [_Justification: Squaring both sides of $n = 2k$. We are doing this step because we want to conclude something about $n^2$._]\n", "4. Therefore $n^2 = 4k^2$. [_Justification: Basic algebra._]\n", "5. This can be written as $2(2k^2)$. [_Justification: Factoring out a 2. We do this because we are trying to show $n^2$ is even._]\n", "6. Since $k$ is an integer, $2k^2$ is also an integer. [_Justification: Left up to the reader. What justifies this?_]\n", "7. Therefore we have written $n^2$ as an integer multiple of $2$, so $n^2$ is even. [_Justification: Definition of \"even\"_]\n", "\n", "Notice, again, that in a well written proof: \n", "\n", "+ The assumptions are clearly stated.\n", "+ There are no unwarranted assumptions being used in the proof. For example if we had assumed that $n$ was positive in the proof above, that would be unwarranted -- what allows me to make such an assumption? Nothing. \n", "+ Each step in the proof is clearly and correctly justified. \n", "\n", "\n", "### Video to watch\n", "\n", "Before proceeding on to the exercises, watch the following videos: \n", "\n", "+ [Integer divisibility](https://youtu.be/dIfpZzX7bKo) (8:52) -- This video gives a formal definition of what it means for one integer to \"divide\" another. Needed for the exercises and HWA. \n", "+ [Direct proof involving divisibility](https://youtu.be/0vIj582-rbQ) (8:49) -- Gives another example of a direct proof. The argument this time is put into what we call a \"know-show table\" which is similar to the numbered proof above. It's a good framework for doing scratchwork with proofs. " ] }, { "cell_type": "markdown", "metadata": { "button": false, "collapsed": true, "deletable": true, "new_sheet": false, "run_control": { "read_only": false } }, "source": [ "### Exercises\n", "\n", "For the following exercises, consider the conditional statement: \n", "\n", ">For each integer $a$, if $4$ divides $a-1$, then $4$ divides $a^2 - 1$. \n", "\n", "1. State the hypothesis of this statement. \n", "2. State the conclusion of this statement. \n", "3. If we were to attempt a direct proof of this statement, what would we assume at the outset of the proof? (In other words, what would be the very first sentence of a proof?) \n", "4. If we were to attempt a direct proof of this statement, after we made the initial assumption (in question 3 above), what would we then need to prove? \n", "5. Suppose we were to continue with a direct proof of this statement. We would need to give a precise interpretation of what \"$4$ divides $a-1$\" means. Rewrite this statement by completeing the following existentially quantified statement: \"There exists an integer $k$ such that...\" \n", "\n", "### Submission\n", "\n", "Put in your answers to the exercises here: [http://bit.ly/1NkzZmW](http://bit.ly/1NkzZmW)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.5.0" } }, "nbformat": 4, "nbformat_minor": 0 }