What is a proof

  • A step by step argument
  • Should be verifiable and finite
  • Every statement must be something we already know from the start such as a definition, axiom or previously-proved theorem
  • Or a logical consequence of some conjunction of previous statements
  • If you've previously established
  • and also that
  • then you can deduce
  • Or if you've established
  • and also that
  • then you can deduce

Finding proofs

  • To prove subset ralations (where and are sets)
  1. Take a general member of , and give it a name ("let ")
  2. Use definition of to say something about
  3. Follow through the logical consequences of that
  4. aiming to prove that also satisfies the definition of
  • To prove set equality "" prove and
  • To prove numerical equality "" prove and

Types of proofs

Proof by construction

  • Also known as proof by example
  • Can be used where the theorem asserts the existence of some object with a specific property just give the example, show it has the property

Proof by cases

  • Also known as proof by exhaustion or (if lots of cases) "brute force"
  • Identify and prove a number of different cases which cover all possibilities

Proof by contradiction

  • Also known as "reduction ad absurdum"
  • Start by assuming the negation of the statement you want to prove
  • Deduce a contradiction
  • Therefore, the statement must be true

Proof by induction

  • Prove base case
  • then prove inductive case where is true which implies is true

Good proofs

Theorem: There are infinitely many primes

  • Proof:
  • Assume by way of contradiction that there are finitely many primes
  • Let be the number of primes
  • Let be all the primes
  • Define
  • This is bigger than any prime
  • Therefore must be a composite of primes
  • However, , if you divide by you will get a remainder of by our construction
  • So cannot be a multiple of therefore cannot be a multiple of any prime number
  • Thus by way of contradiction there is no largest prime

Definition: A set is countable

  • A set is countable if either
    • It is finite, or
    • It can be put in one-to-one correspondence (i.e. bijection) with
  • For example the set of all FIT2014 students is finite,
  • The sets , and can all be put in one-to-one correspondence with
  • However, the set of all sets of strings is not countable
  • The sets of all languages is not countable

Theorem: The set of all languages is uncountable

  • Proof:
  • Suppose by way of contradiction that the set of all languages is countable
  • Since we know it's not finite, there must be a bijection between and {all languages}
  • Let the members of the set of all languages be
  • Recall, that the set of all strings is countable so we can list them as
  • Define a language as follows:
  • We have constructed so that, for each , it differs from in whether or not it contains
  • So it differs from all languages, yet is it a language, this is a contradiction
  • The set of all languages is uncountable

Bad proofs

From a falsehood you can prove anything

  • Recall that : always true if is False regardless of
  • |{McTaggart, The Pope}|
  • |{McTaggart, The Pope}| as
  • McTaggart is the Pope

Induction flaws

  • In an induction proof a lack of a base step allows for invalid proofs
  • Additionally proving a base of and using allows for some strange behaviour such as with the proof that every word is uniform (made up of only one letter (lecture 2.2))

Ugly proofs

  • Often long and not to the point
  • However, there may be some uses like for example proving no formula using basic arithmetic operations for the 5th power polynomial or higher