CS70 Guide
  • This site is now deprecated
  • LaTeX Reference
  • Discrete Math
    • Overview
    • Propositional Logic
    • Proofs
    • Stable Matching
    • Graphs
    • Modular Arithmetic
    • RSA Cryptography
    • Polynomials
    • Countability
    • Computability
  • Probability
    • Overview
    • Counting
    • Discrete Probability
    • Hashing and the Union Bound
    • Expectation and Variance
    • Concentration Inequalities
    • Continuous Probability
    • Markov Chains
    • The Beta Family
    • The Gamma Family
    • Conditional Expectation and Variance
Powered by GitBook
On this page
  • Introduction
  • Direct Proofs
  • Proof by Contraposition
  • Proof by Contradiction
  • Proof by Cases
  • Proof by Induction
  • Stronger Induction
  • Proof of the Induction Principle
  • More Resources

Was this helpful?

  1. Discrete Math

Proofs

PreviousPropositional LogicNextStable Matching

Last updated 2 years ago

Was this helpful?

Introduction

A proof is a set of logical deductions that can be used to show how something is true. This is powerful because proofs can often be very general, allowing a truth to be used in a whole bunch of cases that don't individually need to be re-proven.

There are a number of common proof techniques (although these certainly aren't exhaustive!) outlined below.

Direct Proofs

In direct proofs, we can use the definitions directly to show that something is true. No trickery here, just straightforward navigation from point A to point B.

Direct Proof Form:

  • Goal: P  ⟺  QP \iff QP⟺Q****

  • Assume P.

  • Do a bunch of steps using the definitions and assumptions created by the values and operators used.

  • Therefore Q.

Example:

Let D3D_3D3​be the set of 3 digit natural numbers. Show that for all n∈D3n \in D_3n∈D3​, if the alternating sum of digits of nnnis divisible by 11, then 11∣n11 \mid n11∣n. (Lecture 2)

  • First, let's make sure this makes sense. Let's try some examples:

    • if n=605n=605n=605, then nnnis divisible by 11. Its alternate sum is 6−0+5=116 - 0 + 5 = 116−0+5=11. 111111is indeed divisible by 11, so this looks like it could be true!

  • Next, let's write this in propositional logic:

    • \forall n \in D_3, (11 \mid \mbox{alt sum of digits of n}) \implies 11 \mid n

  • Now, let's try to prove it starting with assuming that all nnn are 3 digit natural numbers.

    • Let a,b,a, b,a,b,and ccc represent the three digits of nnnsuch that n=100a+10b+cn = 100a + 10b + cn=100a+10b+c.

    • If the alternating sum of digits is divisible by 11, then 11∣a−b+c11 \mid a - b + c11∣a−b+c.

    • Using the definition of division, a−b+c=11ka - b + c = 11ka−b+c=11kfor some natural number k. We're trying to prove that n=100a+10b+c=11mn = 100a + 10b + c = 11mn=100a+10b+c=11mfor another integer mmmas well!

    • Solve for cccusing the alternating sum to get c=11k+b−ac = 11k + b - ac=11k+b−a. Substitute this value into the second equation to get 100a+10b+11k+b−a=11m100a + 10b + 11k + b - a = 11m100a+10b+11k+b−a=11m. Simplifying, this equation is equivalent to 99a+11b+11k=11m99a + 11b + 11k = 11m99a+11b+11k=11m.

    • We know that this must be true because each individual term is multiplied by a number divisible by 11. Therefore, the entire number must also be divisible by 11.

Proof by Contraposition

Contraposition Form:

  • Do a bunch of steps using another type of proof.

Example:

For every n \in \mathbb{N}, n^2 \mbox{even} \implies n \mbox {even}

  • If we try proving using a direct proof, we'll have to deal with the squared term (and square roots)! This might get nasty; we'd rather deal with the nicer right side.

  • First, let's find the contrapositive of Q. Q is "n is even", so the contrapositive is "n is odd".

  • Then, let's find the contrapositive of P. P is "n squared is even", so the contrapositive is "n squared is odd".

Proof by Contradiction

Contradiction is a great choice for proving things that have infinitely many cases (since you can just prove the opposite, which is finite!).

Contradiction Form:

  • Do some steps here.

Example:

Show that there are infinitely many prime numbers.

Proof by Cases

Sometimes, we can break a statement down into smaller cases and prove each one individually. These cases could be something like "a is odd" and "a is even", where it is impossible for any other case to be true. If all possible cases are proven, then the entire statement is then proven.

Example:

Proof by Induction

Induction is great for proving that something is true for everything in a set (often the natural numbers). If we prove the first value, then prove that the next value is true, then the value after that is also true, and so on.

This can be likened to the domino effect. If the first one's true, then it knocks down the domino for the next value. If that's true, then it knocks out the next one, and so on until every possible value is covered.

Induction Form

  • Prove P(0). (Base case)

  • Assume P(k). (Induction Hypothesis)

  • Prove P(k+1). (Induction Step)

    • When proving the induction step, we can treat the induction hypothesis as a true statement!

Example: The Two Color Theorem

Here's a visually intuitive example of induction in action!

The Two Color Theorem states that for any collection of intersecting line segments, the regions that they divide can be assigned one of two colors such that a line never has the same color on both sides.

In order to prove this, let's start at the base case, where there is only one line:

Here, it's pretty clear that it is indeed possible to put a different color on each side of the line, in this case let's just choose blue and red.

Now, let's see what happens when we add a new line:

Looks like we have a conflict now! The blues on the top and reds on the bottom are touching. However, it's not too hard to fix this. Let's just flip the blue and red on one of the sides:

It turns out that this process: drawing a new line and flipping all of the colors on one side, works in any configuration of lines! This is because of the fact that flipping the colors on one side of a line doesn't affect whether or not those colors are alternating.

Stronger Induction

Sometimes, an inductive proof can be rather elusive. It might be easier to make the statement stronger and prove that instead! (It should make sense that a stronger argument means that a weaker argument is also true.)

For example, take the statement "The sum of the first n odd numbers is the square of a natural number."

As we try to figure out a pattern, we might notice something:

Proof of the Induction Principle

The Well Ordering Principle states that for all subsets of natural numbers, there exists a smallest number in that subset.

More Resources

As a reminder, the contrapositive of a statement P  ⟹  QP \implies QP⟹Qis ¬Q  ⟹  ¬P\lnot Q \implies \lnot P¬Q⟹¬P. These two statements are logically equivalent! Sometimes, it's easier to prove the contrapositive, which would in turn prove the original statement.

Goal: P  ⟹  QP \implies QP⟹Q****

Assume ¬Q\lnot Q¬Q.

Therefore ¬P\lnot P¬P.

Let's use the definition of an odd number (n=2k+1n = 2k + 1n=2k+1for some natural number k) to work through this.

If n=2k+1n = 2k +1n=2k+1, then n2=4k2+4k+1n^2 = 4k^2 + 4k + 1n2=4k2+4k+1 = 2(2k2+2k)+12(2k^2 + 2k) + 12(2k2+2k)+1.

Since this is also the form of an odd number, n2n^2n2must be odd!

Instead of proving that PPPis true, maybe we could show that ¬P\lnot P¬Pmakes no sense at all! (We know that if ¬P\lnot P¬Pis false, then PPPmust be true.)

Goal: P  ⟹  QP \implies QP⟹Q****

Assume ¬P\lnot P¬P.

Therefore, ¬P\lnot P¬Pis a contradiction.

First, let's assume the opposite - that there are a finite number of prime numbers, which can be represented by the set p1,⋯ ,pk{ p_1, \cdots, p_k}p1​,⋯,pk​.

Let's define a number q=(p1×p2⋯×pk)+1.q = (p_1 \times p_2 \cdots \times p_k) + 1.q=(p1​×p2​⋯×pk​)+1.

Since qqqis larger than any prime number in our set, it can't be a prime number by our assumption.

Note that we did not prove thatq=(p1×p2⋯×pk)+1q = (p_1 \times p_2 \cdots \times p_k) + 1q=(p1​×p2​⋯×pk​)+1is a prime number! This is because we started with a false statement, so everything in the middle of a contradiction proof cannot be generalized to true statements.

Show that there exists an irrational x and y such that xyx^yxyis rational.

First, let's find some cases. The two cases could be that xyx^yxyis rational or xyx^yxyis irrational. If xyx^yxyis rational (the first case is true), then we're done! But if the second case is true, then we're back to where we started.

Since all we need to do is show existence, we can choose any irrational number for x and y. 2\sqrt{2}2​seems like an easy choice!

22\sqrt{2}^{\sqrt{2}}2​2​is irrational, but what about (22)2(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}}(2​2​)2​? That's just 222!

