Yatir Halevi
Posted on Monday, 10 February, 2003 - 09:45 am:
I have in front of me a proof to the theorem: ''If each of two sets M and N can be mapped injectively into the other, then there is a bijection from M to N.''

I'm having trouble following the proof. Could somebody help me? :)

Here is the proof:

Let f:M® N and g:N® M be injections. For each A Í M define the set F(A) Í M by:

F(A):=M\g(N\f(A))

that is, any subset A Í M is mapped to f(A) Í N, then we take its complement N\f(A) in N, then its complement is mapped back to obtain g(N\f(A)) Í M, and of this we finally take to complement in M.

Suppose that there is some A0 with F(A0)=A0, that is, such that g(N\f(A0))=M\A0. Then, clearly, (Not very clear to me... :) ),

j(x):=

f(x) if x Î A0

g-1(x) if x Î A0

provides a bijection from M to N. Hence it remains to find such a ''fixed set'' A0. (I also have a proof for that, and that was easy to understand)

Thanks in advance,

Yatir

Chris Purcell
Posted on Monday, 10 February, 2003 - 11:30 am:
Firstly, g is an injection. Since M\A0=g(N\f(A0)), that means every x Î A0 must equal g(y) for some y Î N, and since g is an injection that element is unique. Hence defining j(x):=g-1(x) on M\A0 makes sense, giving us a bijection between M\A0 and N\f(A0).

Secondly, f is an injection. That means j also gives us a bijection between A0 and j(A0) @ f(A0) simply by virtue of being injective on it.

Now A0 and M\A0 are disjoint and together make up all of M. Equally, j(A0) @ f(A0) and j(M\A0) @ N\f(A0) are disjoint and together make up all of N. j is thus a bijection from M to N.

Sorry if this is still impenetrable - clearly is always hard to explain!

Chris

Yatir Halevi
Posted on Monday, 10 February, 2003 - 12:08 pm:
Got it! Thanks.
I just needed someone to spell it out for me

Yatir