Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
$\exp{}{}{}{}{}$ –  Olivier Bégassat Jun 22 at 6:08
    
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. –  Bryan Jun 22 at 6:23
1  
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$ –  R.. Jun 22 at 13:08

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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