Exercise I.C.1

Question

If a set $S$ is infinite, then it can be put in a one-to-one correspondence with a proper subset of itself.

Toğrul Topal · Accepted Answer

Notice that $\mathbb{N}$ can be put into a one-to-one correspondence with its proper subset $\{2n: n\in \mathbb{N}\}$ using the function
    $$\sigma: \mathbb{N} 	o \mathbb{N}, \quad n \mapsto 2n$$
    First enumerate the elements of $S$ by $l:\mathbb{N}	o S$. Then consider the composition $l\circ \sigma: \mathbb{N} 	o S$ and its image $(l \circ \sigma)(\mathbb{N}) =: T \subsetneq S$. Then $T$ is enumerated by $\mathbb{N}$ using bijection $l \circ \sigma$ and $S$ is enumerated by $\mathbb{N}$ using bijection $l$; and so we can easily build a one to one correspondence between them
    $$c:S	o T, \quad c(s) = (l\circ \sigma) \big ( l^{-1}(s) \big)$$

Exercise I.C.1

Answers

Comments

Exercise I.C.1

Answers

Comments

Add answer