Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!ucsd!sdd.hp.com!uakari.primate.wisc.edu!samsung!uunet!wang!wiis.wang.com!bnh
From: bnh@wiis.wang.com (Bill Halchin)
Newsgroups: comp.theory
Subject: Math Logic
Summary: Provability ala Boolos/Jeffrey
Keywords: proof model
Message-ID: <1990Aug3.162306.29574@wiis.wang.com>
Date: 3 Aug 90 16:23:06 GMT
Distribution: sci.logic
Organization: Wang Laboratories, Inc
Lines: 13

Recently, I have been reading a number of books on mathematical logic, e.g.
Kleene's Intro to Metamathematics, Cohen's Computability & Logic. These
books take the usual formalist approach of the concept of provability, i.e.
pure symbol manipulation involving a recursive set of axioms & a set of rules
of inference. However, I have also been reading the book Computability & Logic 
by Boolos & Jeffrey (Cambridge), which seems to be an excellent book with
recent results like Chaitin's work on algorithmic complexity. One thing confusesme though. In Boolos & Jeffrey, the notion of provability is tied to model theory, i.e. it's tied to semantics not syntax. A theory is the set of sentences closed under logical consequence. Logical consequence in their book is a semantical
concept, i.e. A -> B iff for every model M of A & B, if A is true, then B must
be true. I don't understand the connection between Boolos/Jeffrey concept of
a theory(set of theorems) and the usual approach, e.g. Kleene or Goedel? Can somebody please help to understand this?? Thank you.


   Bill Halchin