# Countable and Uncountable sets

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.

• 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}$. – bradhd Mar 1 '14 at 2:53
• There are also problems with the second argument: what does $|\mathbb N|+1$ mean? – bradhd Mar 1 '14 at 2:54
• Hint: It is countably infinite. You can find an explicit bijective map from $\mathbb{N}$ to $\mathbb{N}\cup \{a\}$. – André Nicolas Mar 1 '14 at 2:55
• 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. – Jose Antonio Mar 1 '14 at 3:00
• 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$. – Jose Antonio Mar 1 '14 at 3:12

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\}}$$