Diagonal Arguments and A Fixed Point Theorem

The Liar Paradox

A man says that he is lying; is what he says true or false?

Eubulides of Miletus

Fourth Century B.C. Greek philosopher

The Barber Paradox

In a village lives a barber, the barber shaves everyone living in the village who does not shave himself, but no one else.

Who shaves the barber?

Russell's Paradox

Bertrand Russell

British philosopher and Mathematician

The Mathematical Version, Russell's Paradox, was critical to the understanding of the importance of formalism in Mathematics.

In his work he refered to:

Berry's Paradox

What is the least integer not describable in fewer than thirteen words?

_______________________________________________________________________________________________________________

A Really Super Computer:

The Computer - The computer we are looking at is standard except that it has unlimited memory. Somehow it can grab as much memory as it needs to do calculations. The bytes in memory are ordered by the Natural Numbers {0,1,2....} . I am not claiming that the computer is fast, just that it is as big as it needs to be to make any calculation.
Target Programs - We are working with some general purpose language Java, C , C++, however, we want to think of the program as compiled and sitting inside our computer in a consecutive sequence of bytes, therefor we can think of a program as a single (binary) number sitting in computer memory. We use $\QTR{Large}{c}$ to denote such a program/number. We can think of programs have an order given by their representation as numbers.

The programs we are interested are those that realize functions of the form That is, if we load into our computer, write $\QTR{Large}{n}$ in the appropriate place in memory, and start the program, after a while the program halts and we find in the appropriate place in memory.
The Program - This program accepts as input a Natural Number and returns if is one of our target programs and if it is not. Again everything is to be thought of as taking place in The Computer. We will write
The Program - This program accepts as input a Natural Number $\QTR{Large}{n}$ and returns the number , the internal representation, of the $\QTR{Large}{\ n\ }$ th Target Program. We write

Some psudo-code for :

Target_c( n ){

int i=0, j=0;

while(True){

if( Check_c(i)){

if( j == n )return i;

j++;

}

i++;

}

}
The Program - This program accepts as input two Natural Numbers $\QTR{Large}{n}$ and $\QTR{Large}{m}$ . Computes and then computes

that is

The Problem: No matter how super our super computer is, cannot be written.

Proof: Consider the function If can be programmed, so can $\QTR{Large}{A(n)}$ .. Let $\QTR{Large}{r}$ be such that is the corresponding internal representation of $\QTR{Large}{A(n)}$ .

The problem is

______________________________________________________________________

The Halting Problem:

Question: Can we write a Program , such that given any syntatically correct program, again thought of as a number , and an input to that program, determines if the program will eventually halt on input $\QTR{Large}{m}$ ?

Answer: No, similar to the argument above, except define . $\QTR{Large}{H(n)}$ such that:

It halts if is false.
Goes in an infinite loop if is true.

______________________________________________________________________

The Fixed Point Theorem

The Setting:

Given sets $\QTR{Large}{S}$ and $\QTR{Large}{T\ }$ , is the set of maps from $\QTR{Large}{S}$ to $\QTR{Large}{T}$ . We want to look at subsets

For Example:
- 1. $\QTR{Large}{S}$ $\QTR{Large}{=}$ $\QTR{Large}{T\ }$ any sets and all maps $\$
  2. $\QTR{Large}{S}$ $\QTR{Large}{=}$ $\QTR{Large}{T=N}$ and are the recursive functions.
  3. $\QTR{Large}{S}$ $\QTR{Large}{=}$ $\QTR{Large}{T=R}$ and are the continuous functions.
Associated with any map there is a map

defined by the formula , where . Note that in the 3. cases above

$\QTR{Large}{S}$ $\QTR{Large}{=}$ $\QTR{Large}{T\ }$ and if $\QTR{Large}{M\ }$ so is , $\QTR{Large}{\in }$ $\QTR{Large}{M\ }$ is closed under composition..

The Theorem:

Suppose we are given two sets $\QTR{Large}{S}$ and $\QTR{Large}{T\ }$ and a map

Let be the set of maps where .

Letting be the diagonal map, assume .

$\hspace{0.5in}$ In particular, for some

Then any function such that has a fixed point.

$\hspace{0.5in}$ In particular, for some ,

Proof:

Under these assumptions for some So ,

$\hspace{0.5in}$ In particular, is a fixed point of $\QTR{Large}{h\ }$ .

_______________________________________________________________________

Corollary 1.

Suppose we have any set $\QTR{Large}{S\ }$ with more than 1 member then there is no map , such that

for any .there is an such that $\QTR{Large}{g\ =}$

Proof:

Following the notation above, thinking that $\QTR{Large}{\ }$ is more or less by definition, it is certainly a map.

Also by definition for any , , here

Since $\QTR{Large}{S}$ has at least 2 members, choose any map without a fixed point contradicting conclusion of the Theorem.

______________________________________________________________________________

Corollary 2.

The is no (total) recursive function such that for any (total) recursive function there is an such that

Proof:

formally is recursive.
The successor function, has no fixed point. and again the set of recursive functions is closed under composition.

_______________________________________________________________________________

Corollary 3. There is no continuous function from the real line onto the set of continuous real valued functions.

Proof:

Use the fact that does not have a fixed point.

Here a cardinality argument does not work since the cardinality of the set of continuous real valued functions is the same as that of the Reals.

________________________________________________________________________________

NOT Corollary 4.

Theorem

Primitive Recursive Functions ARE Recursively Enumerable

Proof:( See)

________________________________________________________________________________

NOT Corollary 5.

There is no continuous function from the unit interval $\QTR{Large}{[0,1]}$ onto the set of continuous real valued functions from the unit interval to itself.

Proof:

Lots of easy proofs but every continuous function does have a fixed point.

________________________________________________________________________________

(Exercise Due May 2) NOT Corollary 6.

$\QTR{Large}{S}$ $\QTR{Large}{=}$ $\QTR{Large}{T=N}$ and are the constant functions These are even primitive recursively enumerable .

Moreover if is any function and $\QTR{Large}{M}$ so is , $\QTR{Large}{\in }$ $\QTR{Large}{M}$ Yet the Theorem itself does not apply. Why?