16
$\begingroup$

I am looking for a beautiful way of showing the following basic result in elementary set theory:

If $A$ is a countable set then the set of finite subsets of $A$ is countable.

I proved it as follows but my proof is somewhat fugly so I was wondering if there is a neat way of showing it:

Let $|A| \le \aleph_0$. If $A$ is finite then $P(A)$ is finite and hence countable. If $|A| = \aleph_0$ then there is a bijection $A \to \omega$ so that we may assume that we are talking about finite subsets of $\omega$ from now on. Define a map $\varphi: [A]^{<\aleph_0} \to (0,1) \cap \mathbb Q$ as $B \mapsto \sum_{n \in \omega} \frac{\chi_B (n)}{2^n}$. Then $\varphi$ is injective hence the claim follows. (The proof of which is what is the core-fugly part of the proof and I omit it.).

$\endgroup$

11 Answers 11

29
$\begingroup$

If $A$ is an infinite countable set, $S$ is the set of finite subsets of $A$ and $S_k$ is the set of $k$-element subsets of $A$, then

$$ |S| = \sum_{k \in \mathbb{N}} |S_k| \leq \sum_{k \in \mathbb{N}} |A|^k \leq \sum_{k \in \mathbb{N}} \aleph_0 = |\mathbb{N}| \cdot \aleph_0 = \aleph_0 $$

$\endgroup$
  • $\begingroup$ Dear Hurkyl, I think this is exactly what I was looking for when I asked the question. I am dismayed to find that as of now I am the only person to upvote your beautifully short proof. $\endgroup$ – Rudy the Reindeer Apr 14 '13 at 15:19
30
$\begingroup$

Subsets of $A$ are in bijection with subsets of $\mathbb{N}$ so it suffices to enumerate the latter. Any subset of $\mathbb{N}$ can be written as a finite string using the following thirteen characters $$0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ \{\ \}\ ,$$ By setting $${\{}=10 \qquad {\}}=11 \qquad {,}=12$$ writing out a subset of $\mathbb{N}$ is a base-$13$ expression of an integer. For example $$\{ 0,1 \}_{13} = 10 \cdot 13^4 + 0 \cdot 13^3 + 12 \cdot 13^2 + 1 \cdot 13 + 11 = 287662$$

The map sending $$S \mapsto \text{the least}\ n\ \text{represented by}\ S$$ defines an injection into $\mathbb{N}$.

$\endgroup$
  • 1
    $\begingroup$ never saw this proof before :) (+1) $\endgroup$ – Ittay Weiss Apr 14 '13 at 14:58
  • 7
    $\begingroup$ If you want real austerity suitable for the times (and to avoid base 13), you could represent subsets of N by binary strings like 111101111101111111011111 where a block of $n +1$ 1's represents $n$ and $0$ is punctuation. Then reread these as binary numbers! $\endgroup$ – Peter Smith Apr 14 '13 at 15:14
  • 3
    $\begingroup$ Indeed! I like this proof because there's no work to do in encoding the string other than assigning values to the extra characters. Of course we could drop $\{$ and $\}$ completely and use base-$11$ instead, but even dropping $\{$ and $\}$ is more work than I can be bothered to do. $\endgroup$ – Clive Newstead Apr 14 '13 at 15:21
  • 1
    $\begingroup$ In the phrase "Any subset of $N$ can be written as...", I think it should be "Any finite subset of ..." instead. $\endgroup$ – evaristegd Aug 29 '18 at 13:44
9
$\begingroup$

It is sufficient to prove the claim for $A=\mathbb{N}$. Denote by $\operatorname{Fin}(\mathbb{N})$ the set of all finite subsets of $\mathbb N$. We have $$\operatorname{Fin}(\mathbb{N}) = \bigcup_{n\in\mathbb{N}}\left\{ A\subseteq\mathbb{N}: \max(A) = n \right\},$$ which is a countable union of finite sets as for each $n\in\mathbb{N}$ there certainly are less than $2^n = \left|\mathcal{P}(\{1,\ldots,n \})\right|$ subsets of $\mathbb{N}$ whose largest element is $n$. Hence, $\operatorname{Fin}(\mathbb{N})$ is countable itself.

$\endgroup$
5
$\begingroup$

Clive's answer works (of course)! Or you could go like this, exploiting the familiar trick of coding a sequence by using powers of primes.

Index the members of $A$ as $a_1$, $a_2$, $a_3$ $\ldots$ (we know we can, because it is countable).

Given a finite non-empty subset $F \subset A$, let $a_f$ be the highest indexed member of $F$, and for $1 \leq j \leq f$, put $c_j = 1$ iff $a_j \in F$ and $c_j = 0$ otherwise. Form the product $n_F = 2^{c_1} \cdot 3^{c_2} \cdot 5^{c_3} \cdot \ldots \cdot \pi_f^{c_f}$, where $\pi_j$ is the $j$-th prime. In an obvious way, $n_F$ uniquely codes for $F$.

