Question about problem in Godel, Escher, Bach

Factual Questions
1

Right now I’m reading Godel, Escher, Bach by Douglas Hofstader. I just finished the section on typographical number theory. At the end of the section, he gives some exercises to familiarize the reader with the theory and its conventions. For the first problem, write that “b is a power of 2.” I thought to show that b can’t have an odd factor, so I came up with this:

∀b:~∃a:<∃c:ca=b⊃∃d:ss0d=a-s0>

For all b, there does not exist an a, such that if there exists a c, such that ca=b, then there exists a d such that 2d=a-1.

I might have messed up on my syntax, but I think my idea was sound. But then the next problem asks to show that b is a power of 10. Hofstader warns that:

I wouldn’t really put myself in either category, so I turn to you, great dopers. I would think you have to show that b can be written in the form 2^n*5^n, but that’s about as much headway as I can make. Thanks in advance.

2

[For those who care and to whom it would mean something, Typographical Number Theory, unless I’m mis-reacquainting myself with it, is just the same as the usual presentation of Peano Arithmetic (except that the successor operator is only used in the syntax of numeric constants).]

Your first formula is a little off: you’ve given a formula that expresses “For all b, something something”, but you don’t mean to say “For all b, b is a power of 2”. You just want to say “b is a power of 2”. So leave off the initial ∀b.

The “something something” is a little off as well: you want to say “there doesn’t exist a number which is both a factor of b and odd”, but you actually say “there doesn’t exist a number such that if it were a factor of b it would be odd”. This latter statement is different from the former one [since it amounts to saying “there doesn’t exist a number which is either not a factor of b or odd”].

Also, technically, TNT only has + as a primitive operation, not -. So we’ll rephrase 2d = a - 1 as 2d + 1 = a.

So, pulling all these reformulations of your first statement together, we get that “b is a power of 2” can be expressed as “~∃a:[[∃c:ca=b] & [∃d:ss0d + s0 =a]]”

3

As for expressing “b is a power of 10”: if we could just find a way to simulate finite lists of numbers within TNT, we would be set. For then we could define “b is a power of 10” as “there exists a list whose initial element is 1, whose (k+1)-th element is 10 * its k-th element [for all k], and whose last element is b”.

And, as it turns out, we can simulate finite lists of numbers within TNT. The Chinese Remainder Theorem is key to the usual parlor trick here. But it’s just a convoluted hack to prove a technical curiosity; if you really cared about having the ability to express such things, you’d work (explicitly or implicitly) in a system that had more directly built-in than just TNT (even if, at the end of the day, it turns out that TNT could, contrivedly express all the same things).

Still, if you care to see the hack (creditable to a throwaway line by Goedel in his 1931 paper, and on which far too much time and mental space has been spent ever since): let’s start by considering how to specify some very simple sequences. For example, an arithmetic sequence (that is, in which each element is some fixed value plus the previous element, such as <1, 2, 3, …> or <7, 10, 13, 16, …>) can be specified by giving two values: the first element (call this Start), and the amount by which to increase each time (call this Jump). Obviously, to extract the k-th element of such a sequence, one just uses the formula Start + k*Jump. [Pedantry: This is on the convention that the first element is the 0-th one]

This is all good and well, but what we want is a way of simulating arbitrary finite lists, not very particular infinite sequences. Patience, patience. Let’s see if we can simulate more complicated sequences.

Well, if we can simulate arithmetic sequences, then we can also simulate the results of applying any definable operation to arithmetic sequences. In particular, let’s now talk about specifying a sequence with three values: let’s call them Start, Jump, and Div. The sequence this specifies will be the result of applying the operation “Div mod _” to the arithmetic sequence specified by Start and Jump; that is, the k-th element of this sequence will be Div mod (Start + k*Jump). [In case you don’t know, “Div mod x” means “The remainder when Div is divided by x”]. So, for example, the sequence specified with Start = 7, Jump = 3, Div = 100 will be <100 mod 7, 100 mod 10, 100 mod 13, 100 mod 16, …> = <2, 0, 9, 4, …>. Let’s call such sequences, I dunno, how about “divarithmetic sequences”?.

What’s the use of these convoluted things? Well, supposing I told you that any finite list you can think of is the start of some divarithmetic sequence. Then we can actually specify a finite list using four numbers: Start, Jump, Div, and the Length of the list.

And we’d then be able to define “b is a power of 10” as “there exist numbers Start, Jump, Div, and Length such that the corresponding list has a first element of 1, a last element of b, and each element within it is 10 times the previous one”, which is to say, “there exist numbers Start, Jump, Div, and Length such that Div mod Start = 1, Div mod (Start + Length * Jump) = b, and for all k < Length, Div mod (Start + (k+1)Jump) = 10 * (Div mod (Start + kJump))”. [Pedantry: Technically, what I’ve written here actually takes the length of the list to be Length + 1. It was easier to write and makes no difference for our purposes.]

