[FOM] Re: FTGI1:Classical Propositional Calculus

[Martin Davis]

Below I review briefly the way I used to introduce the propositional 
connectives and their properties in my graduate level introductory 
mathematical logic course at the Courant Institute. This was a 30 hour 
one-semester whirlwind exposition of Goedel's completeness & incompleteness 
theorems with Hilbert's 10th problem (to make proofs of representability of 
recursive relations easy) en route. I could assume that my students had 
some mathematical sophistication, but zero knowledge of logic.

I wanted a development that would make the truth tables (especially for --> 
) seem a natural development and not some ad hoc thing one began with. What 
I came up with was not the sort of fundamental 
begin-at-the-beginning  approach that I believe Harvey seeks, but I think 
it does answer some of his questions.

I begin with a kind of structure I call a LOGIC of the form <E, |- > where 
E is a non-empty set and |- is a relation between subsets of E (which I'll 
designate with capital letters) and elements of E (which I'll designate by 
lower-case letters) satisfying:

L1. {a} |- a.

L2. (Monotonicity) If A |-a and A is a subset of B then
B |- a.

L3. (Compactness)  If A |- a then there is a
finite subset B of A, such that B |- a.

L4. (Cut)  If A |- a and B u {a} |- b
then A u B |-b.

Next, a BOOLEAN LOGIC is a structure <E, |- , --> , f > where <E, |-> is a 
logic, --> is a binary operation on E, and f is an element of E satisfying:

B1. A u {a} |- b if and only if A |- a --> b
B2. (a --> f) --> f |- a

I suggest that B1 encapsulates the reason that --> plays a fundamental role 
in mathematics. If I remember correctly in PRINCIPLES OF MATHEMATICS, 
Russell defines "pure mathematics" as dealing with propositions of the form 
p --> q. A sense in which something like this is true is that there are 
always axioms whose conjunction serves as the antecedent of implications. 
So one is always proving such implications and B1 gives the typical method: 
take the antecedent as premise and derive the consequent. B2 (double 
negation) is of course much more dubious. E.g. it doesn't hold in 
intuitionistic logic. But it does encapsulate proof by reductio ad absurdum.

Next: where are these structures to be found? Well there is obviously a one 
element Boolean logic, but it is pathological (because |-f), or as we say, 
inconsistent. What is the smallest consistent (and all the usual 
definitions of consistency are equivalent) Boolean logic? It is the unique 
2 element Boolean logic with E = {f, t = f -->f}, and the --> operation is 
compelled to be given by the usual truth table.

Finally, for any Boolean logic, we can study homomorphisms into this 
2-element logic and easily prove that if every such homomorphism that maps 
all elements of A into t also maps a into t, then
A |- a. Quantificational logic, first order theories, etc. then are seen as 
particular Boolean logics so that the proof methods of the classical 
propositional calculus are automatically embedded in them.


                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com