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

1,629

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.

Share:
1,629

Related videos on Youtube

Guerlando OCs
Author by

Guerlando OCs

Updated on August 01, 2022

Comments

  • Guerlando OCs
    Guerlando OCs over 1 year

    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?

    • Axesilo
      Axesilo over 7 years
      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.
    • ClassicStyle
      ClassicStyle over 7 years
      So you are calling $\mathbb{N}$ a finite set?
    • Guerlando OCs
      Guerlando OCs over 7 years
      @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
    • Guerlando OCs
      Guerlando OCs over 7 years
      @DA29731 the definition of a infinite set is simply one that is not finite. I updated my definition of finite set, please see it