# How to complete this proof? Union of a countably infinite set and a finite set is countably infinite

Theorem. Let $X$ be a countably infinite set and $Y$ be a finite set. Then $X\cup Y$ is countably infinite.
Proof. Since $X$ is a countably infinite set, then there exists a bijection function $f\colon \mathbb{N}\longrightarrow X$ and since $Y$ is a finite set, then $X\cup Y$ is (why) is infinite. Therefore there exists (why) a bijection function $g\colon X\longrightarrow X\cup Y$ so $g\circ f\colon \mathbb{N}\longrightarrow X\cup Y$ is a 1-1 and surjective function. This means that $X\cup Y$ is countably infinite.
Could you please tell me the reason of the two WHYs?

• Where did you find this proof? I'd have given it somewhere between 10% to 0% score in an exam. – Asaf Karagila Sep 3 '15 at 13:59
• @AsafKaragila: In a non-official textbook! Is it wrong? – Sisabe Sep 3 '15 at 14:00
• Well, this “proof” basically says “prove it”, because the existence of $g$ is exactly the same as saying that $X\cup Y$ is countably infinite. Moreover the fact that $Y$ is finite has nothing to do with $X\cup Y$ being infinite. – egreg Sep 3 '15 at 14:05
• @egreg: So could you please help me prove it? – Sisabe Sep 3 '15 at 14:10
• First (why) $|X \cup Y| \ge |X| = +\infty$ – gt6989b Sep 3 '15 at 14:14

The first “why” has no explanation; the fact that $X\cup Y$ is infinite stems from $X$ being infinite.
Since $Y$ is finite, also $Y'=Y\setminus X$ is finite. Note that $X\cup Y=X\cup Y'$ and $X\cap Y'=\emptyset$. Since $Y'$ is finite, there exist $d\in\mathbb{N}$ and a bijection $$h\colon\{0,1,\dots,d-1\}\to Y'$$ Define $$g\colon\mathbb{N}\to X\cup Y'$$ by $$g(n)=\begin{cases} h(n) & \text{if n<d}\\[6px] f(n-d) & \text{if n\ge d} \end{cases}$$ Can you prove $g$ is bijective?
(Note: if you're afraid about the case when $d=0$, that is, $Y'=\emptyset$, don't be; anyhow, in this case there's exactly nothing to prove.)
• @Sisabe If an element is in $Y'$, then it belongs to the image of $h$ (hence of $g$). Otherwise it belongs to the image of $f$, say $f(m)$. Then $g(m+d)=f(m)$. – egreg Sep 3 '15 at 14:38
• sorry, but I'm very newbie in Set Theory. Could you please explain the proof of the surjectivity in more details? I have been told only this method to proof the surjectivity: $\forall z \in X\cup Y', \exists$ a $n\in \mathbb{N}$ such that $g(n)=z$ – Sisabe Sep 4 '15 at 14:01
• @Sisabe Isn't it what I showed? If $x\in X\cup Y'$, then either $x\in Y'$ or $x\in X$. In the first case the surjectivity of $g$ says $x=g(n)$, for some $n$, $0\le n<d$, so that $x=h(n)$. In the second case, $x=f(m)$ for some $m$, because $f$ is surjective; then $x=f(m)=h(d+m)$. – egreg Sep 4 '15 at 14:01