For n = 1: 1=12=n21 = 1^2 = n^21=12=n2

For n = 2: 1+3=22=n21 + 3 = 2^2 = n^21+3=22=n2

For n = 3: 1+3+5=32=n21 + 3 + 5 = 3^2 = n^21+3+5=32=n2

Wow, looks like not only is the sum equal to some arbitrary square number, but it's actually equal to n2n^2n2! It's a lot easier to prove this fact than the original one, and proving this completely includes the original statement.

Another (aptly named) principle that might come in handy is the Strong Induction Principle! This principle is useful for when you don't want your base case to be 000. The Strong Induction Principle states that if we prove all of the propositions from P(0) up to P(k), then P(k) can be used as a base case:

(∀k∈N)((P(0)∧P(1)∧⋯∧P(k))  ⟹  P(k+1))  ⟹  (∀k∈N)(P(k))(\forall k \in \mathbb{N})((P(0) \land P(1) \land \cdots \land P(k)) \implies P(k+1)) \implies (\forall k \in \mathbb{N})(P(k))(∀k∈N)((P(0)∧P(1)∧⋯∧P(k))⟹P(k+1))⟹(∀k∈N)(P(k))

(¬∀n)P(n)  ⟹  ((∃n)¬(P(n−1)  ⟹  P(n))(\lnot \forall n)P(n) \implies ((\exists n) \lnot (P(n - 1) \implies P(n))(¬∀n)P(n)⟹((∃n)¬(P(n−1)⟹P(n))

This is not trivial! Think about rational numbers- it's impossible to get the smallest rational number because it extends to −∞-\infty−∞.

This principle justifies the use of induction for any set of natural numbers. If the smallest number (base case) always exists, then we can just prove that and move upwards, rather than trying to prove both k−1k-1k−1and k+1k+1k+1.

Note 2:

Note 3:

Lecture 2 Slides:

https://www.eecs70.org/assets/pdf/notes/n2.pdf
https://www.eecs70.org/assets/pdf/notes/n3.pdf
https://www.eecs70.org/assets/pdf/lec-2-handout.pdf