cardinalselementary-set-theoryfunctionsreal-analysis
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.
So, they have the same cardinality. Let's rationalize this by enumerating the rationals.
Note that we can 'count' all the rationals like in this picture:
There is a small detail about removing repetition, but that's okay. Here, for example, we might count $1, 1/2, 2, 3,$ (skip $2/2$), $1/3 ,$ ...
This describes a function from $\mathbb{N} \to \mathbb{Q}^+$. In fact, it's a bijection, so it serves as a counterexample to both.
Note that the word "equivalent" requires context, literally it would just be interpreted as "satisfying some equivalence relation", but what the nature of this relation is not automatically understood.
In the context of cardinality it means to have a bijection. Namely an infinite set has a bijection with a proper subset of itself. Of course this requires the axiom of choice (or rather a small fragment of it) to hold. This characterization is known as Dedekind-infinite. Without the axiom of choice it is consistent that there are sets which are infinite (in the sense that they are not with bijection with any finite ordinal), but they are not Dedekind-infinite.
For example note that $f(n)=n+1$ is a bijection from $\omega$ into $\omega\setminus\{0\}$. It shows that $\omega$ is a Dedekind-infinite set. For the more general case see my answer for Equivalent characterisations of Dedekind-finite proof.
Best Answer
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.