1
$\begingroup$

We have $A,B \subseteq \mathbb{N}$ non-empty subsets of natural numbers. How to show that if there is a injective function $f : A \rightarrow B$, then there is a injective AND monotone $g : A \rightarrow B$ too.

And is it true that if there are injective functions $f : A \rightarrow B$ and $g: B \rightarrow A$ then there is also a bijective function $h: A \rightarrow B$

$\endgroup$
  • 2
    $\begingroup$ At least as a first approach I would divide into cases according to whether $A$ is finite or infinite. (Later on it may be that you can combine both cases in one wording). $\endgroup$ – Henning Makholm Jan 5 '16 at 12:21
  • $\begingroup$ For the second question: Yes; this is the celebrated Cantor-Schröder-Bernstein theorem. $\endgroup$ – Henning Makholm Jan 5 '16 at 12:22
0
$\begingroup$

The construction of the monotone injective function $g:A\rightarrow B$ is as follows: Let $A=\{a_1, a_2, ...\}.$ an ordered arrangement of $A$. Define $g(a_1)=\min f(A), g(a_2)=\min (f(A)- \{g(a_1\}),g(a_3)=\min (f(A)-\{g(a_1), g(a_2)\}) ...$
This might help in answering your second question also.

$\endgroup$
0
$\begingroup$

The answer to the second question is yes, it's the Schröder-Bernstein theorem. It's valid in general and do not require $A$ and $B$ to be subset of $\mathbb N$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.