The Road to Reality http://www.roadtoreality.info/ 

Exercise [16.10] http://www.roadtoreality.info/viewtopic.php?f=19&t=46 
Page 1 of 1 
Author:  Sameed Zahoor [ 02 Apr 2008, 08:01 ] 
Post subject:  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 11 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) which is the reqd. one to one onto function. 
Author:  jbeckmann [ 20 Aug 2010, 14:57 ] 
Post subject:  Re: Exercise [16.10] 
Here's an illustration for the solution of Sameed Zahoor: Attachment: 
Author:  deant [ 16 Apr 2011, 18:36 ]  
Post subject:  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).

Page 1 of 1  Archived: 07 Aug 2014 
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ 