Could someone verify my proofs?

Proposition: the set of all finite subsets of $\mathbb{N}$ is countable

Proof 1:

Define a set $ X=\{A\subseteq\mathbb{N}\mid \text{$A$ is finite} \}$.

We can have a function $g_{n}: \mathbb{N} \rightarrow A_{n} $ for each subset such that that function is surjective (by the fundamental theorem of arithmetic). Hence each subset $A_{n}$ is countable.

By the "Union of countable sets is countable" theorem, X is countable.

Q. E. D.

Proof 2: Suppose we have an ordered list of prime numbers $p_{1}, p_{2}, ..., p_{n}$. Define a function $g: X \rightarrow \mathbb{N}$ such that $ g(A) = (p_{1})^{a_{1}}*(p_{2})^{a_{2}}*...*(p_{k})^{a_{k}} $ with $k=$ number of elements of each subset and $ a_{1}, a_{2}, ..., a{k} $ the ordered elements of them. By the fundamental theorem of arithmetic, that function is injective, hence $X$ is countable.

Q. E. D.

  • 2
    $\begingroup$ You proved $X=\bigcup A_n = \Bbb N$ is countable, not the set of finite subsets of $\Bbb N$. $\endgroup$ – Quang Hoang Aug 25 '14 at 0:53
  • 2
    $\begingroup$ In place of $A_n$, it seems to me that you want to consider the set of all subsets of $\mathbb N$ of size $n$. $\endgroup$ – vociferous_rutabaga Aug 25 '14 at 0:54
  • $\begingroup$ Then is there a problem with my definition? I've thought I'd defined the set X as the set of all finite subsets of the natural numbers. $\endgroup$ – Guilherme Duarte Aug 25 '14 at 0:55
  • 2
    $\begingroup$ The problem with your definition is that you are indexing the finite subsets of $X$ using $\mathbb{N}$, which pre-supposes that $X$ is countable. It's like saying that $[0,1]=\{x_n\}$ where $x_n \in [0,1]$, so $[0,1]$ is countable. $\endgroup$ – angryavian Aug 25 '14 at 0:57
  • 2
    $\begingroup$ You need to find a single function $\mathbb N\to X$. You can't find $g_n:\mathbb N\to A_n$, because you haven't defined $A_n$ yet. $\endgroup$ – Thomas Andrews Aug 25 '14 at 1:02

What you have is nowhere near a proof. The definition of $X$ can be accepted, but it is not conveying any insight transgressing the verbal formulation of the problem.

We have to construct a bijective map $$f:\quad {\mathbb N}_{\geq0}\to X,\qquad n\mapsto A_n\ .\tag{1}$$ This map produces for each $n\in{\mathbb N}$ a finite set $A_n\in X$, and each element $A\in X$ is produced exactly once.

(Depending on the theorems of elementary set theory that are available at this point one could make do with a surjective $g:\ {\mathbb N}_{\geq0}\to X$, or an injective $h:\ X\to{\mathbb N}_{\geq0}$.)

There are various examples of such $f$'s around. The simplest that comes to mind is the following: Any set $A\subset{\mathbb N}_{\geq0}$ can be encoded as a bit string ${\bf b}_A:=(b_0,b_1,b_2,\ldots)$ by putting $b_k:=1$ when $k\in A$ and $b_k=0$ otherwise. When $A\in X$ this string has only finitely many ones. Now put $$\hat f(A):=\sum_{k=0}^\infty b_k2^k\qquad(A\in X)\ .$$ This means that we interpret ${\bf b}_A$ as binary expansion of a certain nonnegative integer. The $\hat f$ defined in this way is the inverse of a function considered in $(1)$.

  • $\begingroup$ If X was not constrained to having only finitely many ones, how would this proof not work anymore? (If this proof still works then it would violate Cantor's theorem.) $\endgroup$ – Bernard Jan 30 '19 at 15:10
  • 1
    $\begingroup$ @Bernard: If $A\subset{\mathbb N}$ has infinitely many elements then the number $\sum_{k=0}^\infty b_k2^k$ is not defined for ${\bf b}_A$. $\endgroup$ – Christian Blatter Jan 31 '19 at 7:58
  • $\begingroup$ what I don't get is since we encode a set of length k for example as a bit string $(b_0,b_1,..)$ and natural numbers are infinite ( but countable) in order to decide on which elements are going to be included we may have to examine natural numbers forever? ( or because we consider them countable this process of examining each time every natural number untill we have k "1"'s is considered finite ?) $\endgroup$ – brucebanner Sep 1 '20 at 18:31
  • $\begingroup$ @brucebanner: For each finite set $A\subset{\mathbb N}$ we obtain a number $\hat f(A)\in{\mathbb N}$, and conversely: Any number $j\in{\mathbb N}$ can be "retranslated" into its corresponding finite set $A\subset{\mathbb N}$ by expressing $j$ as "binary decimal". For these processes there are only "finitary" computations at work. $\endgroup$ – Christian Blatter Sep 1 '20 at 18:51

Comments on your proof.

Define a set $ X=\{A\subseteq\mathbb{N}\mid \text{$A$ is finite} \}$. OK

We can have a function $g_{n}: \mathbb{N} \rightarrow A_{n} $ << Problem: You have to define $A_n$

Say you wanted to say, $A_n$ is a finite subset of $\mathbb{N}$ defined by: $$A_n = \{n_1,n_2,... | ~ n_i \text{ occurs as exponent in } n = p_1^{n_1} p_2^{n_2} ... \}$$ then a better notation is to use

$g:\mathbb{N} \rightarrow X$ where $g(n) = A_n$ where $A_n ... \text{*as above*}$

