13
$\begingroup$

How many subsets of $\mathbb{N}$ have the same cardinality as $\mathbb{N}$?

I realize that any of the class of functions $f:x\to (n\cdot x)$ gives a bijection between $\mathbb{N}$ and the subset of $\mathbb{N}$ whose members equal multiples of n. So, we have at least a countable infinity of sets which have the same cardinality of $\mathbb{N}$. But, we could remove a single element from any countably infinity subset of the natural numbers and we still will end up with a countably infinite subset of $\mathbb{N}$. So (the reasoning here doesn't seem quite right to me), do there exist uncountably many infinite subsets of $\mathbb{N}$ with the same cardinality of $\mathbb{N}$?

Also, is the class of all bijections $f: \mathbb{N} \to \mathbb{N}$ and a given countably infinite subset uncountably infinite or countably infinite?

  • 0
    Just touched up the formatting a tad, Doug. Nice question.2012-12-22

5 Answers 5

22

One can write a bijection between $\mathrm{Fin}(\mathbb N)$ and $\mathbb N$, i.e. between the set of finite subsets of $\mathbb N$ and $\mathbb N$. For example: $$f(A)=\sum_{i\in A}2^i$$

Note that $A$ is finite so this is a well-defined function. It turns out that this is a bijection as well.

Then one can show that $\mathcal P(\mathbb N)\setminus\mathrm{Fin}(\mathbb N)$ is uncountable, and in fact equipotent to $\mathcal P(\mathbb N)$. This is because $k+\aleph_0=2^{\aleph_0}$ implies that $k=2^{\aleph_0}$. So if $k=|\mathcal P(\mathbb N)\setminus\mathrm{Fin}(\mathbb N)|$ then $k=2^{\aleph_0}=|\mathcal P(\mathbb N)|$.


To the second question, one can show that there are $2^{\aleph_0}$ permutations of $\mathbb N$. Therefore if $f\colon A\to\mathbb N$ is a bijection composing it with a permutation of $\mathbb N$ will result in another bijection. It is not hard to show that if we compose different permutations we have different bijections (i.e. they disagree on the value of some point in $A$). Therefore there are $2^{\aleph_0}$ many bijections between any two countable sets.

(I should also remarked that none of the points in this answer requires the axiom of choice.)

  • 0
    I don't understand the capital Greek sigma here. It's not a summation symbol, but instead a union... correct? Does f(A) equal a unionization of power sets? Also, how do you define A?2012-12-22
  • 1
    @DougSpoonwood: No, it's summation. $A$ is a set of natural numbers.2012-12-22
  • 2
    @DougSpoonwood: The map $f$ takes a finite set $A \subset \mathbb{N}$ and outputs an element of $\mathbb{N}$. For example $$f\left(\{1,2,5,11\}\right) = 2^1 + 2^2 + 2^5 + 2^{11} = 2086.$$2012-12-22
  • 0
    Just to make sure, $\aleph_0$ means the cardinality of the natural numbers, and $2^{\aleph_0}$ means the cardinality of the power set of the natural numbers, correct?2012-12-24
  • 1
    @Doug: Correct.2012-12-24
  • 0
    Let InFin($\mathbb N$) denote the infinite subsets of $\mathbb N$. One might then write |$\mathbb N$|=|InFin($\mathbb N$) U Fin($\mathbb N$)|=(|InFin($\mathbb N$)|+|Fin($\mathbb N$))|=(k+$\aleph_0$)=$2^{\aleph_0}$. That said, Asaf's excellent answer emphasizes disjointedness of the sets here which we need here anyways.2012-12-24
  • 1
    @Doug: Minor correction to your comment, it should be $|\mathcal P(\mathbb N)|$ and not $|\mathbb N|$ there.2012-12-24
  • 0
    @AsafKaragila Whoops!2012-12-25
  • 0
    Say we have an algebra with a set of axioms which a binary operation under the natural numbers satisfy, like say the natural numbers as a commutative monoid. Does the above consequently imply as a corollary that there exists $2^{\aleph_0}$ isomorphic algebras which have a subset of the natural numbers as their set?2013-01-01
  • 0
    @Doug: I don't understand the question.2013-01-01
  • 0
    @AsafKaragila Sorry. As an example, consider the natural numbers under addition, which forms a commutative monoid. The above indicates there exists $2^{\aleph_0}$ of the class of subsets S of $\mathbb N$ for which there exists a bijection from $\mathbb N$ to s, a member of S. Now consider the class of algebras which have their carrier set from S, and have a single binary operation. Does the above imply that there exist $2^{\aleph_0}$ algebras isomorphic with the natural numbers under addition (or more generally, some arbitrary operation... or set of operations)?2013-01-01
  • 2
    @Doug: If you don't require the operation to be the usual addition restricted to the set, then the answer is trivially yes. Take any permutation of $\mathbb N$, and there are $2^{\aleph_0}$ of them, and it defines a "new" operation on $\mathbb N$. In fact take any infinite subset of $\mathbb N$, and a bijection would have the same effect. So yes, there are $2^{\aleph_0}$ subsets which are isomorphic to $\mathbb N$ with the usual addition; and each of them has $2^{\aleph_0}$ operations which are isomorphic to the addition.2013-01-01
  • 0
    Since the integers biject with the natural numbers, and the composition of two bijections gives us a bijection, an upshot of this comes as that we have $2^{\aleph_0}$ groups, rings, and other structures of subsets of natural numbers.2013-01-06
  • 2
    @Doug: Indeed so. Also the rationals, as well the algebraic closure of the rationals. All countable.2013-01-06
  • 0
    @AsafKaragila - The implicit assertion that every member of $\mathcal P(\mathbb N)\setminus\textrm{Fin}(\mathbb N)$ has the same cardinality as $\mathbb N$ assumes that every infinite set is Dedkind infinite. Couldn't you touch this up so that it holds in, say, Cohen's first model? I accept that that's a slightly pedantic thing to do, but it's a shame to have the proof valid only in **most** models of set theory.2013-09-18
  • 1
    @Donkey: It most certainly does not! Every member of $\mathcal P(\Bbb N)$ is a subset of the natural numbers. Therefore you can enumerate it using natural numbers. In particular if it's infinite it has to have the same cardinality of the natural numbers. Cohen's first model adds an infinite Dedekind-finite **subsets** of $\mathcal P(\Bbb N)$, which is a whole other thing.2013-09-18
  • 0
    @Asaf - sorry, that was really silly of me. I take it all back ;-)2013-09-18
9

$\Bbb N$ has only countably many finite subsets, but it has uncountably many subsets altogether, so it must have uncountably many countably infinite subsets (i.e., subsets with the same cardinality as $\Bbb N$ itself).

If $A$ is any countably infinite set, there are uncountably many bijections between $\Bbb N$ and $A$.

  • 0
    I don't see how $\mathbb{N}$ has countably many finite subsets. How do you get that?2012-12-22
  • 0
    @DougSpoonwood: see Asaf's answer for an explanation.2012-12-22
5

Some more answers:

There are uncountably many sets of odd numbers, and adjoining the even numbers to each of these yields a set with the same cardinality as $\mathbb N$.

Given any real number $x$, we can form the set $S(x)=\{\lfloor x \rfloor,\lfloor 10x \rfloor,\lfloor 100x\rfloor,\dots\}$ (e.g., $S(\pi)=\{3,31,314,3141,31415,\dots\}$), which clearly has the same cardinality as $\mathbb N$, and the map $S$ is a bijection, so this process yields uncountably many sets.

(Really the same as the last one) Given any infinite sequence $(a_n)$ of natural numbers, we can form the set $\{2^{a_1},3^{a_2},5^{a_3},\dots\}$ which has the same cardinality as $\mathbb N$.

1

As great answers have been given already, I'd merely like to add an easy way to show that the set of finite subsets of $\mathbb{N}$ is countable:

Observe that $$\operatorname{Fin}(\mathbb{N}) = \bigcup_{n\in\mathbb{N}}\left\{ A\subseteq\mathbb{N}: \max(A) = n \right\},$$ which is a countable union of finite sets as for each $n\in\mathbb{N}$ there certainly are less than $2^n = \left|\mathcal{P}(\{1,\ldots,n \})\right|$ subsets of $\mathbb{N}$ whose largest element is $n$. Hence, $\operatorname{Fin}(\mathbb{N})$ is countable itself.

From here on, you can use Asaf's argument to show that the set of infinite subsets of $\mathbb{N}$ (which are precisely the sets with the same cardinality as $\mathbb{N}$) must be uncountable.

1

Here is a simple explicit bijection from $\mathcal P(\mathbb N)$ to $\mathcal P(\mathbb N)\setminus \operatorname{Fin}(\mathbb N)$:

$$ f(A) = \begin{cases} \{ n+1 \mid n\in A \} & \text{if $A$ is cofinite} \\ \mathbb N \setminus \{ n+1 \mid n\in A \} & \text{if $A$ is finite} \\ A & \text{if $A$ is neither finite nor cofinite} \end{cases} $$

($A$ is said to be cofinite iff $\mathbb N\setminus A$ is finite).