elementary set theory - Is the class of subsets of integers countably infinite?

I am trying to figure out if the class of subsets of integers is countably infinite or not. I know that a collection of all finite subsets of integers is countable. I believe i need to use diagonalization to prove whether it's true or not but I'm not sure how to approach it.

All Help is greatly appreciated!

Answer

No, the set of all subsets of the integer is not countable. Since $\mathbb{Z}$ has the same cardinality as $\mathbb{N}$, it suffice to consider all subsets of $\mathbb{N}$.

For each subset $X$ of $\mathbb{N}$ consider the characteristic function $\chi_X$ defined by

$\chi_X(z) = \begin{cases} 1 & \quad z \in X \\ 0 & \quad z \notin X \end{cases}$

In this way you associate injectively and subjectively each subset $X$ of $\mathbb{N}$ with a function in $2^{\mathbb{N}}$. $2^\mathbb{N}$ has cardinality strictly larger than $\mathbb{N}$. This is proved by the typical Cantor diagonalization argument.

Also, Cantor Diagonalization and the function I wrote above can be used to show more generally that the set of all subsets of a given set has cardinality strictly greater than the given set.

In response to comment :

You can think of a function from $\mathbb{N} \rightarrow 2$ a infinite binary strings of $0$'s and $1$'s. Assume that $2^{\mathbb{N}}$ is countable. That is there is a bijection $\sigma$ from $\mathbb{N}$ to $2^\mathbb{N}$. Then define the function $h : \mathbb{N} \rightarrow 2$ as follows

$h(n) = \begin{cases} 1 & \quad (\sigma(n))(n) = 0 \\ 0 & \quad (\sigma(n))(n) = 1 \end{cases}$

Informally, this is the familiar argument, form a new binary string by going down the diagonal and switching $0$ for $1$ and $1$ for $0$. Now this is a a perfectly good binary string hence it down appear as $\sigma(k)$ for some $k$ if $\sigma$ is indeed a bijection. However, it can not be $\sigma(k)$ for any $k$ since it differs from $\sigma(k)$ in at least the $k^\text{th}$ entry.

I hope this helps.