# Equivalence of sets.

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.