[ 3 posts ] 
 Exercise [16.10] 
Author Message

Joined: 12 Mar 2008, 10:57
Posts: 69
Location: India
Post 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.

02 Apr 2008, 08:01

Joined: 22 Apr 2010, 15:52
Posts: 43
Location: Olpe, Germany
Post Re: Exercise [16.10]
Here's an illustration for the solution of Sameed Zahoor:
File comment: Illustration
Exercise16_10.pdf [32.44 KiB]
Downloaded 239 times

20 Aug 2010, 14:57

Joined: 12 Jul 2010, 07:44
Posts: 154
Post 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).

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
16 Apr 2011, 18:36
   [ 3 posts ]