0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Erick Wong Oct 29 '19 at 23:16
  • $\begingroup$ 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. $\endgroup$ – Gabe Fernandez Oct 30 '19 at 0:15
1
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – ℋolo Oct 31 '19 at 11:31
0
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gabe Fernandez Oct 30 '19 at 0:00
  • $\begingroup$ @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. $\endgroup$ – Mohammad Riazi-Kermani Oct 30 '19 at 0:05
  • $\begingroup$ @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$ :) $\endgroup$ – Erick Wong Oct 30 '19 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.