Some notes on Hofstadter’s Typographical Number Theory


In Godel, Escher, Bach: An Eternal Golden Braid, Douglas Hofstadter outlines his axiomatic “Typographical Number Theory” and sets certain problems for the reader – one is to show that b (a variable) is a power of 2.

These are my notes in trying to demonstrate this (hopefully understandable to anyone who knows a bit of symbolic logic and has a passing knowledge of Peano’s axioms.

My reasoning runs like this: if a number is a power of two then it has no prime factors other than 2 (and 1, if we count that as a prime) – see the earlier entry on the fundamental theorem of arithmetic.

A prime (a) in TNT:

\exists a: \sim \exists a^{\prime}: \sim \exists a^{\prime\prime}: < a^{\prime}.a^{\prime\prime}=a \wedge \sim a^{\prime} = 0 \wedge \sim a^{\prime} = S0 \wedge \sim a^{\prime\prime} = 0 \wedge \sim a^{\prime\prime} = S0>

First Update: Now realise there is a simpler way of stating a prime in TNT – namely that there is no two numbers bigger than one the product of which is the number we seek:

\exists a: \sim \exists a^{\prime}: \exists a^{\prime\prime}: SSa^{\prime}.SSa^{\prime\prime} = a

Second update:

So, we have a definition for a prime, a, and we can set  a to a prime other than 2.

\exists d: \exists a: \sim \exists a^{\prime}: \exists a^{\prime\prime}: <SSa^{\prime}.SSa^{\prime\prime} = a \wedge \sim a = SS0>

Then

\exists b: \exists c: \sim \exists a: \sim \exists a^{\prime}: \exists a^{\prime\prime}: <SSa^{\prime}.SSa^{\prime\prime} = a \wedge \sim a = SS0 \wedge \sim b = a.c>

I think this is a sufficient definition for “b is a power of 2”, as we know that all numbers are products of primes and we have ruled out any prime other 2 being a factor of b. Is that right?

On further thought I don’t think that’s enough, because we need to specify that b is a multiple of 2.

So what about this?

\exists b: \exists c: \exists d: \sim \exists a: \sim \exists a^{\prime}: \exists a^{\prime\prime}: <SSa^{\prime}.SSa^{\prime\prime} = a \wedge \sim a = SS0 \wedge \sim b = a.c \wedge b = SS0.d>

So has that nailed it?

How I discovered the fundamental theorem of arithmetic by chance


Cover of "Gödel, Escher, Bach: An Eternal...
Cover via Amazon

Actually, of course, I rediscovered it.

I have been attempting to read, for the third time Douglas Hofstadter‘s celebrated Godel, Escher, Bach: I bought a copy in Washington DC in 2009 and loved it (though didn’t get very far before I put it down for some reason) but I have always struggled to get deeply into it: it’s plainly a great book – though having read more on Turing these days I am not sure I’d subscribe to what appears to be the core thesis – but it’s not an easy read.

(Though Hofstadter’s preface did inspire me three years ago to read the brilliantly compact Godel’s Proof– buy, steal or borrow a copy if you are at all interested in maths.)

This time round I am feeling more confident I’ll make progress, it just seems a bit easier to grasp – possibly because I am feeling more confident about maths these days (not that there is any higher maths in it – but grasping some of the more complex stuff does seem to help with all of it.)

So I got the part known as the “MU puzzle” – can you go from the axiom MI to the theorem MU following the rules of the formal system he sets out. I thought – oh, yes, easy, just find a power of two that is also a multiple of three – and in my head I start going 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096 – a list I have been familiar with for thirty three years or so. But none of them are multiples of three.

Now, presumably anyone who knows anything about prime numbers has by now said “of course they are not, haven’t you heard of the fundamental theorem of arithmetic?” – well it seems the answer to that is “err, no”.

Or, if I had, I never really grasped its meaning. Each number cn be factorised into a unique set of primes (if a prime then just itself, of course). That precludes any power of two having as a factor any other prime number (of which three is of course one). It’s really epically important in terms of understanding numbers and I am slightly shocked and puzzled I have never really understood it before now.