Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that there is a mapping from a set to itself that is one-to-one but not onto iff there is a mapping from the set to itself that is onto but not one-to-one.

I'm trying to argue that the order of the sets cannot be correct, but I don't understand how there has to be a two different mappings instead of just one.

Thanks guys!

share|cite|improve this question
What do you mean by "the order of the sets cannot be correct"? In particular, there is just one set mentioned. – Robert Israel Feb 13 '13 at 0:14
Maybe I have the wrong idea. I'm not really sure. But a 1-1 mapping always means an element has to map to a unique one, and to be "not onto" means that not every element is mapped to. So if every element has to be unique, but not every element is mapped to, the order must be |S| + 1 at least. – Lilluda 5 Feb 13 '13 at 0:18
The order of what must be at least $|S|+1$? The order of $S$? But the order of $S$ is $|S|$. So, how can $|S|$ be at least $|S|+1$? Therein lies the answer. – Gerry Myerson Feb 13 '13 at 0:21
I'm new to proofs, how would I write that out? Would that be a contradiction? – Lilluda 5 Feb 13 '13 at 0:21
Have you heard about infinite sets? – Berci Feb 13 '13 at 0:24

Let $f:S\to S$ be one-to-one but not onto. Let $X:=S\setminus f(S) \ne \emptyset$.

Then define $g:S\to S$ such that if $s\in f(S)$ then ??? and if $s\in X$ then ???. And it will be onto but not one-to-one.

The other direction can be done similarly.

share|cite|improve this answer
... can be done similarly with the axiom of choice (which is obviously to be assumed here). – Brian M. Scott Feb 13 '13 at 0:32
@Berci for your first question mark, i came up with "then g(s) is not contained in f(s)" and for the second one "g(s) is contained in X" is that correct? – Lilluda 5 Feb 13 '13 at 0:48
first ???: let $g(s):=f^{-1}(s)$ which is unique due to the one-to-one requirement. second ???: let $g(s):=s_0$ a fixed (but arbitrary) element $s_0\in S$. ..@Brian, yes indeed, AC is needed. – Berci Feb 13 '13 at 15:32

It is perhaps easier to imagine that you have two sets, both nonempty, and then find an argument that there exists a one-to-one but not onto $f:A\to B$ exactly if there exists an onto but not-one-to-one $g:B\to A$.

Once you have proved that, it will still be true in the case that $A$ and $B$ happen to be identical. (And then the existence of a function $S\to S$ that is either "not onto" or "not one-to-one" will imply that $S$ is not empty).

share|cite|improve this answer
So with this, I've come up with B mapping to one element in A. This would be an example of something that is onto, but not 1-1 right? – Lilluda 5 Feb 13 '13 at 1:24
@Lilluda: You mean every element in $B$ maps to the same element of $A$? That won't be onto, unless $A$ has only one element. – Henning Makholm Feb 13 '13 at 1:45
What if i define $g:B\to A$ s.t. g(x) =f(x) if x is an element of f(x) otherwise g(x) = x. Wouldn't that be onto? – Lilluda 5 Feb 13 '13 at 1:51
@Lilluda: Are you assuming $f:A\to B$? Then what you're trying to define here won't even be $B\to A$ because you define $g(x)$ to be either $f(x)$ or $x$, both of which are in $B$ rather than in $A$. And $f(x)$ makes no sense if $x$ is in $B$ because the domain of $f$ is $A$ not $B$. – Henning Makholm Feb 13 '13 at 2:05
can you provide more insight... i still haven't figured this out – Lilluda 5 Feb 13 '13 at 3:39

Your Answer


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.