# A set is infinite only if the set is 1-1 with a proper subset, but what the author wrote is not complete, is it?

I think for the one-one mapping, to $$(A\backslash x_1)\cup Y$$, from $$X$$, there is one element which must be borrowed from $$Y$$, but the author writes all of $$Y$$ is mapped to itself. In mapping one-one from the finite subset of $$X$$, $$A=\{x_1, x_2, \ldots, x_n\}$$, the image of the function needs the $$n$$th element to be mapped to a member of $$Y$$, doesn't it? Shouldn't one just say the map borrows some element from $$Y$$, shifting all of $$Y$$ by one as well?

The second to last paragraph of section 4, of M. Rosenlicht's Intro to Analysis, reads as follows:

It is easy to show that a set $$X$$ is infinite if and only if it may be put into one-one correspondence with a proper subset of itself. To do this, note first that if $$X$$ is finite then any proper subset has a smaller number of elements, whereas two finite sets in one-one correspondence must have the same number of elements. This proves the "if" part. On the other hand, if $$X$$ is infinite then there exist distinct elements $$x_1, x_2, x_3, ...$$ in $$X$$. The complement of $$x_1, x_2, x_3, \ldots$$ in $$X$$ is a subset $$Y$$, so that $$X = \{x_1, x_2, x_3, \ldots\} \cup Y \textrm{and} \{x_1, x_2, x_3, \ldots\} \cap Y = \emptyset.$$ A one-one correspondence between $$X$$ and its proper subset $$\{ x_2, x_3, x_4, \ldots\} \cup Y$$ is given by the function which sends each $$x_n$$ into $$x_{n+1}$$ and each element of Y into itself. This proves the "only if" part, completing the proof.

I believe the distinct elements goes along with the Axiom of Choice, as used in answers to the other questions I found on this topic.

• No, the mapping does not borrow anything from $Y$. The element that is “borrowed” is $x_{n+1)$. There is no requirement that the subset $A$ be mapped one-to-one onto itself. – Erick Wong Oct 29 '19 at 23:16
• Well, the quoted text doesn't say anything about mapping the last element of $A$, but he also doesn't explicitly say that the distinct elements $x_n$ is a finite set. – Gabe Fernandez Oct 30 '19 at 0:15

You are using the Axiom of Choice to select (and denumerate) a countably infinite subset of $$X$$. You can always do that because $$X$$ is infinite. Let's say $$S= \{x_1, x_2, \ldots \}.$$ Anything that's left over is defined as being in $$Y$$; in other words, $$Y$$ is defined by $$X \setminus S$$. You're then mapping the countably infinite set $$S ~1-1$$ into a proper subset of itself and leaving $$Y$$ alone, to achieve a $$1-1$$ map from $$X \to X \setminus \{x_1\}$$.

• Sorry for being very pedantic, but the use of the axiom of choice is only for showing that countable (infinite) subset of $X$ exists, selecting a countable (infinite) subset and well order it does not require any choice. This is equivalent to the statement "Dedekind finite iff finite" which is very weak choice principal – ℋolo Oct 31 '19 at 11:31

The proof in the text is correct.

You do not have to borrow anything from $$Y$$ because you have a one-to-one correspondence between $$\{x_1, x_2, x_3,....\}$$ and $$\{x_2, x_3, x_4,....\}$$ with the mapping $$x_n\to x_{n+1}$$

• But those two sets have a different number of elements, because the second set is just to indicate that removing $x_1$ suffices to make it a proper subset. – Gabe Fernandez Oct 30 '19 at 0:00
• @GdbF137 That is the point that you can remove one element from an infinite set and still have a one-to-one correspondence between the proper subset and the whole set. – Mohammad Riazi-Kermani Oct 30 '19 at 0:05
• @GabeFernandez The two sets have a different number of elements? Seems to me that the number of elements in the first set is $\aleph_0$ and the number of elements in the second set is also $\aleph_0$ :) – Erick Wong Oct 30 '19 at 0:29