You can find encodings in the natural numbers of certain collections of subsets of $\mathbb{N}$. For example, as was pointed out by Henning Makholm, there is a very nice encoding of the collection of finite subsets of $\mathbb{N}$.
More generally, let $A$ be a recursively enumerable subset of $\mathbb{N}$. Let $T_A$ be a Turing machine that, on input $n$, halts if $n\in A$, and does not halt otherwise. Then we can encode $A$ by using the usual index of the machine $T_A$.
This encoding is not fully satisfactory. There are infinitely many Turing machines that halt on input $n$ iff $n\in A$. Thus every recursively enumerable set has infinitely many encodings. Moreover, there is no algorithm for telling, given two natural numbers, whether they encode the same set.
For more modest collections than the collection of recursively enumerable sets, there are far more satisfactory encodings. As a small and not very interesting example, consider the collection of subsets of $\mathbb{N}$ that are either finite or cofinite (their complement is finite). A small modification of the encoding of finite subsets will take care of the finites and cofinites. Basically, just use the even natural numbers for the finites. If you have used $2k$ to encode a finite, use $2k+1$ to encode its complement.
In addition, the elements of any countably infinite subset of the power set of $\mathbb{N}$ can, by the definition of countably infinite, be encoded using the natural numbers. However, by cardinality considerations, we cannot encode all the subsets of $\mathbb{N}$ using elements of $\mathbb{N}$.
The first thing you need to ask yourself, about finite sets, is this: When do two sets have the same cardinality?
The way mathematics works is to take a property that we know very well, and do our best to extract its abstract properties to describe some sort of general construct which applies in as many cases as possible.
So how do we compare the sizes of two finite sets? If we can write a table, in one column the set $A$ and in the other the set $B$, and each element from $A$ appears in a unique cell; and each element of $B$ appears in a unique cell. If this table have no rows in which there is only one element, then the sets $A$ and $B$ are equal. For example:
$$\begin{array}{lc}
\text{Two equal sets:} &
\begin{array}{c|c|c}A & a_1& a_2\\\hline B & b_1& b_2\end{array} \\
\text{Non-equal sets:} &
\begin{array}{c|c|c|c}A & a_1 & a_2 & a_3\\\hline
B & b_1 & b_2\end{array} &
\end{array}$$
It is clear that this methods captures exactly when two sets have the same size. We don't require one set to be the subset of another; nor we require that they share the same elements. We only require that such table can be constructed.
Well, the generalization is simply to say that there exists a function from $A$ to $B$ which is injective and surjective, namely every element of $A$ has a unique element of $B$ attached to it; and every element of $B$ has a unique element of $A$ attached to it.
It turns out, however, that this notion has a quirky little thing about infinite sets: infinite sets can have proper subsets with the same cardinalities.
Why is this happening? Well, infinity is quite the strange beast. It goes on without an end, and it allows us to "move around" and shift things in a very nice way. For example consider the following table:
$$\begin{array}{c|c|c|c|c|c}
\mathbb N&0&1&\cdots&n&\cdots\\\hline
\mathbb N\setminus\{0\}& 1&2&\cdots & n+1&\cdots
\end{array}$$
It is not hard to see that this table has no incomplete rows and that every element of the left set ($\mathbb N$) appears exactly once, and every element of the right set ($\mathbb N\setminus\{0\}$) appears exactly once!
This can get infinitely more complicated, and so on and so on.
One can ask, maybe we are thinking about it the wrong way? Well, the answer is that it is possible. We can define "size" in other ways. Cardinality is just one way. The problem is that there are certain properties we want the notion of "size" to have. We want this notion to be anti-symmetric and transitive, for example.
Namely, if $A$ is smaller or equal than $B$ and $B$ is smaller or equal in size than $A$, then $A$ and $B$ have the same size; if $B$ also has the same size as $C$ as well, then $A$ and $C$ are of the same size too. It turns out that the notion described by functions has these properties. Other notions may lack one or both. Some notions of "size" lack anti-symmetry, others may lack transitivity.
So it turns out that cardinality is quite useful and it works pretty fine. However it has a peculiarity... well, who hasn't got one these days?
To overcome this, we need to change the way we think a bit: proper subset need not have a strictly smaller cardinality. It just should have not a larger cardinality. This is the right generalization from the finite case, rather than the naive "strict subset implies strictly smaller".
To read more:
- Is there a way to define the "size" of an infinite set that takes into account "intuitive" differences between sets?
Best Answer
No. The statement is still true. The cardinality of the natural number set is the same as the cardinality of the rational number set. In fact, this cardinality is the first transfinite number denoted by $\aleph_0$ i.e. $|\mathbb{N}| = |\mathbb{Q}| = \aleph_0$. By first I mean the "smallest" infinity.
The cardinality of the set of real numbers is typically denoted by $\mathfrak{c}$. We have $\mathfrak{c} > \aleph_0$, since we can set up a bijection from $\mathbb{R}$ to the power set of the natural numbers and by Cantor's theorem, for any set $X$, we have $|X| < |2^{X}|$. So we have $|\mathbb{R}| = |2^{\mathbb{N}}| > |\mathbb{N}|$. So what this essentially says is that "there are more real numbers (which include rational and irrational numbers) than there are integers" in some sense.
The continuum hypothesis states that "there is no set whose cardinality is strictly between that of the natural numbers and that of the real numbers" which essentially means real numbers form the second "smallest" infinity.