Proof by Bijection

• functions properties
  • let $f:A⟶B$ be a function from set A to B
  • surjective if
    • $\mathrm{\forall }b\in B,\mathrm{\exists }a\in A$ such that $f(a)=b$
  • injective if
    • $\mathrm{\forall }a,a^{\prime }\in A$ if $f(a)=f(a^{\prime }),$ then $a=a^{\prime }$
  • bijective if it is both surjective and injective

Used primarily in Counting Theorems proofs, where the left hand size of an equation will be equal to the right hand size