Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

66 FUNCTIONS AND ALGORITHMS [CHAP. 3

3.26. Prove the following equivalent formulation of the Schroeder–Bernstein Theorem 3.5:

SupposeX⊇Y⊇X 1 andXX 1. ThenXY.

SinceXX 1 there exists a one-to-one correspondence (bijection)f:X→X 1 SinceX⊇Y, the restriction of

ftoY, which we also denote byf, is also one-to-one. Letf(Y)=Y 1. ThenYandY 1 are equipotent,

X⊇Y⊇X 1 ⊇Y 1

andf:Y→Y 1 is bijective. But nowY⊇X 1 ⊇Y 1 andYY 1. For similar reasons,X 1 andf(X 1 )=X 2 are

equipotent,

X⊇Y⊇X 1 ⊇Y 1 ⊇X 2

andf:X 1 →X 2 is bijective.Accordingly, there exist equipotent setsX, X 1 ,X 2 ,...and equipotent setsY, Y 1 ,Y 2 ,...

such that

X⊇Y⊇X 1 ⊇Y 1 ⊇X 2 ⊇Y 2 ⊇X 3 ⊇Y 3 ⊇···

andf:Xk→Xk+ 1 andf:Yk→Yk+ 1 are bijective.

Let

B=X∩Y∩X 1 ∩Y 1 ∩X 2 ∩Y 2 ∩···

Then

X=(X\Y)∪(Y\X 1 )∪(X 1 \Y 1 )∪···∪B

Y=(Y\X 1 )∪(X 1 \Y 1 )∪(Y 1 \X 2 )∪···∪B

Furthermore,X\Y, X 1 \Y 1 ,X 2 \Y 2 ,...are equipotent. In fact, the function

f:(Xk\Yk)→(Xk+ 1 \Yk+ 1 )

is one-to-one and onto.

Consider the functiong:X→Ydefined by the diagram in Fig. 3-11. That is,

g(x)=

{

f(x) ifx∈Xk\Ykorx∈X\Y

x ifx∈Yk\Xkor x∈B

Thengis one-to-one and onto. ThereforeXY.

Fig. 3-11

SupplementaryProblems

FUNCTIONS

3.27. LetW={a, b, c, d}. Decide whether each set of ordered pairs is a function fromWintoW.

(a) {(b, a), (c, d), (d, a), (c, d) (a, d)} (c) {(a, b), (b, b), (c, d), (d, b)}

(b) {(d, d), (c, a), (a, b), (d, b)} (d) {(a, a), (b, a), (a, b), (c, d)}

3.28. LetV={ 1 , 2 , 3 , 4 }. For the following functionsf:V→Vandg:V→V, find:

(a)f◦g; (b),g◦f; (c)f◦f:

f={( 1 , 3 ), ( 2 , 1 ), ( 3 , 4 ), ( 4 , 3 )} and g={( 1 , 2 ), ( 2 , 3 ),( 3 , 1 ), ( 4 , 1 )}

3.29. Find the composition functionh◦g◦f for the functions in Fig. 3-9.