Gödel! #4 An Introduction to Gödel’s Theorems 2.2

2.4 Effective enumerability

Similar to effective computability and effective decidability, effective enumerability describes which sets can be enumerated using a strictly mechanical procedure (such as our Turing machines described in secion 2.2). Now it is easy to imagine a program that enumerates a finite set: it just spits out the elements of the set and then halts. Consider the program:

\texttt{for (int i=0;i<5;i++)\{}\\\texttt{\indent print(i);}\\\texttt{\}}

This program will enumerate the set \{0,1,2,3,4,5\}. But what does it mean to effectively enumerate an infinite set? Consider the program:

\texttt{for (int i=0;;i++)\{}\\\texttt{\indent print(i);}\\\texttt{\}}

We can get an intuitive sense that this program will enumerate the set of all natural numbers, \mathbb N, but can we formalize the notion of a non-terminating program being used to enumerate an infinite set? This isn’t discussed in the book, but I like to think of it as follows:

A program \Pi is said to list an element e iff there, after some finite number of steps of execution \Pi prints out e. If \Pi lists every element in a set B then \Pi is said to enumerate B. Thus, B is effectively enumerable iff there exists a program \Pi which enumerates it.

So in our program above, we can now see formally that every element of n\in\mathbb N will be listed after exactly n+1 steps (if we ignore steps involved in managing the loop logic.

An interesting fact is that every finite set is enumerable. To observe this, consider a finite set \{n_0,n_1,\ldots,n_k\}. This set is then enumerable by the program:

\texttt{print(}n_0\texttt{);}\\\texttt{print(}n_1\texttt{);}\\\ldots\\\texttt{print(}n_k\texttt{);}

Thus, given any finite set, we can in essence simply store every element in the set into memory and spit them out on demand.

2.5 Effectively enumerating pairs of numbers

What follows is a useful theorem that we will use time and time again.

Theorem 2.2: The set of ordered pairs of numbers \langle i,j\rangle is effectively enumerable.

Proof: Consider a table of ordered pairs of numbers:

\langle 0,0\rangle \rightarrow \langle 0,1\rangle \langle 0,2\rangle \rightarrow \langle 0,3\rangle \ldots
\swarrow \nearrow  \swarrow
\langle 1,0\rangle \langle 1,1\rangle \langle 1,2\rangle \langle 1,3\rangle \ldots
\downarrow  \nearrow  \swarrow
\langle 2,0\rangle \langle 2,1\rangle \langle 2,2\rangle \langle 2,3\rangle \ldots
 \swarrow
\langle 3,0\rangle \langle 3,1\rangle \langle 3,2\rangle \langle 3,3\rangle \ldots
\downarrow
\vdots \vdots \vdots \vdots \ddots

We can use a computer to zig-zag through this table (in the order indicated by the arrows) which will eventually arrive at every possible combination. Since the table will be stored somehow in memory, we must generate it on the fly since we can’t operate on an infinite table, but we can make the table of arbitrarily large size and increase it as needed due to the infinite memory capabilities of our idealized computer system. Thus, we have created a program which enumerates the set \mathbb N^2.

QED

The book mentions that you can explicitly create a computable function f:\mathbb N\rightarrow\mathbb N^2 that will do this without the use of the table, however it doesn’t go into details and even if it did, this exercise can be quite messy. The way I actually know how to do it doesn’t involve the table at all and actually goes the other way, \pi:\mathbb N^2\rightarrow\mathbb N. It looks like:

\pi(x,y)=2^x(2y+1)-1

You can also define inverse functions \pi_0,\pi_1 such that \pi(\pi_0(n),\pi_1(n))=n, but this is complex and involves \mu-calculus which I’m not ready to get into yet.

That wraps up chapter 2. Next time: axiomatized formal theories and why we should care.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: