# Proof of one-one correspondence

a. Show that every infinite set can be put into a bijection with a proper subset of itself.

b. Show that the initial segment determined by $n$ cannot be put into a bijection with the initial segment determined by $m\in\mathbb{N}$, if $m<n$.

c. Show that $\mathbb{N}$ cannot be put in a bijection with any initial segment of $\mathbb{N}$.

a. : I know that every infinite set has a denumberable subset, but I don't understand how it can have a bijection to the subset since its infinite?

b. and c. : Do not know how to do. Would it be true the other way around?

-

Hints:

a. If $A$ is an infinite set, $A'=\{a_n\mid n\in\mathbb N\}$ is a denumerable subset, then $f(a)=a$ for $a\notin A'$, and $f(a)=a_{n+1}$ whenever $a=a_n$ for some $n$ is a bijection of $A$ with a subset of itself.

b. Suppose there was an injection from $\{0,\ldots,n\}$ to $\{0,\ldots,m\}$, and $m<n$, then we can reiterate the injection because the elements in the range are also in the domain. Show that every iteration must omit some elements from the range, and so after finitely many steps we must have a function from a non-empty set into an empty set which is absurd.

c. $\mathbb N$ can be put in bijection with some of its proper subsets. Show that this property is preserved under bijections, and deduce from b. that $\mathbb N$ cannot be injected into any of its proper initial segments.

-
THanks Asaf! But for a. why is it a bijection? What I get from that is , $f(a)=a$ is not in the subset of $A'$ and $f(a)=a_{n+1}$ is also not in the subset so how can the subset and the infinite set form a bijection? I understand b now, thank you for that! And for c I do not understand, wouldn't an initial segment be a proper subset of $\mathbb{N}$ thus making it a bijection? –  Q.matin Feb 8 '13 at 1:27
I didn't say that the bijection is with $A'$. It's a bijection with a proper subset. It is easy to verify that the function is injective, and you just have to note that $a_0$ is not in the range of the function. Therefore the range is a proper subset, and therefore the function is a bijection with a proper subset as wanted. –  Asaf Karagila Feb 8 '13 at 1:28
+1 of course... :-) –  amWhy Feb 8 '13 at 1:28
@amWhy: Thank you, of course! :-) –  Asaf Karagila Feb 8 '13 at 1:31
@Q.matin: What is an initial segment of $\mathbb N$? What do you know about these sets? These are finite sets. There are only finitely many elements below $n$. We know that you can't have an injection from a set of $3$ elements into a set of $2$. Follow this by induction, or hide the induction using my hint, either way you get that proper initial segments do not share a certain property with $\mathbb N$ itself. This is a property which is preserved under bijections, so if $\mathbb N$ was in bijection with $\{0,\ldots,k\}$ you would have an initial segment with this property, contradiction. –  Asaf Karagila Feb 8 '13 at 1:51