If you really care about expressing it in symbols, well, you can expand it all out (remember to expand out the definitions of “mod” and “<”).

Ok, then, the only thing that’s left for us to prove is that it really is true that any finite list of numbers is the start of some divarithmetic sequence. I’ll put that in another post for cleanliness’s sake.

4

It’s been a long time since I’ve looked at TNT, but is there anything that rules out saying something like “b is a power of k if and only if b = 1 or there is some number c such that c is a power of k and b = k*c”? Even if multiplication isn’t a primitive, you can define it in terms of addition, so that’s not a problem.

5

The problem is that that’s a recursive definition, and, as is typical for first-order theories, TNT has no direct means for expressing recursive definitions.

So, finishing things off with the proof that any finite list of numbers is the start of some divarithmetic sequence: The key now is the Chinese Remainder Theorem: this tells us that if a[sub]1[/sub], …, a[sub]m[/sub] are all relatively prime (i.e., no prime divides any two of them), and <b[sub]1[/sub], …, b[sub]m[/sub]> is any list such that each b[sub]i[/sub] is less than the corresponding a[sub]i[/sub], then there is some number Div such that Div mod each a[sub]i[/sub] is the corresponding b[sub]i[/sub].

Thus, if we want some list B to be the start of some divarithmetic sequence, it suffices to find an arithmetic list A of the same length, all the elements of which are relatively prime to each other, and each element of which is greater than the corresponding element of B. Of course, for this last condition, it suffices that each element of A be greater than the maximum over all of B.

So if we could prove that there exist arbitrarily long, arbitrarily high-starting arithmetic lists of all relative primes, we’d be done.

This we do now:
Theorem: For any m and s, there exists an arithmetic list of length m, every element of which is > s, and any two elements of which are relatively prime
Proof: Let F be the product of all the primes < m. Consider the list of length m whose k-th element is 1 + (k + s)*F (using the convention that the first element has k = 0 and the last has k = m-1). This is clearly an arithmetic list of length m; furthermore, each element within it is >= 1 + s * F > s * F >= s (this last step because F >= 1). Thus, it only remains to show that every two such elements are relatively prime; that is, no prime divides both 1 + (k[sub]1[/sub] + s)*F and 1 + (k[sub]2[/sub] + s)*F for indices k[sub]1[/sub] < k[sub]2[/sub]. Assume, for the sake of contradiction, that the prime p divided both of these. Then p does not divide F (for if it did, it would have to also divide 1, which is impossible). But if a prime were to divide both of those, it would have to divide the difference, (k[sub]2[/sub] - k[sub]1[/sub])*F. As it couldn’t divide F, it would have to divide k[sub]2[/sub] - k[sub]1[/sub]. But this would mean it must be less than m, which would force it to divide F after all, yielding a contradiction. This completes the proof.

6

What a mess, eh? Still, it gets the job done.

It’s worth noting, incidentally, that if you removed multiplication from the definition of TNT, you couldn’t immediately get it back by finding a way of expressing it in terms of addition; in fact, you couldn’t get it back at all. In technical terms, Presburger Arithmetic doesn’t interpret Peano Arithmetic. The trick of expressing recursive definitions in terms of lists is quite general, but the specific hack of simulating lists using arithmetic sequences is only very narrowly applicable, and can’t get off the ground if you don’t already have the ability to express multiplications.

7

Ok, thanks for that, your math posts are always very thorough. :slight_smile:

But I have to wonder, does Hofstader really intend the reader to go through all of that hoop-jumping? Is there a way to write the statement with just the rules covered in the book to this point, which are just the basics? We certainly haven’t covered the chinese remainer thereom, and I don’t think modular arithmetic either. I would imagine there’s some answer with a few lines of cleverly constructed symbols. It does say these are practice exercises to test your understanding of the notation of TNT, after all. But then again, maybe not.

8

Well, hence the statement "and if you know quite a bit of number theory. ", I assume.

The final answer you get is pretty terse; it’s just proving that it works that’s complicated.

9

(It occurs to me, as a tiny, pedantic nitpick, that even after the corrections mentioned above, your formulation of “b is a power of 2” is as “b can’t have an odd factor”, but it really needs to be “b can’t have an odd factor greater than 1”. So where we used 2d + 1 = a, this should be replaced with, say, 2d + 3 = a. But this isn’t really an issue with your understanding of the syntax of TNT.)