Clarification about positive definition of prime numbers in book Douglas Hofstadter "Gödel, Escher, Bach: An eternal golden braid"

Question

I'm reading this book in Dutch. There is a part that keeps me puzzled. Maybe I don't fully understand (needing explanation) or suspect potential errors in the translation (needing verification). Could anyone with an English copy help me in verifying? And if it's correct, please help me understand?

---

At the end of Chapter 3, Hofstadter is setting up a formal system to define the prime numbers in a positive way. This in contrast to defining them in a negative way, i.e. saying that prime numbers are those that are not divisible numbers.

1. It starts with a formal system for producing statements about whether X is divisible by Y. Hofstadter uses a coding system with strings of dashes/hyphens, x is a string containing X dashes/hyphens (e.g. '---' represents the number 3). In my copy, he mentions a production rule as follows:

   • Dutch: "Als x NDD y een stelling is, dan ook x NDD xy." (NDD = niet deelbaar door)
   • My translation to English: "If x NDB y is a statement, then also x NDB xy." (NDB = not divisible by)

   I think this rule should read "xy NDD/NDB y" in the end, instead of "x NDD/NDB xy", to be useful in his system. Then, it could be used to produce all numbers X that are not divisible by number Y, from the axioms (all dash/hyphen strings of the form x NDD/NDB xy).

2. In the next paragraph, there is the following sentence:

   • Dutch: "We zouden graag een manier willen hebben om in de taal van het systeem te zeggen: 'het getal Z is delervrij tot X', waarmee we bedoelen dat Z niet deelbaar is door enig getal tussen 2 en Z."
   • My translation to English: "We would like an approach to say in the language of the system: 'the number Z is divisor-free up to X', by which we mean dat Z is not divisible by any number from 2 to Z."

   I think the sentence should read "(...) by any number from 2 to X." instead.

3. Then finally in the formal system to produce the strings representing prime numbers, I can't seem to derive that for example 3 is a prime number, i.e. whether P--- is valid. Using the production rules backwards, I'd need to prove that 3 is divisor-free up to 2. But this is impossible using the available rules. At the same time, I don't see the purpose of the first production rule that is mentioned, so maybe it is not correct.

   • Dutch: "Als z NDD -- een stelling is, dan ook -- NDD z."
   • My translation to English: "If z NDB -- is a statement, then also -- NDB z."

   What is the purpose of this rule? The axiom "x NDD/NDB xy" already leads to conclude that 2 is not divisible by any number larger than 2. What do we learn additionally from 2 not being divisible by 1 (if that's even valid)? Rather - I think - a rule like this would be more useful:

   • My suggestion for an alternative rule: "If z NDB -- is a statement, then also z DF --." (DF = divisor-free up to)

   Then at least, from 3 not divisible by 2, we could conclude that 3 has no divisors up to 2, leading eventually to 3 being a prime number.

Answer 1

1. In Hofstadter's original English, the operator which the Dutch translator translates to NDD is DND. This is to be understood as "does not divide". Perhaps you have mistaken the left-hand operand for the right-hand one and vice versa?

2. You are correct. This must be a mistake in the translation. The English says 'We would like to have a way of saying, in the language of the system, "the number $Z$ is divisor-free up to $X$", meaning that no number between 2 and $X$ divides $Z$.'

3. You are correct. This must be another mistake in the translation. The English indeed uses DF exactly as you suggest.