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 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)

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:
File comment: Illustration
Exercise16_10.pdf [32.44 KiB]
Downloaded 239 times

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).

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

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