[FOM] Arithmetic-free theory of formal systems?

[Dennis E. Hamilton]

In <http://www.cs.nyu.edu/pipermail/fom/2004-May/008206.html>
Tim Chow asks "... Is there a way of developing a
theory of formal systems without any reference to arithmetic?"

Take a look at Raymond Smullyan's "Theory of Formal Systems."  It is one of
the Princeton Annals publications (No. 47, 1961), and I see that it is still
in print, <http://pup.princeton.edu/titles/2398.html>.

There is also a (JSL?) piece from it on Elementary Formal Systems.

He uses

	E11
and	Ex -> Ex11

as an example of you-know what.  I don't have a copy any longer so I can't
tell you if he comes closer to what you are talking about.  He does get to
undecidability and I don't recall how he does the "arithmetization" of the
formal system.

I like the above example (and your two) because, in formal terms, they are
each, taken separately, indistinguishable from this one:

	N0
	Nx -> Nx'

Now, looking at Tim's questions, how is it we are willing to believe that,
taking the scheme as a generation rule, duplicates are never produced and
there is no end to the sequences that satisfy N?  Have I presumed numbers?
Where?

PS: Amazon.com even has a listing for the book, and there was this wonderful
example of natural language processing when I looked: "Customers interested
in Theory of Formal Systems (AM-47) may also be interested in: Dresses at
Macy's ... ."

 - orcmid
-------------------------------
Dennis E. Hamilton | KIT eLearning student | University of Liverpool on-line
M.Sc in IT
mailto:Dennis.Hamilton at Liverpool.ac.uk | gsm:+1-206.779.9430
http://orcmid.com | http://nfoWare.com | http://Miser-theory.info
OpenPGP public key fingerprint BFE5 EFB8 CB51 8781 5274  C056 D80D 0C3F A393
27EC