6
$\begingroup$

I'm aware of the existence of this question: Surjectivity implies injectivity

However, the question is regarding a finite set $S$. I was wondering, though: What happens when $S$ is an infinite set? Zhen Lin addresses this cases in his answer, by saying that it ceases to be necessarily true, for example $f:\mathbb{N}\rightarrow \mathbb{N}$ defined by $x \mapsto x+1$ is injective but not surjective.

My question is: what happens if $S = \mathbb{R}$? Constructing a counterexample for $S=\mathbb{N}$ seems simple enough, but I'm struggling to find a function $f:\mathbb{R}\rightarrow \mathbb{R}$ that's injective but not surjective. Does such a function even exist? If so, how to construct it?

And perhaps a more general question (maybe too broad): For which infinite sets $S$ there is a function $f:S\rightarrow S$ such that $f$ is injective but not surjective?

$\endgroup$
4
  • 3
    $\begingroup$ $\exp{}{}{}{}{}$ $\endgroup$ Jun 22, 2014 at 6:08
  • $\begingroup$ That every infinite set is Dedekind-infinite requires some very weak form of choice. For example, the assumption that every infinite set contains a countable subset is sufficient. $\endgroup$
    – user123641
    Jun 22, 2014 at 6:23
  • 1
    $\begingroup$ If you already have such an $f$ for $\mathbb{N}$, just extend it to $\mathbb{R}$ by defining it as the identity on $\mathbb{R} \cap \mathbb{N}^C$ $\endgroup$ Jun 22, 2014 at 13:08
  • $\begingroup$ This is, to some extent, related: Equivalent characterisations of Dedekind-finite proof $\endgroup$ Nov 24, 2016 at 10:14

3 Answers 3

8
$\begingroup$

The function $f(x) = \arctan x$ is injective but clearly not surjective on $\mathbb{R}$.


In general, it is true that every Dedekind-infinite set has this property.

$\endgroup$
5
$\begingroup$

$f(x)=\arctan x$, for example, is injective but not surjective.

$\endgroup$
5
$\begingroup$

For your second question, let $S$ be an infinite set and $f:S\to S$ be any injection. Then fix some $x_0$ in $S$. Then, since $S$ is infinite, $|S|=|S\setminus\{x_0\}|$ ($|A|$ is the cardinal of a set $A$), so there exists a bijection $\phi$ of $S$ onto $S\setminus\{x_0\}$. Then $\phi\circ f$ seen as an application from $S$ into $S$ is injective but not surjective.

Note: usual definition of cardinals require the Axiom of Choice. We don't need the whole theory of cardinals here, but I don't whether AC is necessary or not.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .