Prove that if $M$ is an arbitrary infinite set and $A$ is countable, then $M \sim M \cup A$

$M\sim N$ are said to be equivalence if a one-to-one correspondence can be set up between their elements

This exercise comes in the book of funtional analysis to Kolmogorov.

My doubt goes around how a formal proof would be written, in this book several examples come, but, the functions are not built. I think it is clear how to create function 1-1, assigning the first elements of $M$ to $A$ and the rest of them back to $M$


We may assume without loss of generality that $A \cap M = \emptyset$, otherwise replace $A$ with $A \setminus M$ (which is countable being a subset of a countable set).

Consider the case where $A$ is countably infinite. The idea is that we will take a countable subset $N = \{ n_0,n_1,n_2,\ldots\}$ of $M$, then map $N$ into itself by mapping it onto the 'even' part, i.e., $n_k \mapsto n_{2k}$. This leaves the 'odd' part free to map $A = \{a_0,a_1,a_2,\ldots\}$ onto, i.e., $a_k \mapsto n_{2k+1}$. We may fix the elements of $M\setminus N$.

Being completely formal, let $f\colon\mathbb{N} \to M$ be an injection and $g\colon \mathbb{N} \to A$ a bijection. Then $h\colon M \sqcup A \to M$ defined by $$ h(m) = \begin{cases} f(2f^{-1}(m)) & \text{if $m\in \operatorname{im} f$,} \\ f(2g^{-1}(m)+1) & \text{if $m \in A$,} \\ m & \text{otherwise.} \end{cases}$$

The case where $A$ is finite is similar, except you only need to reserve the first $|A|$-many elements of $N$ (again, a countable subset of $M$ with some fixed enumeration) to map the elements of $A$ to, translating the elements of $N$ forward by $|A|$-many indices, and keeping the other elements of $M$ fixed.

| cite | improve this answer | |

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.