[FOM] "Literal"

William Tait williamtait at mac.com
Sun Sep 10 09:51:20 EDT 2006

I blush to confess: I misremembered. In my 1967 paper and a later one  
on partial cut-elimination in the Buffalo conference I used the term  
"atomic".  That is because in those papers I thought of formulas as  
not containing negation (so that atoms come in complementary pairs).  
In later papers, I was anxious to emphasize that the proof theory of  
these negationless propositions applies directly to formulas in the  
usual sense and so wanted to distinguish atomic and negated atomic  
while having a term for both. So  I have used the term "prime" in  
lectures on proof theory and in later papers---e.g. the recent BSL  
paper "Goedel's reformulation of Gentzen's consistency proof for  
arithmetic and the no-counterexample interpretation". (Anyway, in my  
heart I always knew they were prime, not atomic.)


On Sep 9, 2006, at 2:31 PM, Charles Silver wrote:

> William Tait wrote:
>> I have used the term "prime" for atomic and negated atomic  
>> formulas---
>> e.g. in my paper "Normal derivability in classical logic" in 1967,
>> and so not predating the Quine and (shame on you Martin) Davis-Putnam
>> strange use of the term "literal". The motivation was (is) that the
>> composite formulas are built up from the prime ones by means of the
>> lattice operations of disjunction, conjunction, and the quantifiers
>> (if we identify formulas with their De Morgan equivalents).
> 	Great!!  To me, "Prime" seems so apt a term for its denotation as  
> to override the history of "literal".  I'm also glad to read that  
> "prime" is enshrined in one of your publications (even though it  
> does not precede Quine's).   The only doubt I had when I first read  
> the above was that Quine and everyone else in c.s. who uses the  
> Quine-McCluskey algorithm also use "prime implicant" (for a totally  
> different) concept.   However, what links the two uses of "prime",  
> it seems to me, is that they're both fundamental building blocks of  
> a sort, just as prime numbers are the fundamental building blocks  
> of the integers.
> 	I want to thank everyone who's replied to my query.   I appreciate  
> all the responses.
> Charlie
> P.S.  It's odd, isn't it, that such a wordsmith as Quine would use  
> the term "literal".   I don't get it.

More information about the FOM mailing list