2.
In the Beginning, There was Gödel
As you may have guessed – or
known – and the rest of you will now be told, the first words after
“Gödel”, are also the first words of his proof that that there
is more than one infinity. But the key step is to make a interesting
assertion profound.
What was it that Gödel that is so
important? For almost all of recorded history, a proof was either
regarded as true or false. If it had not been decided yet,
mathematicians assumed that the proof was to be forthcoming. In other
words, the answer was out there – someplace – it is just that we
had not discovered it yet -only a few obscenely bright mathematicians
such as Gauss said that they could come up with propositions which no
one could either confirm or deny. Even when Aristotelian logic was
replaced by Boolean logic, there was still the root that logical
propositions were either true or falseby most people. If it was not
known, then it was a human problem, not a math problem. Somewhere out
there, the maths new whether they were true or false. There was no
third. Even though the proposition that propositions could be neither
one nor the other had been proposed.
I
am going to reverse a few of Gödel's steps, to make easier for us.
What I'm going to do is introduce
Boolean architecture, where everything came out true or false:
T ← P → F
First, I am going to check if the
proposition can be checked, Gödel
did this later, but it is still his proof:
T ← P'(P )→ F
And then went on to say, it again this is trivial - so trivial that
no one even noticed it – that if it were a mathematical formula,
then it to could be checked in mathematics. That is to say, the
question itself could be checked.
After all, all mimsy were the
borogoves is English, after a particular literary fashion, but
not mathematics. And one could decide this in the language of
mathematics. Taking a roof from Lewis Carroll and Lewis Padgett, this
trivial step was actually key to the question. Because if the first
question was could the question the decided in mathematics, as a
mathematical term, we are actually deep in an interesting question.
For the next step he took was to
say that if that is a question, then metaphorically, and
meta-logically, the question about being the question could also be
answered, and so on:
This is what we call recursion –
and computer scientists were encouraged to ask recursion problems,
partially to test their operating system and computer language.
Because in an actual computer, it would eventually stop sometime –
though it does not stop mathematically. So this is the start of
recursion, from Gödel.
The next step is to introduced a
~, or negation. But that means that if the proposition is true, then
the argument is false, and if the proposition is false, then the
argument is true:
F → T → F → T → F → T →
F → T → F → T …
Now take the next step: what makes 0 and 1 so difficult? Because
they are the basis of Boolean logic, and every proof Boolean logic is
either 0 or 1. So long as your proofs do not worry about this, there
is no problem. But if 0 or 1 becomes useful, than we have a problem,
because then the proofs enter in to the answer. One problem is if we
take an answer which becomes 0, but it is a negative answer – then
it will reverse, if the answer is about a topic which is not under
discussion, then the proposition is true. And so on. If we play a
game, we can see this almost immediately. For example, let us say you
have two make a choice between two roads, and by the road sits a man.
He is a very special man, either everything he says will be true, or
everything he says will be false. So you ask the question “What
road would you take if you were in my position?”
Now think about that for a moment, you ask a question which asks a
question. This means that the liar once to lie, but is forced to tell
the truth because he wants to lie about lying. The truth teller is
not so encumbered – he tells the truth about telling the truth,
which is no problem. So a lie about another lie is the same as the
truth to tell another truth.
What Gödel did was attach this one zero operation to a counter –
each time you incremented the counter by another prime, which since
Euclid we know is infinite. So instead of a 0,1 Going on to infinity,
which is trivial, we had a series of primes going on to infinity.
T ← P(G+3)((~P(G+2)(PG+A(G))) →
F
And it is deep. From trivial to
deep in only a few lines of thought. This far a high school student
can get. But there is one more step two getting to Gödel's proof.
With these two pieces, he moved on to the subject of primes. He noted
that if there were primes than all of the operatives – addition and
so on – could be phrased as numbers. And we are off to the races,
because now the entire set of mathematics can be represented as
logical strings, in the same way that anything else could be. Such as
1 + 1 = 2.
Now, 1 + 1 = 2
had been shown by Whitehead and Russell to the a deep problem, taking
pages of proofs to actually be decided. What was happening at this
time, generally, was that the underpinnings of math, when questioned,
turned out to be anything but clear. Even the means of such proofs
was being refined, with a problem discovered by Frege on the creation
of paradoxical sets finding a solution in Russell, with a more
elegant refinement in Zermelo-Fraekel set theory.
Thus,
he started 1931 with the assertion that “the development of
mathematics has been in the direction of greater exactness has – as
is well known – lead to large tracts of it becoming well
formalized, so that proves again be carried out according to a new
mechanical rules, the most comprehensive formal systems yet set up
are, on the one hand, the system of PM, and on the other hand, the
system for set theory by Zermelo-Fraekel (later extended by von
Neumann).” I will note that this is not the last time that von
Neumann is referenced. I will also mention the 1997 extract by
Schwalbe and Walker as a good summary of Zermelo role in all of this,
by Harvard University, with input from numerous inputs, including
Kuhn.1
What he did in this startling
introduction was too subtle for words: he introduced a way to build 0
and 1 into primes and composites. 0 and 1 do not fit the primes and
composite picture, and that is all right if they do not enter in to
the picture of proofs. (We will get later to the third Number which
is not prime nor composite: -1.)
So what he has done, is attach a riddle to the engine of axioms, and
sets a counter which he knows will be infinite.
Then he makes the final step: is there a question which can be asked
mathematically, which will set off our 0/1 trigger? The answer is:
yes. And the question is: is this answer a question which could NOT
be answered, mathematically?
And
there we are: if the proposition that the question asks about is
true, then the proposition is false. But if the answer is false, then
the proposition is true. And so it goes, to quote Kurt Vonnegut. So
that means in a world which has only two answers, there is underling
a third answer. And it is always there, and keeps track of how many
times it has been answered. 0, 1, and this third answer is built in
to be bedrock.
Now
dressing this up as a proof is not an easy thing to do, but if you
have the answer, it is tedious high level work, but it is tedious. In
the language of math, it is “trivial.” remember that trivial does
not mean the same thing – often math people like to joke how a math
professor stops as he is writing something down, which is “trivial”,
and spends the next hour puzzling over whether it really is trivial.
So he goes to his notepad, with everyone in the class waiting, and
then at the end of the hour, he finally looks up and says “Yes, it
is trivial!” with his notepad filled with equations.
So rather than the answer being 0 or 1, it is 0, 1, or Unknown. Thus
even the two division B-tree is really three, and a three that keeps
track of how often it is called. Later, we shall show that the
numbering system is not correct, and that it is -1 and 1, with 0
being the limit of unknown.
It did not occur to anyone that
this would have practical possibilities, at least so far as the word
willing to publish, or even quoted. Now if I were relating all of the
history of this idea I would begin with Cantor, move on to bring
Principia Mathematic by the pair of misguided geniuses Whitehead and
Russell, then take a moment to admire the foundation of the rules of
the game by von Neumann and Morgenstern, and tell all of those odd
quirks of personality. This is what one gets by thinking about
probability vectors such as P and Q and a positive number that will
solve an equation that is complementary to pT (A-
lB)q = 0.
The
key is building recursion into the engine of axioms, because that is
what makes the rest of the proof. This proof then turns on the
uniqueness of prime numbers, And makes 0 and 1 part of the engine; it
translates into primes, and builds from there into a GN version,
which will be unique.
Recursion means that the question of whether something is
expressible, is also an equation. This is why Neg(17(Gen(r)) means
something very specific in Gödel logic – it is the point where
logic is also an equation.
What this ends up with, through a variety of steps beyond Gödel's
original proof, is a three tier logical system.
It
then says for any proof system one of three things is Logically
possible:
1.
The system is finite, and will cast out all of the proofs which would
create disharmonies.
2.
The system is finite or infinite with a fixed number of axioms, but
will have disharmonies within it.
3.
The system is infinite in its number of axioms.
Of
course there are systems which are illogically possible, but that is
the realm of poetry, prose, and lyrics. Which are not to say these
are not important.
One might think, but not to
quickly mind you, that a system which is finite and casts out all of
the proofs would be preferable. Humanity got along just fine without
them, or so it appears. After all classical logic has only two
variables, and a virtual plot of eliminating the obvious from the
conclusion. “Whatever is left, however improbable, is the truth,”
says Sherlock. But the things that you have to give up are
tremendous. Such as multiplication, that is right 3 x 3 is right out.
Sherlock may get by without multiplication, but the rest of us need
it, for buying milk, and so on.
This is why very old digital
machines would actually work, they did not number that many steps,
and even such multiplication as they could do, was within limits. In
other words they had a finite enough math to work. As we got more
precision, we crept up to an invisible line – a line where there
was too much to hold in a finite space. We had broken through,
unintentionally, to the infinite.
The third choice offers
attractions which have yet to be explored, but will require things
like Goldbach Postulate will have to be included, things on which
nothing else relies upon. This is quite a drag on the system, and it
will have to have a new sort of mathematics to engage in, there might
not be anything wrong with that, and one of you might discover it.
What this means, is that the
axioms which built up the system are equivalent to primes, one could
make a great deal of progress with only a limited set of primes –
but there will always be truths that cannot be proven – or at least
one false thing which can be proven. The theorems that can be proven
are composite numbers in logical space. Thus, there are as many
primes as composites in the infinite space of logic.
But
we knew this, because there are two numbers which do not admit to
prime/composite ordering: 1 and 0. the root of Gödel theory is that
trying to push one and zero in two the logic creates a central
problem when doubled back on itsself – we can do it, but pushing 1
and 0 keeps doubling back on itself. It is this reference back to the
theory which creates problems.
For this reason is why Codd and
Date needed variables which were undecided in their Relational
Database System, a direct descendent of what we are talking about.
-
One
major difference between a Gödel numbered system and a current is
that generally it is the GN, which is to be found, either
because it is unknown, or it is being hidden by the party who wants
not to reveal what they are doing. This means that GN is often worked
backwards from a von Neumann position, the proof of which is the
problem to be set up.
One
example of this is from my friend Scott Kominers3, of the
Harvard Society of Fellows. The key determiner of a patent troll,
called in the language of art a “Non-Practicing Entity”, is the
difference in the target company. In a normal lawsuit there is harm
that is alleged to have been done, and a lawsuit is filed against the
holder of the patent. In a NPE lawsuit however there is a direct
correlation between the ability to pay, and the likelihood that such
a lawsuit will be filed. Even if the money does not come from the
patent.
This,
and other examples, means that the GN is only a fraction of the
story, and for all practical purposes is the endpoint not the
beginning. One often finds this in the sciences: first one needs to
find out where there is a problem. But it also means that the problem
exists and no way of solving it has yet appeared. It is a problem
that is discovered first.
But when a problem appears, most
people do not think of how to solve the problem in general, but
attack the problem in detail; which clutters the literature with
innumerable small examples. But a few pioneers see a larger
question, and set themselves to work. Once a current has been made,
in our electoral example, then one needs a voltage and resistance. In
the same way, in informational space, one needs a machine, and a
limit. These two followed quickly because once the problem was
determined to be informational, it was only a matter of time and
brilliance. Because let us remember that even the failures were
brilliant, and even more so the two successes.
For example, someone Needs to find
out the minimal completeness number, by taking Gödel's logical
steps, and place them in order, giving us minimal number - so (,),+
and so on in the least order, and that is merely trivial problem, far
harder is to take the terms and see if there is any correlation
between the axioms and the prime numbers – call it “ God's
Completeness”, where the order of axioms is also the order of
primes. More on this later.
The world had gone to sleep where
there were proofs, on one hand, and quantities on the other. It woke
up in a world where the two things were enmeshed, and that they were,
logically, inclined in an infinite haze.
Now, I was in some genius who
thought of this – it had already been baked in two the cake. All I
had to do was put it back together. And can to, you can build it from
top down – basically if you know what you are doing – or you can
build it from bottom up – if you do not. Of course I belted from
bottom up.
The
first thing to recognize is that the algorithm calls itself, this
would not happen if there was not a reason – a clue that somebody
someplace new what they were doing, even if unconsciously. The first
and most mindless step is to do just that :
print_this() {
println(“ this is called by itself.”);
print_this();
}
This is
written in a pseudo-code which resembles C, I did not have time for
Pascal, even though he shows up in this book. Pascal, the language,
does not get at any of the larger points, and addresses many smaller
issues which do not have a reason to. Its written by a man who had
obsessions, (Wirth, though I will not pun on name) the which I do not
share.
But you
realize very quickly, that this goes on for ever – and we want be
program to halt if it can reasonably be solved.
So we
change, one step at a time:
print_this( character [] this) {
println(”/c is called by itself.”, this[]);
print_this( this []);
}
now
currently stops, though not through any action of our own – there
is a limit to how many steps of recursion the computer can contain –
though now it is many more then when this was done.
And remember that we want a Gödel
recursion model, because that is, at the heart, of the deep point.
But now we get in to one of the differences between pure mathematics
and computer science – time. It does not exist for pure
mathematics, but it does for computer science. This means that either
we use a clumsy point backwards motion, or we point forwards. So
first of all we need to solve that:
print_this( character [] this, character [] tf) {
println(”/c is /c.”, this[],tf[]);
if(tf[]
= “t”) {
tf =
”f”;
} else {
tf =
“t” ;
}
print_this( this []);
}
now we have two steps left, first
a counter:
print_this( character [] this, character [] tf, int n) {
println(”/c is /c on the /n .”, this[],tf[]);
if(tf[]
= “t”) {
tf =
”f”;
} else {
tf =
“t” ;
}
n++;
print_this( this [],tf,int n);
}
now for
the hard part, because computer science does not easily have a quick
way to determine the next prime, but you will get to this later. As
it is only pseudocode, for the moment we can ignore it, and put a
function which do not know how to do yet.
print_this( character [] this, character [] tf, int n) {
println(”/c is /c on the /n .”, this[],tf[],n);
if(tf[]
= “t”) {
tf =
”f”;
} else {
tf =
“t” ;
}
next_
prime(n);
print_this( this [],tf,int n);
}
then we must relate this to the
next iteration – so that the recursion references itself.
print_this( character [] this, character [] tf, int n) {
if(tf[]
= “t”) {
tf =
”f”;
} else {
tf =
“t” ;
}
println(”/c
is /c on the /n .”, this[],tf[], n);
next_ prime(n);
print_this( this [],tf,int n);
}
I will
leave you to write the algorithm, which took me a night of not
sleeping for your own amusement. But there in pseudocode is Gödel's
proof. It is easy because several brilliant people made small and
large contributions – we have just set our cells to do this, that
is all.
Realize
that I have used recursion by cutting and pasting the pseudocode, and
making small changes. Recursion is everywhere to us, though for a
long time it was unknown to the vast majority of people on the
planet.
