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?

  • $\begingroup$ Well, what is your definition of $Y$ being infinite? Perhaps something like this: there exists an injection from $\mathbb{N}$ into $Y$? Or: there exists a surjection from $Y$ onto $\mathbb{N}$? Both of these would get you what you are after, I think. $\endgroup$ – Axesilo Apr 22 '16 at 2:53
  • $\begingroup$ So you are calling $\mathbb{N}$ a finite set? $\endgroup$ – ClassicStyle Apr 22 '16 at 2:59
  • $\begingroup$ @TylerHG sorry, the subset of $\mathbb{N}$ is finite, more precisely: $I_n = \{p\in \mathbb{N}; 1<p\le n\}$, gonna update the question $\endgroup$ – Guerlando OCs Apr 22 '16 at 3:07
  • $\begingroup$ @DA29731 the definition of a infinite set is simply one that is not finite. I updated my definition of finite set, please see it $\endgroup$ – Guerlando OCs Apr 22 '16 at 3:08

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.


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.