Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

8 Answers 8

up vote 17 down vote accepted

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

share|improve this answer
    
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. –  Matt N. Apr 14 '13 at 15:19

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

share|improve this answer
    
never saw this proof before :) (+1) –  Ittay Weiss Apr 14 '13 at 14:58
6  
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! –  Peter Smith Apr 14 '13 at 15:14
    
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. –  Clive Newstead Apr 14 '13 at 15:21

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.

share|improve this answer

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.

share|improve this answer
    
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 : ) –  Matt N. Apr 14 '13 at 15:10
    
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) –  Matt N. Apr 14 '13 at 15:11

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.

share|improve this answer
2  
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. –  vonbrand Apr 14 '13 at 15:04
    
Yes, thank you, I like this one also better than my own proof. –  Matt N. Apr 14 '13 at 15:24

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.

share|improve this answer

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

share|improve this answer
    
I'm sorry for being slow: what is $\mathrm{ld}(n)$? –  Matt N. Apr 14 '13 at 15:13
1  
@MattN. The logarithmus duālis, the binary logarithm, logarithm to the base 2. –  Stefan Hamcke Apr 14 '13 at 15:18

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.