In proving the theorem: Every infinite set is equivalent to one of its proper subsets, I am confused about the following:

We consider an infinite set $M$, which always contains a countable subset, which is denoted $A := \{a_1, a_2, \dots \}$. We may partition $A$ into two countable subsets:

$$ A_1 := \{a_1, a_3, a_5 \dots \}, \qquad A_2 := \{a_2, a_4, a_6 \dots \} $$

and we have a one-to-one correspondence between $A$ and $A_1$ given by $a_n \to a_{2n-1}$.

We can then extend this correspondence to a one-to-one correspondence between the two sets:

$$ A \cup (M - A) = M, \qquad A_1 \cup (M-A) = M-A_2 $$

by simply assigning $x$ itself to each $x \in M-A$. I don't quite understand this extension, how are we allowed to do this?

This is a proof taken from Introductory Real Analysis by Kolmogorov and Fomin.

  • $\begingroup$ What do you mean by "being allowed"? It is not a matter of permissions. $\endgroup$ – Andrés E. Caicedo Feb 17 '18 at 3:02
  • $\begingroup$ @AndrésE.Caicedo as in what is the property that permits us to perform this extension $\endgroup$ – dimebucker Feb 17 '18 at 3:04

You have a bijection between the elements of $A$ and $A_{1}$. That is, you have a map $f\colon A\longrightarrow A_{1}$ which is bijective. You define another map, $g\colon A\cup (M-A) \longrightarrow A_{1}\cup (M-A)$, such that $$g(x)= f(x) \quad \text{if} \quad x\in A,\quad \text{and} \quad g(x)=x \quad \text{if}\quad x\in M-A.$$

Note that $A\cap (M-A)=\varnothing$, so $g$ is well-defined and $g$ is a bijection.


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.