Counting: Function.For sets a.B.a function aB is a relation between A and B.(a,f(a))s.t.for each aA,3 B satisfying b=f(a) Injection(one to one function):if a a',then f(a)f(a). Surjection(onto)∀b∈B,3a∈A,s.tf(a=b. Bijection(one to one correspondence)Injection&Surjection. Porpostion1.For sets A,B (1)if3 injection f:A→B then A≤|BL. (2)if3 surjection f:A→B then A≥lBl (3)if 3 bijection f A-B then Al Bl. proof: (1)Assume B<Al since 3 functionf A B by definition Va EA,3E B s.t.f(a)=b.since B<Al then 3a t at s.t. f(a)=f(ar)(by pigeonhole principal)This is contradiction with the fact that f is a injection. (2)Assume B>Al since 3 functionf AB by definition a∈A,3b∈Bs.t.f(a)=b.3b∈Bs.t.there does not exist a E A satisfying f(a)=b This is contradiction with the fact that f is a surjection. (3)(1)&(2)→(3). 0 2Counting: Function.For sets A,B. a function A → B is a relation between A and B. (a, f(a)) s.t. for each a ∈ A, ∃b ∈ B satisfying b = f(a) Injection(one to one function): if a 6= a 0 ,then f(a) 6= f(a 0 ). Surjection(onto) ∀b ∈ B, ∃a ∈ A, s.t.f(a) = b. Bijection(one to one correspondence) Injection & Surjection. Porpostion1. For sets A,B (1) if ∃ injection f : A → B then |A| ≤ |B|. (2) if ∃ surjection f : A → B then |A| ≥ |B|. (3) if ∃ bijection f : A → B then |A| = |B|. proof: (1) Assume |B| < |A| since ∃ functionf : A → B by definition ∀a ∈ A, ∃!b ∈ B s.t.f(a) = b. since |B| < |A| then ∃a 6= a0 s.t. f(a) = f(a0)(by pigeonhole principal) This is contradiction with the fact that f is a injection. (2) Assume |B| > |A| since ∃ functionf : A → B by definition ∀a ∈ A, ∃!b ∈ B s.t.f(a) = b. ∃b ∈ B s.t.there does not exist a ∈ A satisfying f(a) = b This is contradiction with the fact that f is a surjection. (3) (1)&(2) ⇒ (3). 2