luks@uoregon.UUCP (luks) (01/22/86)
This is in response to following request from Eric Postpischil: >I don't think this got posted the first time I tried it, so I am trying again. > >In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b >is a power of 10" in Typographical Number Theory. Does anybody have a solution >for this? I offer an outline of my solution to this, but I follow with an even more intriguing version of the problem suggested by Steve Becker, Physics Dept, Bucknell University, Lewisburg, PA 17837 (BITNET: sbecker@bucknell ). Solution to problem as stated: Since the TNT formula is tedious to type or read, an outline of the idea is best. I assume it is clear how to express such assertions as "a > b", "a = b modulo (m)" ("=" used for "is congruent to") Hofstadter indicated how to express: "p is prime" It is easy, for p prime, to express: "n is a power of p" (e.g., by asserting that n is divisible by no primes other than p"). Now, "b is a power of 10" iff "b = rs and there exist x and y such that r = 2**x and s = 5**y AND x = y" (We write it in this peculiar form to isolate the last conjunct "x = y", which is the real hangup.) Suppose that r = 2**x, and p is any prime > r+1. Observe that the SMALLEST t such that t is a power of p and t = r modulo (p-2) is precisely p**x . (Proof: For any z, p**z = 2**z modulo (p-2) and so, if p**z = r modulo (p-2) with z<x then modulo (p-2): 2**x = p**z = 2**z so that 2**(x-z) = 1 modulo (p-2) which implies p-2 =< 2**(x-z) -1 =< 2**x -1 so that p =< r+1, a contradiction.) We can exploit this to express a predicate for the assertion A: "p>r+1 and p is prime and there exists x such that r = 2**x and t = p**x" (for the last, by asserting t = r modulo (p-2) and there is no u<t such that u is a power of p and u = r modulo (p-2) ). Similarly, if s = 5**y, and p is any prime >s+4, the smallest t such that t is a power of p and t = s modulo (p-5) is p**y. So this gives us a handle on a predicate that asserts B: "p>s+4 and p is prime and there exists y such that s = 5**y and t = p**y" What we want, finally, is "there exist r and s such that ( b = rs and there exist p and t such that A and B)" (eliminating one redundant "p is prime" if you like). Note that, contrary (I think) to Hofstadter's warning that this may require "quite a bit of number theory", we only seem to need Euclid's observation that there are an infinite number of primes (so that p always exists). ==================== Now for Steve Becker's problem: Express in Hofstadter's Typographical Number Theory: " b = 10**x " The difference here, if it is not obvious, is that he wants you to identify the exponent x. I found it hard to believe that this was possible in TNT. However, it, and a lot more, can be so expressed. Unless someone else comes up with the answer, I shall post Steve's solution in about 10 days. Meanwhile, those who wish to see the solution WITH ALL THE GORY TNT DETAILS may write to him at the above address. - Gene Luks, University of Oregon
ds@warwick.UUCP (01/31/86)
Summary: Expires: Sender: Followup-To: Distribution: Keywords: Xpath: ukc eagle In article <139800001@uoregon.UUCP> luks@uoregon.UUCP writes: >This is in response to following request from Eric Postpischil: >>In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b >>is a power of 10" in Typographical Number Theory. Does anybody have a solution >>for this? >I offer an outline of my solution to this Using his hints I have arrived at (Using E for there exists, A for for all, ^ for and, v for or, I for implies) Er:Es:<b=(r.s)^Ep:Et:<<Ax:Ay:~(SSx.SSy)=p>^<<<Ec:(Sr+Sc)=p>^<<Ec:Ed:<SSd=p> ^<<t=(r+(c.d))>v<r=(t+(c.d))>>>^<Au:<Ec:Ed:<SSd=p>^<<u=(r+(c.d))>v<r=(u+(c. d))>>>IEc:(t+c)=u>>^<<Ec:(SSSSs+Sc)=p>^<<Ec:Ed:<SSSSSd=p>^<<t=(s+(c.d))>v<s =(t+(c.d))>>>^<Au:<Ec:Ed:<SSSSSd=p>^<<u=(s+(c.d))>v<s=(u+(c.d))>>>IEc:(t+c) =u>>>>> (It's only 307 chars) Now can someone check that and post any corrections? If someone can post a derivation for this string I *would* be impressed.:-) +---------------------------------+-------------------------+ | 'Anchoring on his left foot and | Douglas Spencer | | balancing poised over the talc- | Mathematics Institute | | like pulverate, testingly he | University of Warwick | | put his right foot in.' | Coventry | | Who is it? What story is this? | CV4 7AL | | What happens next? Please email | England | +---------------------------------+-------------------------+ | ..seismo!mcvax!ukc!warwick!ds | 1,29'35" W 52,25'15" N | +---------------------------------+-------------------------+
luks@uoregon.UUCP (luks) (02/03/86)
This is another follow-up to the request from Eric Postpischil: >In Godel, Escher, Bach, Douglas Hofstadter poses the problem of expressing "b >is a power of 10" in Typographical Number Theory. Does anybody have a solution >for this? In responding to Eric's request, I posted a solution that I had worked out while reading that section of GEB. It is both simple and elementary but clearly ad-hoc. As indicated, it answered Hofstadter's specific challenge: "Express `b is a power of 10' in Typographical Number Theory" but not a broader one (proposed by Steve Becker, BITNET: sbecker@bucknell): "Express `b = 10**x' in Typographical Number Theory" In fact, Steve's problem is based upon the sources that Hofstadter undoubtedly had in mind. A significant result of mathematical logic is the observation that a first-order theory based only upon Peano's Postulates seems to incorporate all the basic statements and proofs of elementary number theory. See, for example, Chapter 3 of [Introduction to Mathematical Logic, by Elliott Mendelson, Van Nostrand, 1964], especially pp 131-134 where a technique is developed for expressing any recursive function. Steve followed the recipe to obtain a solution to the second problem. ----- Outline of solution: It is easy to see that "y = mod(n,m)" is expressible in TNT, where mod(n,m) refers to the residue of n modulo m, i.e., the remainder when n is divided by m. Claim: the following statement (easy to convert to TNT) asserts "b = 10**x" "there exist c and d such that mod(c,1+d) = 1 and mod(c,1+(1+x)d) = b and for all v<x: mod(c,1+(2+v)d) = 10*mod(c,1+(1+v)d)" The proof of the claim is left as a nice exercise for the reader. Hint: the Chinese Remainder Theorem is essential. ----- Perhaps the above remarks will be deemed worthwhile by the respondents to Eric's request who commented that the problem has "limited scope and interest" and that "nobody cares about TNT" and "I couldn't imagine duller problems than DHs". Then again, perhaps not.
ladkin@kestrel.ARPA (02/05/86)
In article <139800002@uoregon.UUCP>, luks@uoregon.UUCP (luks) writes: > [...] A significant result of mathematical logic > is the observation that a first-order theory based only upon Peano's > Postulates seems to incorporate all the basic statements and proofs > of elementary number theory. See, for example, Chapter 3 of > [Introduction to Mathematical Logic, by Elliott Mendelson, > Van Nostrand, 1964] No longer true. Paris and Harrington have a formulation of Ramsey's Theorem which is unprovable in Peano Arithmetic (see Handbook of Mathematical Logic, North-Holland 1977), and much work along the same lines has been done by, particularly, Harvey Friedman (e.g. Kruskal's Theorem is unprovable in Peano Arithmetic). *Result* is an unfortunate choice of words. Peter Ladkin