# [SOLVED] Cantor-Schroder-Bernstein

• Oct 11th 2009, 01:55 PM
[SOLVED] Cantor-Schroder-Bernstein
Consider the injections $\displaystyle f : \mathbb{N} \rightarrow \mathbb{N} \sqcup \mathbb{N} : n \rightarrow (0, n)$ and $\displaystyle g : \mathbb{N} \sqcup \mathbb{N} \rightarrow \mathbb{N}$ given by
$\displaystyle (i, n) \rightarrow 3n + i$, where $\displaystyle i = 0$ or $\displaystyle i = 1$.
(a) From the proof of Cantor-Schroder-Bernstein compute F(n) directly for n =
0, 1, 2, 3, 4 and find $\displaystyle F^{-1} (0,4)$.

Is this just simply finding g o f? Like for n=2 it would be f(2) = 2 then g(0,2) = 6?

Or is it... Find x such that (g o f)(x) = 0,1,2,3,4?

OR! Is it something to do with the fact that... if i=0 then F(n) can be either 0,3,6, ... (3n + 0 basically). And if i=1 then F(n) can be either 1,4,7, ... (3n+1)..?

Since F isn't actually defined I'm not sure what it is.

AND. Since the CSB theorem is involved, there will be bijection A -> B so it makes me think that some values of n will equal 0,3,6, ... or 1,4,7 ... and the rest will have to be defined as something else...
• Oct 11th 2009, 02:15 PM
Plato
Quote:

Consider the injections $\displaystyle f : \mathbb{N} \rightarrow \mathbb{N} \sqcup \mathbb{N} : n \rightarrow (0, n)$ and $\displaystyle g : \mathbb{N} \sqcup \mathbb{N} \rightarrow \mathbb{N}$ given by
$\displaystyle (i, n) \rightarrow 3n + i$, where $\displaystyle i = 0$ or $\displaystyle i = 1$.
(a) From the proof of Cantor-Schroder-Bernstein compute F(n) directly for n = 0, 1, 2, 3, 4 and find $\displaystyle F^{-1} (0,4)$.

Do you realize that there are as many difference proofs of the Cantor-Schroder-Bernstein theorem as there are places where a proof is published?
So there is no way for us to know how your $\displaystyle F$ is defined.
• Oct 12th 2009, 08:46 AM
Bleh im dumb.

Proof is the one with the zig-zig diagram that has A on one side, B on the other, f is an injection from A to B and B is an injection from B to A.
Then you repeatedly apply f and g to an element $\displaystyle a \in A$.
Now, we must be in one of two situations: either

(a) we can go up indefinitely from a or end on the A side, or,
(b) we end on the B side.

Let $\displaystyle A_1 = a \in A$, a is type a, $\displaystyle A_2 = a \in A$, a is type b. Then $\displaystyle A = A_1 \cup A_2$ and $\displaystyle A_1 \cap A_2 = \emptyset$.

From this we have a well defined map $\displaystyle F : A \rightarrow B$ given by...

$\displaystyle F(a) = f(a)$ if $\displaystyle a \in A_1$, $\displaystyle g^{-1}(a)$ if $\displaystyle a \in A_2$
Taken from the notes!

Indeed I probably shoulda noticed this bit first...

So, Does this mean that F(0), F(1), etc = f(0), f(1), ... respectively since they are single integers and $\displaystyle F^{-1}(0,4) = g(0,4) = 12$ since its of the form (i,n), so we apply g to it..?
• Oct 13th 2009, 08:14 AM