[Math] find an injective function from a finite set to an infinite one, and a surjective inverse

elementary-set-theoryfunctions

I have to prove that there exists an injective function from $X$ to $Y$, being $X$ a finite set, and $Y$ an infinite set. I must also prove that there exists a surjective function from $Y$ to $X$.

My definition of finite set $X$ is that there exists a bijection of a finite subset of $\mathbb{N}$ to $X$. More precisely, this set is $I_n = \{p\in \mathbb{N}; 1<p\le n\}$

For the injective function, I was thinking about picking the greatest element of $X$ and mapping to something, and then the antecessor of the greatest element and so, since the set is finite I can always find them. But the problem is: where do I map them to?

For the surjective function I know that I can map lots of elements from $Y$ to a single element in $X$, but I don't know a rule that would work for any infinite set. Remember that it does not need to be countable.

I think that the only way to create a rule that would work for any infinite set would be to think about parts of this set?

Best Answer

As I mentioned in my comment, a good way to go is to prove the following lemma:

Lemma: Let $Y$ be a set. The following are equivalent:

  1. $Y$ is infinite.
  2. There exists an injective map $g: \mathbb{N} \rightarrow Y$.
  3. There exists a surjective map $h: Y \rightarrow \mathbb{N}$.

First, let's see how the lemma implies the result. If $X$ is finite, then there exists a bijection $f: X \rightarrow S$, where $S \subseteq \mathbb{N}$. We can then compose $f$ with the inclusion map $i : S \hookrightarrow \mathbb{N}$, which is automatically injective, to get the injective function $i \circ f: X \rightarrow \mathbb{N}$. Last, we follow up with the injective map $g$ from the lemma to get the injection $g \circ i \circ f : X \rightarrow Y$.

You can show there exists a surjective function $Y \rightarrow X$ in a similar way.

There are different levels of how rigorously you can prove the lemma, such as going to the Recursion Theorem, but maybe it's best to keep it elementary. (I had an argument here previously, but I cut it out for being overly confusing.) For example, to show (1) implies (2), just assume $Y$ is infinite and notice that given any sequence of distinct elements $f(1), f(2), \ldots, f(n)$ in $Y$, you can always find some $y$ not in this list, or else $Y$ would be finite. Define $f(n+1) = y$ and continue.