Question

Exercise 3 (Cantor-Bernstein-Schröder). Let f: A → B and g: B → A be injective maps. We define recursively the sets C = UCn Co = A \ g(B), Cn+1 = g(f(Cn)), nƐN and a new map h: A → B by if x E C, f (x) h(x) = if x 4 C, g='(x) where the preimage g¬1(x) is well-defined since g is injective and x E g(B) in that case (check that!). Show that h is bijective. Conclude that if |A| < |B| and |B| < |A|, then |A| = |B|.

Answer 1

e fi AB and g :BJA be injective maps.we want a bijective map hi AB: we define recursively the sets Co= Aug 6), ent) = g(fas)), Easy to see that en CA sno set, C=U Cn SA NENUOS. Let us define a map hi AB by h = 2 f , ifaec - 1 g @ ifade Given that g: B A injective. Suppose g(8) = B'CA. So g: B B' is a bijection and hence g": B'B exists. in 24 c = a & Go -> x E g (B) This for x&c. & exists. This shows that above map is well defined. To show that h is one one: Ket asyEA such that ha)=hG). Case(): If noyEG, then ha) = h) In this => x=y (since f:A-B inj) case his injective

Case(s): If any eC² = Aic, then xy EgB) = 6 ha =ho) → 9 m) -97 () ² x=y [ g: B B' bijection ] In this case his abo injective. Case (ii): XE C and ye Anc. Then h = had → 583 = [iye g(6)] > gcf@)) =y: XEC XE Cm for some mzo. > gffG) E Cmti > y = 9648 € (36=ů cm). This is or contradiction. So this case can not arise. Hence hi AB one one. To show his suvjective: Ket YEB. Then either (i) y E f6 or ☺ € Bif©). If ye f(C) , then there exists a EC such that f = you "XEC swh that ha) = f(x) = Y. - In this case his surjective. I n the If ye Bif(c): claim: g (Bif(()) = Anc

MEO co=A96 If ye Bif), then y q f((). Now of© = offớcn) = G4C1) = i cuti = in =CICO ..y & f (0) = g(y) ¢ C.Co Again, g9 € g B) g G & Co. Therefore g & c re, g y Edic cog(8-f@) SAVC Conversely, let a EAIC Then x&c=> x¢ Cn for all nyo. → & gf 0 E: 9fC) = Cico] > g®4 f© > g EB foc: fOSB] ne g (Bifre) Alce g (B, f()) Hence, g (B f(()) = AIC ссА → f© SB This shows that if y E Bifo, then } REAIC, such that g) = 2 > gt@=y for medic Lig'exists on? . 7X EAIC such that h = 9(2)=y. This completes the proof of surjectiveness. Hence h: A B is a bijection.

Secondparti If All Bl is then there is an injective map f: A B . If BIC | Al, then there is an injective map g: B A. By Contor, Bernstein - Schroder theorem, there is a bijection map hi AB. Any bijective map between two sets have same Cardinality. So I A1 = 1B1.