The map $F \mapsto n_F$ is plainly an injection from the non-empty finite subsets of $A$ to the natural numbers (distinct subsets go to distinct numbers), so the finite subsets are countable.

$\endgroup$
  • $\begingroup$ Both Clive's and your proof seem to be my proof with fractions of powers of two replaced by powers of $13$ and powers of primes respectively : ) $\endgroup$ – Rudy the Reindeer Apr 14 '13 at 15:10
  • $\begingroup$ I suppose there are only so many different ways in which one can prove results that are as basic as what I am asking. (and +1, of course) $\endgroup$ – Rudy the Reindeer Apr 14 '13 at 15:11
4
$\begingroup$

Perhaps you'll find the following more to your liking. Let $S$ be a countable set and let $F$ be the set of all finite subsets of $S$. Let $E$ be the set of all finite sequences of elements of $S$. Clearly $|F|\le |E|$. Now, for each natural number $n$, let $E_n=S^n$ be the set of all sequences of $S$ of length $n$. Then $E=\bigcup _n E_n$. Now, a countable union of countable sets is countable, thus $E$ is countable, and thus also $F$ is countable.

Of course, this argument relies on the fact that a countable union of countable sets is countable and that for a countable set $S$, the sets $S^n$ are all countable, which have elegant proofs.

$\endgroup$
  • 2
    $\begingroup$ Why the detour through sequences? The set $S_n$ of all subsets of $[1, n]$ of $\mathbb{N}$ is finite, so $\bigcup_{n \in \mathbb{N}} S_n$ is a countable union of countable sets. $\endgroup$ – vonbrand Apr 14 '13 at 15:04
  • $\begingroup$ Yes, thank you, I like this one also better than my own proof. $\endgroup$ – Rudy the Reindeer Apr 14 '13 at 15:24
4
$\begingroup$

Let $A$ denote the set of all finite subsets of $\mathbb N$. Then

$$f: A \to \mathbb N \,;\, f(F)=\sum_{k \in F} 2^k \,$$

is a bijection.

Note: $f^{-1}$ identifies a non-negative integer with the possitions of $1's$ in its binary representation.

$\endgroup$
1
$\begingroup$

For $n$ in $\mathbb N$ let the tupel $(b^n_{\lfloor\text{ ld}(n)\rfloor},\dots,b^n_0)$ represent the binary expression of $n$, where we define $b^n_k=0$ for all $k>$ ld$(n)$. Then $f_n:\omega\to\{0,1\}$, $m\mapsto b^n_m$ defines a finite subset of $\omega$. This gives a bijection from $\mathbb N$ to the set of finite subsets of $\omega$.

$\endgroup$
  • $\begingroup$ I'm sorry for being slow: what is $\mathrm{ld}(n)$? $\endgroup$ – Rudy the Reindeer Apr 14 '13 at 15:13
  • 1
    $\begingroup$ @MattN. The logarithmus duālis, the binary logarithm, logarithm to the base 2. $\endgroup$ – Stefan Hamcke Apr 14 '13 at 15:18
1
$\begingroup$

A proof for finite subsets of $\mathbb{N}$:

For every $n \in \mathbb{N}$, there are finitely many finite sets $S \subseteq \mathbb{N}$ whose sum $\sum S = n$.

Then we can enumerate every finite set by enumerating all $n \in \mathbb{N}$ and then enumerating every (finitely many) set $S$ whose sum is $\sum S = n$.

Since every finite set has such an $n$, every finite set is enumerated. QED.

If you want the proof to hold for any countable $A$, first define any injective function $f: A \to \mathbb{N}$.

$\endgroup$
1
$\begingroup$

Let $\mathbb{N}$ include $0$.

Every finite subset of $\mathbb{N}$ can be represented uniquely as a binary string terminated by a $\mathtt{1}$. For example $\mathtt{1011}$ codes for $\{0,1,3\}$.

Then since every integer can be expressed uniquely in binary, we have a direct bijection between $\text{Fin}(\mathbb{N})$ and $\mathbb{N}$. In this case, the number $0$ corresponds to the empty set.

$\endgroup$
0
$\begingroup$

Let $n \in \mathbb{N}$. Note $n$ is finite.

Let $A_n \subseteq \mathbb{N}$ where $n = max(A_n)$.

Since $n$ is finite, $A_n$ is finite.

$\mid \mathcal{P}(A_n) \mid = 2^n$. Since $n$ is finite, $2^n$ is finite.

$\mathcal{F}(\mathbb{N}) = \bigcup_{n=1}^\infty \mathcal{P}(A_n)$

