text: # 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. Commented Sep 3, 2015 at 13:59
  • @AsafKaragila: In a non-official textbook! Is it wrong? Commented Sep 3, 2015 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. Commented Sep 3, 2015 at 14:05
  • First (why) $|X \cup Y| \ge |X| = +\infty$ Commented Sep 3, 2015 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)$. Commented Sep 3, 2015 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$ Commented Sep 4, 2015 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)$. Commented Sep 4, 2015 at 14:01
metadata: {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}