Discrete Mathematics for Computer Science

The Pigeon-Hole Principle 253

(d) F(A 1 ) - F(A 2 ) _ F(Ai - A 2 ).

(e) A, c F-I(F(A1)).

(f) Find an example in which A 1 C A 2 but F(A 1 ) = F(A 2 ).

(g) Find an example in which A 1 36 F-^1 (F(A 1 )).

19. Let A be any nonempty set, and let .FA be the set of all functions from A to R.
    (a) Why is F + G E YA for all F, G e .A.
    (b) Prove (F+G) +H = F+(G+H) for all F,G,H E•YA.
    (c) Let Zero E .FA be defined by Zero(a) = 0 for all a E A. Prove that Zero + F = F

for all F E `A.

(d) For F E .-A, define P by F(a) = -F(a) for each a E A. Prove that F + F =

Zero = F + F for all F E YA.

20. Let .A be defined as in Exercise 19. For each F, G E .FA, define F .G(a)=

F(a) .G(a).

(a) Why is F. G eFA for all F, G e•YA?

(b) Prove that F. G = G. F for all F, G E YA.

(c) Prove that (F. G). H = F. (G. H) for all F, G, H E .A.

(d) Prove that the function U : A --> R defined by U(a) = 1 for all a E A satisfies

U.F = F = F. U for all F E YA.

(e) Prove that (F+G)•H = F.H+G.H for all F,G, H E.-A with F+G de-

fined as in Exercise 19.

(f) Prove there are F, G Ef7A such that F 0 Zero and G # Zero but F. G = Zero.

21. (a) Let F : A -- B be a function. Prove that F is onto if and only if F-^1 (Bi) A 0 for
    each nonempty subset B 1 of B.

(b) Let F : A -> B be a function. Prove that F is onto if and only if F(F-I (B 1 )) -

BI for all B 1 C B.

22. Let X be a set, and let .Fx be the set of all 1-1 functions from X onto X. We have two
    operations on functions in Fx : o and -1. Prove the following statements called group
    axioms. (If the results are already proved in the book, note where to find the proofs.)

(a) For all F, G E Yx, F o G E Y.

(b) For all E, G, H c .x, (F o G) o H = F o (G o H) (Associative Law).

(c) For all F E Fx , F o Idx = Idx o F = F. (Identity Axiom).

(d) For all F E Yx, there exists an F-^1 such that F o F-1 = F-^1 o F = Idx (In-

verse Axiom).

23. An operation ® on a set Y is commutative if for all y, z E Y, y ® z = z ® y. For X
    and .x as defined in Exercise 22, prove that o need not be commutative on .x.


24. Let F: A --+ B be a function. Define G : P(3) -> P'(A) by G(B 1 ) = F-I(B1).

Prove that G is 1-1 if and only if F is onto.

U The Pigeon-Hole Principle

After a February town meeting in rural New England, the 200 people attending entered the

parking garage to get their cars and drive home. (Assume that no one was walking home

in the typical winter weather.) An observer counted 65 cars exiting the parking garage.