## Proof by contradiction --- ## Attempt via direct proof #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Attempted proof Because $x^2$ is even, it follows that $x=\sqrt{x^2}$ is … <!-- .slide: data-auto-animate class="smallertext" --> --- ## Attempt via direct proof #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Attempted proof Because $x^2$ is even, it follows that $x=\sqrt{x^2}$ is … #### Try some examples $16$ is even and its square root is $4$, which is also even. <!-- .slide: data-auto-animate class="smallertext" --> --- ## Attempt via direct proof #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Attempted proof Because $x^2$ is even, it follows that $x=\sqrt{x^2}$ is … #### Try some examples $16$ is even and its square root is $4$, which is also even. But $18$ is even, and its square root is $3\sqrt2$, which is not even, indeed it is not an integer! <!-- .slide: data-auto-animate class="smallertext" --> --- ## Attempt via direct proof #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Attempted proof Because $x^2$ is even, it follows that $x=\sqrt{x^2}$ is … #### Try some examples $16$ is even and its square root is $4$, which is also even. But $18$ is even, and its square root is $3\sqrt2$, which is not even, indeed it is not an integer! #### Analysis Knowing an integer is even is not enough to know much useful about its square root. So the proof can't proceed. <!-- .slide: data-auto-animate class="smallertext" --> --- ## Attempt via direct proof #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Attempted proof Because $x^2$ is even, it follows that $x=\sqrt{x^2}$ is … #### Try some examples $16$ is even and its square root is $4$, which is also even. But $18$ is even, and its square root is $3\sqrt2$, which is not even, indeed it is not an integer! #### Analysis Knowing an integer is even is not enough to know much useful about its square root. So the proof can't proceed. #### Lesson Sometimes we need to try a different method of proof. <!-- .slide: data-auto-animate class="smallertext" --> --- ## Proof by contradiction #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Proof Let $x\in\mathbb Z$ be such that $x^2$ is even. <!-- .slide: class="smallertext" data-transition="slide-in none-out" --> --- ## Proof by contradiction #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Proof Let $x\in\mathbb Z$ be such that $x^2$ is even. <span class="fragment daz-switch preload" data-fragment-index="0">Suppose additionally that $x$ is not even</span>. <!-- .slide: class="smallertext" data-transition="none" --> --- ## Proof by contradiction #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Proof Let $x\in\mathbb Z$ be such that $x^2$ is even. <span class="fragment daz-switch preload" data-fragment-index="0">Suppose additionally that $x$ is not even</span>. Then, for some $k\in\mathbb Z$, $x=2k+1$. <!-- .slide: class="smallertext" data-transition="none" --> --- ## Proof by contradiction #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Proof Let $x\in\mathbb Z$ be such that $x^2$ is even. <span class="fragment daz-switch preload" data-fragment-index="0">Suppose additionally that $x$ is not even</span>. Then, for some $k\in\mathbb Z$, $x=2k+1$. So $x^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$, which is not even. <!-- .slide: class="smallertext" data-transition="none" --> --- ## Proof by contradiction #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Proof Let $x\in\mathbb Z$ be such that $x^2$ is even. <span class="fragment daz-switch preload" data-fragment-index="0">Suppose additionally that $x$ is not even</span>. Then, for some $k\in\mathbb Z$, $x=2k+1$. So $x^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$, which is not even. This is impossible, as we know $x^2$ is even. <!-- .slide: class="smallertext" data-transition="none" --> --- ## Proof by contradiction #### Theorem If $x\in\mathbb Z$ and $x^2$ is even, then $x$ is even. #### Proof Let $x\in\mathbb Z$ be such that $x^2$ is even. <span class="fragment daz-switch preload" data-fragment-index="0">Suppose additionally that $x$ is not even</span><span class="fragment daz-switch color1" data-fragment-index="1">Suppose additionally that $x$ is not even</span>. Then, for some $k\in\mathbb Z$, $x=2k+1$. So $x^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$, which is not even. This is impossible, as we know $x^2$ is even. Therefore our <span class="fragment daz-switch preload" data-fragment-index="0">assumption</span><span class="fragment daz-switch color1" data-fragment-index="1">assumption</span> must have been incorrect; $x$ is actually even.   □ <!-- .slide: class="smallertext" data-transition="none" --> --- ## Proof by contradiction #### Theorem If $x\in\mathbb Z$ and $x^2$ is divisible by $3$, then $x$ is divisible by $3$. <!-- .slide: class="smallertext" data-auto-animate data-auto-animate-restart --> --- ## Proof by contradiction #### Theorem If $x\in\mathbb Z$ and $x^2$ is divisible by $3$, then $x$ is divisible by $3$. #### Proof Let $x\in\mathbb Z$ be such that $x^2$ is divisible by $3$. <span class="fragment daz-switch preload" data-fragment-index="0">Suppose additionally that $x$ is not divisible by $3$</span><span class="fragment daz-switch color1" data-fragment-index="1">Suppose additionally that $x$ is not divisible by $3$</span>. Then, for some $k\in\mathbb Z$, $x=3k+1$ or $x=3k+2$. So $x^2=(3k+1)^2=9k^2+6k+1=3(3k^2+2k)+1$, or $x^2=(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1$, neither of which is divisible by $3$. This is impossible, as we know $x^2$ is divisible by $3$. Therefore our <span class="fragment daz-switch preload" data-fragment-index="0">assumption</span><span class="fragment daz-switch color1" data-fragment-index="1">assumption</span> must have been incorrect; $x$ is actually divisible by $3$.   □ <!-- .slide: class="smallertext" data-auto-animate --> --- ## Longer proof by contradiction #### Theorem There is a positive irrational number whose square is $2$. #### Proof We already proved $\exists$ positive $z\in\mathbb R$ such that $z^2=2$. <span class="fragment daz-switch preload" data-fragment-index="0">Suppose $z\in\mathbb Q$</span><span class="fragment daz-switch color1" data-fragment-index="1">Suppose $z\in\mathbb Q$</span>. Then $\exists$ $a,b\in\mathbb Z\setminus\\{0\\} \mid z=a/b$ and $a,b$ not both even. Then $a^2=2b^2$, so $a^2$ is even. Therefore $a$ is even. So $\exists c\in\mathbb Z$ such that $a=2c$. But then $4c^2=a^2=2b^2$, so $b^2$ is even, and so is $b$. <span class="fragment daz-switch preload" data-fragment-index="0">But this contradicts $a,b$ being not both even</span><span class="fragment daz-switch color1" data-fragment-index="1">But this contradicts $a,b$ being not both even</span>. So it must be that $z\notin\mathbb Q$. Hence $z$ is irrational.   □ <!-- .slide: class="smallertext" data-auto-animate data-auto-animate-restart --> --- ## Structure of a proof by contradiction #### Theorem 1 $A \implies B$. #### Proof structure 1 We know $A$ is true. Suppose not $B$. Then… <em>argument using both $A$ and not $B$</em> …therefore, <em>false statement</em>. But this is false, so the supposition must have been incorrect.   □ #### Proof structure 2 Suppose not $B$. Then… <em>argument using not $B$</em> …therefore, not $A$. But we know $A$ is true, so the supposition must have been incorrect.   □ <!-- .slide: class="smallertext" data-auto-animate data-auto-animate-restart --> --- ## Structure of a proof by contradiction #### Theorem 1 $A \implies B$. #### Proof structure 2 Suppose not $B$. Then… <em>argument using not $B$</em> …therefore, not $A$. But we know $A$ is true, so the supposition must have been incorrect.   □ In proof structure 2, we have actually proved the contrapositive of theorem 1: #### Theorem 2 (equivalent to theorem 1) not $B \implies $ not $A$. <!-- .slide: class="smallertext" data-auto-animate -->