MA121 Study Guide - Final Guide: Summation, Mathematical Induction, Pigeonhole Principle
Document Summary
Pigeonhole principle to prove the contrapositive of the statement: If f is a one-to-one function, then it is also an onto function. We shall prove that if f : a a is not onto, then f is not one-to-one. Then the set of outputs of f is a subset of a with less than n elements. But the set of inputs of f , i. e. , the domain of f is a with n elements. Pigeonhole principle, there must be (at least) two distinct elements ai and aj (a pair of pigeons!) with f (ai) = f (aj). This implies that f is not one-to-one. (b) let a and b be subsets of the same universal set and denote by a(cid:52)b the symmetric di erence of a and b. Apply de morgan"s laws to prove directly the statement: Suppose that ac bc = ac bc.
