Cardinal arithmetic argument for countability of finite subsets of integers.

Question

I am trying to prove that the set of all finite subsets of $\mathbb{Z}$ is countable. I proved that the set of all infinite sequences of $\mathbb{Z}$ is uncountable, simply by using a bit of cardinal arithmetic.

I'm familiar with the usual proof for my problem - indicating a bijection between finite subsets of $\mathbb{Z}$ and $\mathbb{N}$, and then using some inductive argument to show that the finite subsets of the naturals are countable.... that's all good. But I was curious as to whether there is a more direct approach with cardinal arithmetic.

I was playing around with taking the union of all of the possible finite subsets of the integers and attempting to find the cardinality of that set (and felt like I was on to something), but have had a hard time actually formulating the result. Does this seem like a reasonable approach, and if not are there any other proof mechanisms for this problem?

Answer 1

Let $S$ be the set of all finite subsets of $\mathbb{Z}.$ Here's an explicit bijection $i$ mapping $S$ to $\mathbb{N}\!:$

$$i(A)=\sum_{\substack{n\in A\\n\ge 0}}4^{n}+\frac12\sum_{\substack{n\in A\\n\lt 0}}4^{-n}.$$

An empty sum here is equal to $0,$ as usual.

I'm taking $\mathbb{N}$ to mean $\lbrace 0, 1, 2, \dots\rbrace.$ If you don't want to count $0$ as a member of $\mathbb{N},$ add $1$ to the formula.

It's a good exercise to see why this works. (Hint: it uses binary representation of natural numbers.)

Answer 2

Z and N have the same cardinality.So we need to prove that the set of all finite subsets of N is countable.Given any natural number n consider the set {1,2,....,n}.This set has 2^n number of subsets.Let An be the set of all subsets of {1,2,...,n}.Therefore An is finite for each n belonging to the set of natural numbers.Now take the union of all An's. Now the union is countable union of finite sets so it will be countable.Now if B is any finite subset of N then B belongs to the union.Hence the proof.