Joined: 12 Mar 2008, 10:57 Posts: 69 Location: India

Exercise [16.10]

Let "a" be a mapping from B to A and "b" be another map from A to B. Our aim is to find a 1-1 onto map from A to B. Assume 'a' and 'b' are into functions for if 'a' was onto then 'a~' ('a' inverse) would do the job and if 'b' was onto then it would itself be the required function. Now apply a~ to A (if possible),then b~ to a~A(if possible),then again a~ to b~a~A and so on...Such a sequence of steps will either continue forever or will terminate.If it terminates,it would do so in either an even or an odd number of steps.Hence, A can be partitioned into 3 disjoint classes whose union is A.Call them as follows; A(inf) : infinte number of steps to terminate, A(even): even number of steps, and A(odd): odd number of steps. Similarly divide B into B(inf),B(even) and B(odd). We see that b maps A(inf) onto B(inf),A(even) onto B(odd) and a~ maps A(odd) onto B(even).Now define a function 'f' such that

f(x)= b(x) if x belongs to A(inf) or A(even) f(x)= a~(x) if x belongs to A(odd)

Here's an illustration for the solution of Sameed Zahoor:

Attachment:

File comment: Illustration Exercise16_10.pdf [32.44 KiB]
Downloaded 239 times

20 Aug 2010, 14:57

deant

Joined: 12 Jul 2010, 07:44 Posts: 154

Re: Exercise [16.10]

Actually, with all due respect to J. Beckmann for his effort, I think there's a clearer way to diagrammatically represent the solution to this exercise. (Attached).

Attachments:

File comment: PDF version: Exercise [16.10].pdf [95.94 KiB]
Downloaded 149 times

File comment: MS Word 2010 version (original): Exercise [16.10].docx [124.21 KiB]
Downloaded 142 times