Saturday, August 23, 2008

From Logic and Structure

Amazon has been telling me repeatedly that a new edition of Dirk van Dalen's Logic and Structure is coming out soon, so I thought I'd look at an older version. I picked up a copy of the third edition. The opening of the preface is too good to pass up, if one ignores the run-on sentences:

"Logic appears in a 'sacred' and in a 'profane' form; the sacred form is dominant in proof theory, the profane form in model theory. The phenomenon is not unfamiliar, one observes this dichotomy also in other areas, e.g. set theory and recursion theory. Some early catastrophes such as the discovery of the set theoretical paradoxes or the definability paradoxes make us treat a subject for some time with the utmost awe and diffidence. Sooner or later, however, people start to treat the matter in a more free and easy way. Being raised in the 'sacred' tradition my first encounter with the profane tradition was something like a culture shock. .. In the course of time I have come to accept this viewpoint as the didactically sound one: before going into esoteric niceties one should develop a certain feeling for the subject and obtain a reasonable amount of plain working knowledge. For this reason this introductory text sets out in the profane vein and tends towards the sacred only at the end."

I don't have any comment on the book's contents as I haven't slogged through it. The brief chapter on second-order logic makes an interesting point though. It shows how all the connectives of classical logic can be defined using just → and ∀, although this does require both first- and second-order quantifiers. The book obscures this fact in the statement of the theorem. This isn't surprising once one sees the proof, but it is still neat.

3 comments:

Rafal Urbaniak said...

As for the definability of connectives using only one connective together with a universal (propositional) quantifier, there's a fairly well-known result of Tarski from his 1923 dissertation `On the primitive term of logics', included in Logic, Semantics, Metamathematics. Although, there might be some interesting differences. What do the definitions you talk about look like?

Shawn said...

Thanks, I wasn't aware that Tarski had that result too. The definitions in the van Dalen book are (I don't have a lot ): define ⊥ as ∀A(A). Then use that and → to define negation and the other connectives as expected. Then use those to define the existential quantifier out of the universal, as usual.

Rafal Urbaniak said...

yeah, so that's pretty much the same trick. As far as I remember T. didn't go via the falsum. He defined ~A as (A-> (A)A), but that's a minor difference.

Although, I wouldn't say `had that result too'. I'd rather say that the whole idea simply is Tarski's.:P

Anyway, thanks, I didn't know anyone actually talked about this stuff in a modern textbook!