[FOM] Formation Rules

Alasdair Urquhart urquhart at cs.toronto.edu
Fri Oct 20 13:05:21 EDT 2006

John Corcoran asked:

" I would like to know when logicians started thinking of formal
 languages as subsets of the set of finite strings over a finite
alphabet, which of course is what they are.

This conception of what formal languages are is not so obvious, not if
"what they are" is meant in any but a very weak sense."

An early source for this idea is in C.I. Lewis's " A Survey of Symbolic
Logic" published in 1918.  In his sixth chapter,  Lewis contrasts the logistic 
method of Whitehead and Russell with what he calls a "heterodox" view of the 
nature of mathematics and logistic.

Lewis presents his view of the logistic method in the
following striking definition:

	 A mathematical system is any set of strings of recognizable
	marks in which some of the strings are taken initially and the 
	remainder derived from these by operations performed according to
	rules which are independent of any meaning assigned to the marks.

and he goes on to present the propositional calculus of Principia Mathematica
as a mathematical system in his sense.  

This Chapter 6 of Lewis's Survey had a very strong influence on Emil Post.
Unfortunately, when the book was reprinted as a Dover paperback in 1960,
Lewis chose to omit this chapter.  Consequently, this historically influential
chapter is now rather hard to access.

Alasdair Urquhart

More information about the FOM mailing list