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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was reading an article on infinite sets and I came across a proof about how the power set of natural numbers has a greater cardinality than the set of natural numbers. I know that both given that proof and the proof of Cantor's theorem, that it must be true. So, my question is why does encoding the each set of natural numbers in the power set using Gödel numbering not work?


share|cite|improve this question
How do you propose to assign Gödel numbers to arbitrary subsets of $\mathbb N$? The standard arithmization schemes only handle finite subsets of $\mathbb N$. – Henning Makholm Feb 27 '12 at 15:36
Not all subsets of $\mathbb N$ are definable. – azarel Feb 27 '12 at 15:38
You can find encodings, though not fully satisfactory ones, of the recursively enumerable subsets of the natural numbers, via the index of a Turing machine that recognizes the set. But encoding all subsets is ruled out by cardinality considerations. – André Nicolas Feb 27 '12 at 16:39
up vote 2 down vote accepted

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}$.

share|cite|improve this answer

Your Answer


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.