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

N

.''

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

Here is the proof:

Let $f : M \to N$ and $g : N \to M$ be injections. For each $A \subseteq M$ define the set $F (A) \subseteq M$ by:

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

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

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

$φ (x) : =$

$f (x)$ if $x \in A_{0}$

$g^{- 1} (x)$ if $x \in A_{0}$

provides a bijection from $M$ to $N$ . Hence it remains to find such a ''fixed set'' $A_{0}$ . (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 \A_{0} = g (N \f (A_{0}))

, that means every

x \in A_{0}

must equal

g (y)

for some

y \in N

, and since

g

is an injection that element is unique. Hence defining

φ (x) : = g^{- 1} (x)

M \A_{0}

makes sense, giving us a bijection between

M \A_{0}

and

N \f (A_{0})

Secondly, $f$ is an injection. That means $φ$ also gives us a bijection between $A_{0}$ and $φ (A_{0}) ≅ f (A_{0})$ simply by virtue of being injective on it.

Now $A_{0}$ and $M \A_{0}$ are disjoint and together make up all of $M$ . Equally, $φ (A_{0}) ≅ f (A_{0})$ and $φ (M \A_{0}) ≅ N \f (A_{0})$ are disjoint and together make up all of $N$ . $φ$ 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