Let A be a finite, nonempty set of cardinality n. (a) Prove that if a ...

 

Transcribed Image Text:

Let A be a finite, nonempty set of cardinality n. (a) Prove that if a € A, then |A-{a}|=n-1. Hint: If the bijection f: A→ {1,..., n} happens to satisfy f(a) = n, then there is little to do. What if f(a) #n? (b) Let B be a subset of A that has cardinality m E NU {0}. Use part (a) and induction on m to prove that |AB| =n-m. You may use A - B = (A- (B-{a})) - {a} for any a € B without proof. Let A be a finite, nonempty set of cardinality n. (a) Prove that if a € A, then |A-{a}|=n-1. Hint: If the bijection f: A→ {1,..., n} happens to satisfy f(a) = n, then there is little to do. What if f(a) #n? (b) Let B be a subset of A that has cardinality m E NU {0}. Use part (a) and induction on m to prove that |AB| =n-m. You may use A - B = (A- (B-{a})) - {a} for any a € B without proof.