Not feeling well, so I’m spending Saturday night tucked in bed reading Gödel, Escher, Bach, which I picked up from the library last week. Let me just say that if it takes as long to read the full twenty chapters as it has the first three, there’s no way I’m finishing this before I have to return it. I generally like Hofstadter’s style but it’s quite brief in places, and I find myself having to try out paraphrases and interpretations to understand what he means. I am currently stuck on his formal system for primality at the end of chapter 3 and I’m sure I’m just misunderstanding some part of the notation. I googled around in the hope of locating another explanation. I have found:
- what looks like a very nice overview of the book aimed at high school students on MIT OpenCourseWare, which skips the primality formal system
- an interesting interpretation of Inception referencing GEB
- and a Wolfram Alpha demo that lets you explore the system and generate theorems but which crashes my computer when I try to install it. The documentation’s pretty helpful though.
I will do my best to paraphrase the problem, in case one of my readers can help me out, but also because I believe there should be a variety of explanations of a given topic available online.
Hofstadter begins by stating that x, y and z are strings of hyphens*, and identifying an “axiom schema” or “thing that you just have to take on faith is true”. That schema is xyDNDx. We can interpret this as string x plus string y does not divide string y, although it’s important to point out that the formal system doesn’t inherently care about what you can or cannot divide – that’s the meaning we’re assigning to the letters DND. Because we trust Hofstader that this system represents division, primality, and all those good things (as Hofstader would say, the system is isomorphic to primality) we can use discrepancies between the two to locate flaws in our own thinking. But we can’t actually reason from them – we can’t say that xyDNDx is true because a number greater than x (xy) cannot divide x. That’s why it’s an axiom, a thing we have to take on faith within the formal system.
(* Probably worth saying that anytime you see a “-” below it is a hyphen, not a minus sign.)
(Added later: In the process of typing this out, I figured out where I was getting stuck. Hofstadter uses a confusing notation, where the values of x y and z change from axiom to rule and from rule to rule. Why doesn’t he just create new variables each time – x,y,z,a,b,c,etc? Or, if we’re re-using variables, why do we need z? We never need more than 2 strings in an axiom or rule. Maybe there’s a reason for these choices, but I find them deeply confusing. I imagine he’ll follow this pattern throughout the book, so I’ll try to let it go (let it go! (sorry.)) Thank you, readers, for being my Rubber Duck.)
Anyway. There are a few rules that allow us to generate theorems from this axiom schema. Rule 1 states that xDNDy -> xDNDxy. Regardless, if you try this out with real number examples, you’ll see that it works isomorphically. For instance:
So now we have a formal way of representing the concept “does not divide”. But how can we represent “has no divisors”, which is what primeness/primality actually is? Rule 2 gives us the rule –DNDz -> zDF–. This is easy to interpret into plain English. If two does not divide a string, than that string has no divisors less than or equal to two. Hofstadter calls this being ‘divisor-free’, represented as DF. Rule 3 extends this with (zDFx and x-DNDz) -> zDFx-. Wolfram Alpha paraphrases well: “if z is divisor free up to x and if x+1 does not divide z, then z is divisor free up to x+1.” For example, if we’ve already established that 7 is divisor free up to 5, and 6 doesn’t divide 7, then 7 is divisor free up to 6. Note that this rule, taken alone, allows us to say “35 is divisor free up to 3, and 4 doesn’t divide 35, so 35 is divisor free up to 4″. Which is totally true. Iterating just one more time, though, will have us checking if 5DND35 is a theorem. It’s not – you can’t generate it using rule 1 – so we can’t add it to our pile of primes.
We make said pile of primes with the following final rule: z-DFz -> Pz-. Again, Wolfram Alpha has a good interpretation: “if z+1 is divisor free up to z then z+1 is prime”. For example, if 13 is divisor-free up to 12, then 13 is prime.
To generate primes using this ruleset, you’d take the following steps:
1) You start with a number that you want to test is prime. If you’re generating primes, you can start from 1. Let’s test 5. We start with rule 2, replacing z with 5. Is 2DND5 a theorem?
2) To answer this question, we attempt to generate it from the axiom schema. We can do so by assigning x to 1 and y to 1. Then our initial axiom is (1+1)DND1 or 2DND1. Applying rule 1, we get the theorem 2DND(1+2) or 2DND3. Applying again, we get 2DND(1+2+2) or 2DND5. So it is a theorem. Since 2DND5, 5DF2 – that is, 5 is divisor-free up to 2.
3) We next see if we can apply rule number 3. We’ve shown that zDFx – that 5 is divisor-free up to 2. Is (2+1)DND5 a theorem? Again, we attempt to generate from the axiom schema. We can do this by assigning x to 2 and y to 1. This gives us an axiom 3DND2. We can add to it by applying rule 1: 3DND(2+3) or 3DND5. Excellent! So we can apply rule 3, and say that 5 is divisor-free up to 3.
4) After each attempt at rule number 3, we check rule number 4 to see if the conditions are satisfied. Rule 4 says that z-DFz -> Pz-. Remember, we’re not substituting our value of z in for z here, because variables don’t need to be consistent between rules, only within them. Instead, we can ask: have we shown 5DF4? The answer is no, we’ve only gotten up to 5DF3. So: once more back to rule 3.
5) We’ve shown that 5DF3. Is 4DND5 a theorem? Yes, because we can generate it from our axiom schema by assigning x to 1 and y to 3. This gives us an axiom of 4DND1. Applying rule 2, we get 4DND(1+4) or 4DND5. Yay! So 5DF3 and 4DND5, which means 5DF4 – 5 is divisor-free up to 4.
6) Back to rule number 4. Have we shown that 5DF4? I believe we have. Applying rule number 4, we determine that P5 – that the number 5 is prime.
Okay, I’m going to bed.