Can someone explain what that means? How can there exist an injective function from an infinite set to a proper subset of itself. A function from a set A to a set B where B has fewer elements than A cannot be one-to-one, but this is what it says in a textbook.
Thanks in advance.
On
Well, we can go for detailed proof . But I don't think this is what you asked for . So , for your question, the answer is 'yes' . It is a necessary and sufficient condition . Because when you are talking about infinity, you don't Know what are you talking about . And a bijective function is nothing but a way to order the elements of two sets . For an example, $\Bbb{Q}$ and $\Bbb{N}$ look like there will not be any bijective mapping between them . But by Continuum Hypothesis the cardinality of $\Bbb{N}$ is $\aleph_{o}$ and cardinality of $\Bbb{R}$ is $\aleph_{1}$ . And cardinality of any other set can't be fit in between these two. And to increase your surprise cardinality of $\Bbb{Q}$ is same of cardinality of $\Bbb{N}$. So every where u can't go with the idea of infectivity between finite sets and can't apply it to understand infinity sets.
On
What you have described does not work for finite sets; however, it does for infinite sets.
Consider the set of natural numbers $N = \lbrace 1, 2, 3, \ldots \rbrace$.
This set is infinite; and the set whose cardinality (which Cantor called $\aleph_{0}$) is exactly the same as any other (what we call, "countably infinite set").
Take for example, the set of positive even numbers, $E = \lbrace 2, 4, 6, \ldots \rbrace$ . Clearly, $E$ is a proper subset of $N$.
However, there does exist a 1-1 correspondence between $E$ and $N$; namely, take every counting number $n$ in $N$ and map it into $E$ by the function $f(n) = 2n$. Every element in $N$ gets mapped to one and only one corresponding element in $E$, and moreover, the mapping is onto; i.e., every element in $E$ has some element in $N$ mapped to it.
Conclusion: The number of positive even integers is identical to the number of natural numbers.
When Cantor developed his theory on countable and uncountable infinite sets, and different orders of infinity some 140 years ago, it was not without controversy; and to a certain extent, that is still true today.
On
Can someone explain what that means?
It means what it sounds like it means.
How can there exist an injective function from an infinite set to a proper subset of itself.
Consider $A = \{1,2,3,4,5,6,7,......\} = \mathbb N$ and $B = \{2,3,4,5,6.....\} = \mathbb N - \{1\}$.
Let $f:A \to B$ be $f(n) = n+1$ so $1 \mapsto 2$, $2\mapsto 3$, etc.
$f$ is one-to-one.
A function from a set A to a set B where B has fewer elements than A cannot be one-to-one,
No. It can't but a proper subset doesn't have to have "fewer elements". Consider $A$ and $B$ above. They both have the "same number" of elements.
In fact, if a proper subset has the "same number of elements" than it and that superset must both be infinite. That's a consequence of this statement.
....
The proof is difficult and heavy on precise technical definitions, but a paraphrase of the result is the following:
If $A$ is finite then there can not be an injective function from $A$ to a proper subset.
If $A$ is finite and has $n$ elements, then if $B\subsetneq A$ then $B$ has fewer than $n$ elements and ... nope, you can't have an injective function.
If $A$ is infinite then there must be a proper subset $B$ and an injective function between them.
Well, if $A$ is infinite then you can pick $a_1, a_2, a_3,......$ out of them. You can let $B = A - \{a_1\}$. You can have $f: A\to B$ by if $x = a_i$ let $f(x) = a_{i+1}$. If $x$ doesn't equal any of the $a_i$ then $f(x) = x$. That function is injective.
....
Okay, that was not a proof but an explanation as to why the sentence makes sense and why it is reasonable that it would be true (even though it is counter-intuitive).
Instead of considering an infinite set, lets look at the finite case. If we consider the an injective function from the set to itself the image has the same number of elements as the set itself and so is a surjection, and thus a bijection. If we consider a function from the set to a proper subset it cannot be injective because of the pigeon-hole principle, there will be two elements of the set with the same image.
Now an infinite set differs in that you can find an injection into a proper subset. This matches intuition in that we would expect that if we take a finite number of things away from an infinite set there would still be infinitely many left. It's this feature that ensure it can't be a finite set and so characterizes infinite set.