Since union of countable sets is countable and $\mathcal{F}(\mathbb{N})$ is such, it is countable.

$\endgroup$
  • $\begingroup$ And this differs from the accepted answer how? $\endgroup$ – Asaf Karagila May 12 '15 at 22:39
0
$\begingroup$

This answer community wiki. Please fee free to change it into an airtight argument.

To begin, please review the construction of the Cantor Pairing Function found here. The basic idea is that if we can totally order each finite set in a countable family, then the union of those sets is countable and comes equipped with a natural enumeration.

Let $X$ be a finite set with $n$ elements and assume you have a totally ordered $\mathcal{P}(X)$ (the power set) with $\le$. If you add a new element $\hat x$ to $X$, the number of subsets of $X \cup \{\hat x \}$ containing $\hat x$ is $2^n$, so you can copy $\le$ over to these new sets. Not only that, we can 'add' these $2^n$ subsets after $\mathcal{P}(X)$, giving a total ordering on $\mathcal{P}(X \cup \{\hat x\})$, a set with $2^n + 2^n = 2^{n+1}$ elements.

At a minimum for those seeking a mathematical framework, we have to explain how to copy $\le$ over when we add $\hat x$. We simple start by adding $\hat x$ to the $\le$ smallest element in the $\mathcal{P}(X)$ linear chain and then proceed adding it in to each of the following elements in turn.

It is kind of amusing that since there is only one ordering on a set with one element, and we start with $\mathcal{P}(\emptyset)$, there is not much work involved. Any bijective enumeration of $A$ drives the recursion.


Here is a partial listing:

Let $A$ be enumerated by $(a_n)_{ \, n \ge 1}$. We enumerate the finite subsets of $A$ as follows:

$\{\}$

$\{a_1\}$

$\{a_2\}$
$\{a_2,a_1\}$

$\{a_3\}$
$\{a_3,a_1\}$
$\{a_3,a_2\}$
$\{a_3,a_2,a_1\}$

$\{a_4\}$
$\{a_4,a_1\}$
$\{a_4,a_2\}$
$\{a_4,a_2,a_1\}$
$\{a_4,a_3\}$
$\{a_4,a_3,a_1\}$
$\{a_4,a_3,a_2\}$
$\{a_4,a_3,a_2,a_1\}$

$\{a_5\}$
$\{a_5,a_1\}$
$\{a_5,a_2\}$
$\{a_5,a_2,a_1\}$
$\{a_5,a_3\}$
$\{a_5,a_3,a_1\}$
$\{a_5,a_3,a_2\}$
$\{a_5,a_3,a_2,a_1\}$
$\{a_5,a_4\}$
$\{a_5,a_4,a_1\}$
$\{a_5,a_4,a_2\}$
$\{a_5,a_4,a_2,a_1\}$
$\{a_5,a_4,a_3\}$
$\{a_5,a_4,a_3,a_1\}$
$\{a_5,a_4,a_3,a_2\}$
$\{a_5,a_4,a_3,a_2,a_1\}$

$\{a_6\}$ $\{a_6,a_1\}$

$\{a_6,a_2\}$ $\{a_6,a_2,a_1\}$

$\{a_6,a_3\}$ $\{a_6,a_3,a_1\}$ $\{a_6,a_3,a_2\}$ $\{a_6,a_3,a_2,a_1\}$

$\{a_6,a_4\}$ $\{a_6,a_4,a_1\}$ $\{a_6,a_4,a_2\}$ $\{a_6,a_4,a_2,a_1\}$ $\{a_6,a_4,a_3\}$ $\{a_6,a_4,a_3,a_1\}$ $\{a_6,a_4,a_3,a_2\}$ $\{a_6,a_4,a_3,a_2,a_1\}$

$\{a_6,a_5\}$ $\{a_6,a_5,a_1\}$ $\{a_6,a_5,a_2\}$ $\{a_6,a_5,a_2,a_1\}$ $\{a_6,a_5,a_3\}$ $\{a_6,a_5,a_3,a_1\}$ $\{a_6,a_5,a_3,a_2\}$ $\{a_6,a_5,a_3,a_2,a_1\}$ $\{a_6,a_5,a_4\}$ $\{a_6,a_5,a_4,a_1\}$ $\{a_6,a_5,a_4,a_2\}$ $\{a_6,a_5,a_4,a_2,a_1\}$ $\{a_6,a_5,a_4,a_3\}$ $\{a_6,a_5,a_4,a_3,a_1\}$ $\{a_6,a_5,a_4,a_3,a_2\}$ $\{a_6,a_5,a_4,a_3,a_2,a_1\}$

Note: I started using a word processor for the last few steps...

$\endgroup$

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.