Suppose that f is a function from A to B where A and B are finite sets. Explain why | f(S )| ? | S | for all subsets S of A.

SolutionStep 1Proof by ContradictionLet us assume that S be a subset of A.By Contradiction, |f[S]| > |S|Now we have to define a function x : f(S) S by x(b) = some a belong to x like that f(a) = b.Pigeonhole PrincipleIf A and B are finite sets then |A| > |B| then f will not be an onto function.According to the pigeonhole Principle, if some ‘a’ belong to x and ‘b’ belongs to f[x]. Thenx(b) = x(b’) = aSo, if f(a) = b and f(a) = b’ Here, f be a onto function then |f(a)| bHence, by contradiction it is proved that |f(S)| |S| for all subset of A.