2
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ Where did you find this proof? I'd have given it somewhere between 10% to 0% score in an exam. $\endgroup$ – Asaf Karagila♦ Sep 3 '15 at 13:59
  • $\begingroup$ @AsafKaragila: In a non-official textbook! Is it wrong? $\endgroup$ – Sisabe Sep 3 '15 at 14:00
  • $\begingroup$ 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. $\endgroup$ – egreg Sep 3 '15 at 14:05
  • $\begingroup$ @egreg: So could you please help me prove it? $\endgroup$ – Sisabe Sep 3 '15 at 14:10
  • $\begingroup$ First (why) $|X \cup Y| \ge |X| = +\infty$ $\endgroup$ – gt6989b Sep 3 '15 at 14:14
2
$\begingroup$

The first “why” has no explanation; the fact that $X\cup Y$ is infinite stems from $X$ being infinite.

The second “why” is exactly the whole proof.

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.)

$\endgroup$
4
  • $\begingroup$ Thanks for your answer. I know how to prove that g is 1-1, but don't know how to prove it is a surjective. Could you please explain it? $\endgroup$ – Sisabe Sep 3 '15 at 14:34
  • $\begingroup$ @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)$. $\endgroup$ – egreg Sep 3 '15 at 14:38
  • $\begingroup$ 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$ $\endgroup$ – Sisabe Sep 4 '15 at 14:01
  • $\begingroup$ @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)$. $\endgroup$ – egreg Sep 4 '15 at 14:01

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.