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 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 its true or not but im not sure how to approach it.

All Help is greatly appreciated!

Thanks

share|improve this question
4  
For any particular subset, any particular integer is either in the subset or not in the subset. –  user13456 Sep 4 '11 at 23:46
    
I would suggest adding the tag "Set Theory". –  William Sep 4 '11 at 23:49
5  
@William: The set theory tag is for "for set theory topics typically studied at the advanced undergraduate or graduate level." Thus, I added the (elementary-set-theory) tag instead. –  t.b. Sep 5 '11 at 0:01

4 Answers 4

up vote 11 down vote accepted

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.

share|improve this answer
1  
Thank You For Your Response! I was wondering, How can i use Cantor's Diagonalization to prove this? –  Jeff Sep 4 '11 at 23:55
    
I provided a brief sketch of diagonalization argument for proving $2^\mathbb{N}$ is not countable. I hope that was what you were asking. –  William Sep 5 '11 at 0:05

It is not. For any family $\mathscr A=(A_x)$ of subsets of a given set $X$, indexed by $x$ in $X$, consider the subset $B$ of $X$ defined as follows: $B$ is the set of elements $x$ of $X$ such that $x\notin A_x$. Then $B$ cannot be any of the sets $A_x$, hence any family $\mathscr A$ indexed by $X$ cannot contain every subset of $X$.

This argument is called Cantor's diagonal argument (where diagonal refers to the diagonal of a hypothetical array whose lines would be indexed by $X$ and columns would be indexed by $\mathscr A$). It shows that the set of all subsets of $X$ has cardinality greater than $X$, for any set $X$.

share|improve this answer

Edit. I rewrote this answer since there was a small, but significant, inaccuracy in my earlier hint. Thanks to GEdgar for pointing out the error, and to both GEdgar and Henning Makholm for suggestions for fixes.

First, note that William Chan demonstrates a bijection from the power set of $\mathbb N$ to the set of infinitely long $0$-$1$ strings (call1 this set $Z$). This is nothing but the map sending $S \subseteq \mathbb N$ to its characteristic vector (function).

Now, given an infinite $0$-$1$ string, we can transform it to a real number by placing a binary point in the beginning, and interpretting it as a binary expansion of a real number; this number will clearly lie in $[0,1]$. (If this seems too informal, see leo's answer for a formal definition.) So we have a map from $Z$ to the reals in $[0,1]$.

This map is certainly not injective, since $0.00111\ldots_{2}$ and $0.01000\ldots_{2}$ represent the same real number. (This was, in fact, the error in the previous hint.) However, it is surjective, basically because all real numbers (in $[0,1]$) have a binary expansion (with nothing before the binary point). And we only need surjectivity for this idea to go through.

Now, since $[0,1]$ is uncountable, can you see that $Z$ is also uncountable? What can you then conclude about the cardinality of $2^{\mathbb N}$? For the first part, you will need the fact that there exists no surjective mapping from a countable set to an uncountable set.

1Edit. Per Zhen Lin's comment, I changed $\lbrace 0,1 \rbrace^\omega$ to $\lbrace 0,1 \rbrace^{\mathbb N}$. I decided to call this set simply $Z$, instead of $\lbrace 0,1 \rbrace^{\omega}$ or $\lbrace 0,1 \rbrace^{\mathbb N}$. See the comments below. Thanks to Asaf for the clarification anyway.

share|improve this answer
    
Unfortunately, this correspondence has a few bad points, where two different 0-1 strings correspond to the same real. –  GEdgar Sep 5 '11 at 3:00
    
You could note that there are only countably many numbers it fails to be one-to-one for, and then do some Hilbert-holtel-esque shuffling to make them all fit anyway. –  Henning Makholm Sep 5 '11 at 4:05
    
@Henning Thank you for your suggestion. I'll think about how to do this correctly. –  Srivatsan Sep 5 '11 at 4:13
    
Instead of writing down an explicit bijection (Henning suggests how to do that), it is probably better to rely on Schroeder-Bernstein, and write down two explicit injections, one in each direction. –  GEdgar Sep 5 '11 at 12:30
    
@Gedgar Turns out that there's a simple fix after all :). Thanks again for your help. –  Srivatsan Sep 6 '11 at 14:29

The answer is no. I think the best way to see this is the @Didier Piau's answer. Now, to another, the problem can be reduced to show that the class of subsets of natural numbers is no countable, as William Chan say. I'll show that class of infinite subsets of natural numbers is not numerable. This is just a little change of the Srivatsan's argument.

We say that a set $A$ is numerable, if is equipotent to the set $\mathbb{N}$ of natural numbers. We say that $A$ is countable, if is finite or numerable.

Lemma. If $A\subseteq B$ and $B$ countable, then $A$ is countable.

Now, consider the class of infinite subsets of natural numbers $\mathfrak{I}$. Define $\psi:\mathfrak{I}\to ]0,1]$ by $$\psi(A)=\sum_{n\in \mathbb{N}}\frac{\chi_A(n)}{2^n},$$ where $\chi$ is as in the William Chan's answer. The function $\psi$ is well defined because of the uniqueness of the infinite expansion in base $2$ of the numbers in $]0,1]$. Since a infinite string of 0-1s (that is not always $0$ from a moment) corresponds to a infinite subset of $\mathbb{N}$, $\psi$ is a bijection and therefore since $]0,1]$ isn't numerable, we conclude that $\mathfrak{I}$ is not numerable. Then by the lemma the class of subsets of $\mathbb{N}$ isn't countable.

share|improve this answer
    
Ah, that was a clever way to get around the issue :) . –  Srivatsan Sep 5 '11 at 6:38
    
Thanks @Srivatsan –  leo Sep 5 '11 at 6:39

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.