Introduction to Proofs

Logic, sets, induction and functions, the language every later course is written in.

1. Unit 1

   Logic and sets

   Implications and contrapositives · Quantifiers and negation · Set operations and set equality · Proof by contradiction

   • The contrapositiveChoose
   • Negating an ε-δ statementChoose
   • A De Morgan law for set differenceProof
   • The square root of 2 is irrationalProof

2. Unit 2

   Induction

   Mathematical induction

   • Sum of the first odd numbersCompute
   • Prove the sum of odd numbers by inductionProof

3. Unit 3

   Functions and counting

   Injective and surjective functions · Counting functions and subsets

   • Counting injective functionsCompute
   • The power set of a power setCompute
   • If g∘f is injective, so is fProof