Then you would say "By the fundamental theorem of arithmetic, each $A_n$ is finite and $g$ is surjective."

With the above clarifications, your remark "By the 'Union of countable sets is countable' theorem, X is countable" does not help.

You would invoke instead the following argument:

"Likewise, it is easy to find $h:X \rightarrow \mathbb{N}$, a surjective function too, for example $h(A) = min(A)$.

And as we have a surjective function in both directions, they have the same cardinality."

  • $\begingroup$ what does min(A) denote? $\endgroup$ – Daschin Jun 7 '17 at 3:58

As others have remarked, you seem to already assume that the set you want to be countable is countable by the way you label the finite sets. However, you can "lexicographically order" the finite sets of natural numbers in many ways, for example the following: If $A$ and $B$ are finite sets of natural numbers, say that $A <B$ if $|A| < |B|$. If $A$ and $B$ are different subsets of $\mathbb{N}$ of the same cardinality, define $A <B$ if the smallest element if $B$ is less than the smallest element of $B$. If $|A| = |B|$ and $k >0$ and the $k$ smallest elements of $A$ coincide with the $k$ smallest elements of $B$, but the $k+1$-st smallest element of $A$ is less than the $k+1$-st smallest element of $B$, say that $A <B.$ this allows you to list the subsets of $\mathbb{N}$ in a strictly increasing order, and shows that there are countably many such sets. ( For each $n,$ there are countably many subsets of cardinality $n$, so the theorem you want to use does indeed apply here).


But the union of an *un*countable number of countable subsets need not be countable; think of the union of the singleton elements of $R$; so you need to have shown that $X$ is countable at this step - but that's what you're trying to prove.

The only evidence I see that there are a countable number of elements in X is your notation $A_n$. Usually with this notation, we mean it goes without saying that $n$ is in $N$ and that there is an implicit injective function $f : X \rightarrow N$.

But that again assumes what you already want to prove: that $X$ is countable.

Obviously, nobody would be asking you to prove that $X$ is countable if it weren't countable (well, actually, I've encountered a number of mistakes in textbook mathematical questions, so actually that isn't always true). But you always need to be careful that you aren't somehow assuming what you want to prove.

As a hint, think of the function f:

$f(A) = \sum_{a \in A} 3^a$

So, first off we must make sure - is $f(A)$ well-defined for all $A \in X$? It sure wouldn't be for all $A \in P(N)$!

Next, is $f$ in bijection with a subset of $N$ (in particular, does $f(A')=f(A'')$ if and only if $A'=A''$)?

Can we say "Q.E.D" now? What is the definition of "$X$ is countable"?

  • $\begingroup$ And if I call $A_{n}$ all subsets of $\mathbb{N}$ with n elements. Then, we would have X as a Union of all A_{n}. $\endgroup$ – Guilherme Duarte Aug 25 '14 at 2:49
  • $\begingroup$ @GuilhermeD Sure, that would be a legal definition. Then the question turns to: since the quoted justification is "a countable union of countable sets is countable", what's your proof that $A_n$ is countable? Because there are clearly more than a finite number of elements in $A_n$, especially when $n$ is large :)! $\endgroup$ – Chas Brown Aug 25 '14 at 3:03
  • $\begingroup$ I re-elaborated the proof: Suppose we have an ordered list of prime numbers $p_{1}, p_{2}, ..., p_{n}$. Define a function $g: X \rightarrow \mathbb{N} $ such that $g = (p_{1})^{a_{1}}*(p_{2})^{a_{2}}*...*(p_{k})^{a_{k}}$ with $ k = \text{number of elements of each subset} $ and $ a_{1}, a_{2}, ..., a{k}$ the ordered elements of them. By the fundamental theorem of arithmetic, that function is injective, hence X is countable. Is that correct? $\endgroup$ – Guilherme Duarte Aug 25 '14 at 3:30
  • $\begingroup$ That's the ticket; although I suggest as a learning aid you really go through the tedious steps to show that FTA proves this. One thing I wanted to point out in problems like this is that there is a temptation to get fancy and try to find a bijection with $N$; but it's really not needed. There are "just as many" even naturals as naturals which are perfect squares; and sometimes it's easier to show that some set is isomorphic (in whatever context) with a "sparser" subset of the original question than one might initially think. $\endgroup$ – Chas Brown Aug 25 '14 at 3:44
  • $\begingroup$ So is my second proof correct? Thanks... $\endgroup$ – Guilherme Duarte Aug 25 '14 at 3:47

Here's a thought:

For $i\in\mathbb{N}$ let $B_i=\{S\subseteq\mathbb{N}\mid \sum_{x\in S}x=i\}$

  • 3
    $\begingroup$ His question starts: "Could someone verify my proof?" Have you done this for the OP? $\endgroup$ – Thomas Andrews Aug 25 '14 at 1:05

I understood that you want to use the fact that countable union of countable sets is countable. Do the following.

Let $X$ be a set of all finite subsets of $\mathbb{Z}_{+}$ and $X_{n}$ be the set of all subsets of cardinality n of the natural numbers.

Define $f_n:\mathbb{Z}_{+}^{n} \longrightarrow X_n$ s.t. each tuple is mapped to a set having the same elements as the ones in the tuple.

It is clear that this function is surjective. Now we know there is a surjective function from $\mathbb{Z}_{+}$ to $\mathbb{Z}_{+}^{n}$. Therefore, $X_n$ is countable.

Now $X$ is the union of $X_n$ so you have the result from the fact that you wanted to use, ie countable union of countable sets is countable.


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