Let $S$ be the set of all infinite subsets of $\mathbb N$ such that $S$ consists only of even numbers.

Is $S$ countable or uncountable?

I know that set $F$ of all finite subsets of $\mathbb N$ is countable but from that I am not able to deduce that $S$ is uncountable since it looks hard to find a bijection between $S$ and $P(\mathbb N)\setminus F$. Also I am not finding the way at the moment to find any bijection between $S$ and $[0,1]$ to show that $S$ is uncountable nor I can find any bijection between $S$ and $\mathbb N$ or $S$ and $\mathbb Q$ to show that it is countable. So I am thinking is there some clever way to show what is the cardinality of $S$ by avoiding bijectivity arguments?

So can you help me?


Notice that by dividing by two, you get all infinite subsets of $\mathbb{N}$. Now to make a bijection from $]0,1]$ to this set, write real numbers in base two, and for each real, get the set of positions of $1$ in de binary expansion.

You have to write numbers of the form $\frac{n}{2^p}$ with infinitely many $1$ digits (they have two binary expansions, one finite, one infinite). Otherwise, the image of such a real by this application would not fall into the set of infinite sequences of integers (it would have only finitely many $1$).

  • $\begingroup$ Note that $0.01111\ldots_2 = 0.1_2$. Of course your argument can be easily fixed, but the function you describe is not a bijection. $\endgroup$ – dtldarek Mar 25 '13 at 14:02
  • $\begingroup$ That's exactly why I wrote one need to use the infinite expansion when there are two possible binary expansions. Why do you think it's not a bijection? $\endgroup$ – Jean-Claude Arbaut Mar 25 '13 at 14:04
  • $\begingroup$ You are right, I should refresh my browser more often (sometimes AJAX does not work). $\endgroup$ – dtldarek Mar 25 '13 at 14:06
  • $\begingroup$ But you are right, I had to include 1 in the interval, to take care of image of $\mathbb{N}$. Now I think everything is fixed. $\endgroup$ – Jean-Claude Arbaut Mar 25 '13 at 14:08
  • $\begingroup$ Thank you, it surely looks good! $\endgroup$ – user67878 Mar 25 '13 at 14:08

The set of even numbers is countably infinite, and so equinumerous to $\Bbb N$ (explicit bijection given by $n\mapsto\frac12n$). With $F$ the set of finite subsets of $\Bbb N$, as you say, we can use the map $f(n)=\frac12n$ to get a bijection $g:S\to P(\Bbb N)\setminus F$, given by $$g(A)=\{f(n):n\in A\}.$$ I leave it to you to prove that it's bijective.

  • $\begingroup$ So, if I understood your argument well, it is the case that if there is a bijection between $A$ and $B$ then there is a bijection between $R$ and $S$ where $R$ is the set of all infinite subsets of $A$ and $S$ is the set of all infinite subsets of $B$? $\endgroup$ – user67878 Mar 25 '13 at 13:57
  • $\begingroup$ Absolutely right, and you can prove that as a general statement using the same idea that I outlined above. $\endgroup$ – Cameron Buie Mar 25 '13 at 13:59
  • $\begingroup$ Do you mean by the "general statement" that it works for every cardinality of $A$ and $B$ if we precisely enough define cardinality of $R$ and $S$, which is not needed in my case because every infinite subset in my problem must be of countable infinity? $\endgroup$ – user67878 Mar 25 '13 at 14:05
  • $\begingroup$ What a flaw by me! It is fairly "obvious" what is the set of all infinite subsets of some set so in my previous comment maybe it is better to put away the word "precise". And you already answered that it is possible so it looks like I am asking the same question as in the first comment. It was a wave of confusion few minutes ago so it is clearer now for me to see it should work for every cardinality. Thank you! $\endgroup$ – user67878 Mar 25 '13 at 14:14
  • 1
    $\begingroup$ So, if I ask you what approach would you choose for yourself, a set theory in which that statement is true, or set theory in which that statement is not true, what would you choose? You can choose it without an axiom of choice! ;.D $\endgroup$ – user67878 Mar 27 '13 at 19:44

Use the Cantor-Bernstein theorem, that is (in the simplified version)

$$|A| \leq |B| \text{ and } |B| \leq |A| \text{ implies } |A| = |B|.$$

We have that $S \subset P(\mathbb{N})$, so $|S| \leq |P(\mathbb{N})|$. Moreover, we have an injection $f : P(\mathbb{N}) \to S$ given by

$$ f(A) = \{4k \mid k \in A\} \cup \{4k+2 \mid k \in \mathbb{N}\}. $$

Hence, we have $|P(\mathbb{N})| \leq |S|$, so $|S| = |P(\mathbb{N})|$.

I hope this helps ;-)

  • $\begingroup$ Yes, you all got +1 for the effort! $\endgroup$ – user67878 Mar 25 '13 at 14:02
  • $\begingroup$ @Thus As there might be many solutions, it would be still of benefit to you to know the Cantor-Bernstein theorem. Sometimes bijections are troublesome to construct (see, e.g. bijection between $P(\mathbb{N})$ and $\mathbb{R}$), while usually there is a much more simple way to construct two injections. $\endgroup$ – dtldarek Mar 25 '13 at 14:14
  • $\begingroup$ I know about the theorem but didn´t look in that direction that it could be easier to construct two injections instead of one bijection, not because of $1<2$ :-D $\endgroup$ – user67878 Mar 25 '13 at 14:21

Hint: If $\{x_n\mid n\in\Bbb N\}$ is a set of even integers then $\{\frac{x_n}2\mid n\in\Bbb N\}$ is a sequence of integers. Show that this operation is in fact a bijection between $S$ and the set of all infinite subsets of integers. The latter is more familiar.

  • $\begingroup$ Thank you! I have a question that I can put in a comment and I believe that you could solve it, do you want of me to ask you? $\endgroup$ – user67878 Mar 25 '13 at 14:28
  • $\begingroup$ If it is related, sure. $\endgroup$ – Asaf Karagila Mar 25 '13 at 14:29
  • $\begingroup$ I will answer it too, I just want of you to confirm is my line of reasoning correct. Let $S$ be the set of all subsets of $\mathbb N$ such that every set that belongs to $S$ consists only of numbers that are pairwise coprime (relatively prime). So I was thinking of this. The set of all prime numbers $P$ is in $S$ and it is infinite. Because the $P$ is infinite and every infinite subset of $P$ is also obviously consisted of coprime numbers then $S$ is uncountable because the $P$ is countable so it has uncountable number of countable subsets. Is this good reasoning? $\endgroup$ – user67878 Mar 25 '13 at 14:43
  • $\begingroup$ If it is then I understood your arguments for the question I asked. $\endgroup$ – user67878 Mar 25 '13 at 14:43
  • $\begingroup$ Yes, it is an excellent reasoning. $\endgroup$ – Asaf Karagila Mar 25 '13 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy