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?
Best Answer
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.)