Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: notesfiles
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!decwrl!pyramid!hplabs!hp-pcd!uoregon!luks
From: luks@uoregon.UUCP (luks)
Newsgroups: net.math
Subject: Re: Godel-Escher-Bach ans. + new problem
Message-ID: <139800002@uoregon.UUCP>
Date: Sun, 2-Feb-86 17:12:00 EST
Article-I.D.: uoregon.139800002
Posted: Sun Feb  2 17:12:00 1986
Date-Received: Fri, 7-Feb-86 20:21:41 EST
References: <139800001@uoregon.UUCP>
Organization: Univ of Oregon - Eugene, OR
Lines: 53
Nf-ID: #R:uoregon:139800001:uoregon:139800002:000:2084
Nf-From: uoregon!luks    Feb  2 14:12:00 1986

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.