0
$\begingroup$

Is $\mathbb{N}\cup\{a\}$, for some $a\not\in\mathbb{N}$ countable or uncountable?

$\mathbf{Attempt: }$ It is true that a set is countable if there exists an injective function $f : S → N$ from $S$ to the natural numbers $\mathbb{N}$. Since $\mathbb{N}\cup\{a\}$ has cardinality $|\mathbb{N}|+1$, $\mathbb{N}\cup\{a\}$ is not countable. However, there is a surjective mapping from $\mathbb{N}\cup\{a\}\to\mathbb{N}$. A set $X$ is uncountably infinite if $X$ is nonempty and there is no surjective function from the natural numbers to $X$. $\mathbb{N}\cup\{a\}$ is nonempty, and there is a surjective mapping from $\mathbb{N}\cup\{a\}\to\mathbb{N}$. But we had said that it is not countably infinite. This seems to be a contradiction, so $\mathbb{N}\cup\{a\}$ is countably infinite.

$\endgroup$
  • 1
    $\begingroup$ The first attempt doesn't work out. You could argue that if it is countable then $\mathbb{N}\cup\{a_1,\ldots,a_n\}$ is countable for any $a_1,\ldots,a_n\notin \mathbb{N}$. $\endgroup$ – bradhd Mar 1 '14 at 2:53
  • $\begingroup$ There are also problems with the second argument: what does $|\mathbb N|+1$ mean? $\endgroup$ – bradhd Mar 1 '14 at 2:54
  • 1
    $\begingroup$ Hint: It is countably infinite. You can find an explicit bijective map from $\mathbb{N}$ to $\mathbb{N}\cup \{a\}$. $\endgroup$ – André Nicolas Mar 1 '14 at 2:55
  • $\begingroup$ How do you pin down "adding an uncountably infinite number of times"? I'm a newbie in math but as far as I know an infinite number of operations to be applied is a very dangerous step to allow for any number of paradoxes. On the other hand the union of countable sets is countable. $\endgroup$ – Jose Antonio Mar 1 '14 at 3:00
  • 1
    $\begingroup$ For a more general approach. Suppose $X$ and $Y$ are countable sets. Then there exists bijective map $f: \mathbb{N} \to X$ and $g: \mathbb{N} \to Y$. Now define $h: \mathbb{N} \to X\cup Y$ by setting $h(2n)=f(n)$ and $h(2n+1)=g(n)$ and show that $h[\mathbb{N}]=X\cup Y$. $\endgroup$ – Jose Antonio Mar 1 '14 at 3:12
3
$\begingroup$

Hint:

Let $f: \Bbb N \rightarrow \Bbb N \cup \{a\}$ be defined thus. $$f(1) = a \; \text{and } \; f(x) = x - 1 \; \text{for every member in $\Bbb N \setminus \{1\}$} $$

You can show that this is a bijection.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy