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
    Commented Sep 3, 2015 at 13:59
  • $\begingroup$ @AsafKaragila: In a non-official textbook! Is it wrong? $\endgroup$
    – Sisabe
    Commented Sep 3, 2015 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
    Commented Sep 3, 2015 at 14:05
  • $\begingroup$ @egreg: So could you please help me prove it? $\endgroup$
    – Sisabe
    Commented Sep 3, 2015 at 14:10
  • $\begingroup$ First (why) $|X \cup Y| \ge |X| = +\infty$ $\endgroup$
    – gt6989b
    Commented Sep 3, 2015 at 14:14

1 Answer 1

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
    Commented Sep 3, 2015 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
    Commented Sep 3, 2015 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
    Commented Sep 4, 2015 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
    Commented Sep 4, 2015 at 14:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .