2
$\begingroup$

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?

Thanks.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Henning Makholm Feb 27 '12 at 15:36
  • $\begingroup$ Not all subsets of $\mathbb N$ are definable. $\endgroup$ – azarel Feb 27 '12 at 15:38
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Feb 27 '12 at 16:39
2
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.