Fundamentals of Proof

  • A proof is a logical argument demonstrating that a certain proposition or statement is true, it involves assumptions, propositions, intermediate conclusions and a final conclusion.
  • Direct proof is the most common type of proof. Here, you start from a given set of assumptions and use them to show that a certain conclusion is valid.
  • Proof by contradiction (also known as reductio ad absurdum) involves assuming that the statement you’re trying to prove is not true, and then showing that this leads to a contradiction.
  • Proof by induction is typically used for proving statements involving positive integers. It is characterised by two steps: the base case and the inductive step.
  • In a base case, you prove the statement for a specific small number, typically 1.
  • In the inductive step, you assume the statement holds for an arbitrary positive integer ‘k’. Then you show that, under that assumption, it must also work for ‘k+1’.
  • Proof by exhaustion involves checking all the possible cases in a finite set. This method is useful when the number of cases is relatively small.

Types of Statements and Definitions

  • Conditional statements have a hypothesis and conclusion. They follow the structure “if p, then q.”
  • Biconditional statements are based on “if and only if” and imply that the hypothesis and conclusion depend on each other. They are true in both directions.
  • Counterexamples are used to disprove conditional and biconditional statements. They are examples that conform to the initial conditions of the statement but don’t produce the correct outcome.
  • An axiom or postulate is a statement that is accepted without proof. They form the basis of any mathematical theory.
  • A theorem is a major result that has been proved to be true using axioms or other already established theorems.
  • A lemma is a “helping theorem,” a proposition that isn’t interesting in its own right, but is used to assist in the proof of a larger theorem.
  • A corollary is an immediate consequence of a theorem.

Proof Techniques

  • Modus Ponens is a deductive argument meaning ‘the mode of affirming’. If a statement of “if p then q” is true and p is true, then q must also be true.
  • Modus Tollens is another deductive argument, meaning ‘the mode of denying’. This says if “if p then q” is true and q is false, then p must be false.
  • Disjunctive Syllogism also referred to as ‘the either/or scenario’. Given the statement “p or q”, if ‘p’ is false then ‘q’ must be true and vice-versa.
  • The use of Quantifiers in mathematics, such as “for all” and “there exists”, allows for more generalised and powerful forms of statements.
  • Familiarity with Logic and Set Notation will facilitate the reading and writing of formal mathematical proofs.

Remember that understanding and practising the construction of mathematical proofs is a critical skill in further mathematics. Being able to follow a series of logical steps to arrive at a conclusion, and then to articulate that process in a clear and concise way, is a significant part of your maths development.