8

What comes after an introduction to Mathematical Logic? Also, Where would Formal Language Theory stand among the other four branches of Mathematical Logic (listed in the title)?

JimmyJackson
  • 1,517
  • 3
    You can probably learn each one with knowing just very little on the others. I, for example, know almost nothing about proof theory and just very very very little about recursion theory, and only the "pre-Shelah" part of model theory. – Asaf Karagila Oct 11 '13 at 06:43
  • 1
    Could you explain what you mean by "Formal Language Theory"? It sounds to me like you are talking about something from computer science (e.g. the Chomsky hierarchy) - is that right? – Carl Mummert Oct 11 '13 at 10:46
  • 1
    @CarlMummert Perhaps I used the title Formal Language Theory erroneously, what I want to say is in logic we discussed logic as an object language using a metalanguage (mathematical English). And we discussed that our object language has an alphabet, connectives, rules for forming wfs, rules of inference (and I think i am missing some other aspects). By Formal Language Theory, I was referring to the construction of a formal language. – JimmyJackson Oct 11 '13 at 18:42

3 Answers3

6

It depends on what your goals are. If you have a basic introduction to logic (e.g. Enderton's book or the book by Boolos, Burgess, and Jeffrey), you have the background to learn significant amounts of each of the four areas.

One thing most general introductions to logic lack is a solid background in basic set theory, particularly ordinals and cardinals. A nice book like Halmos' Naive Set Theory (undergraduate level) or the first couple chapters of Kunen's Set Theory (graduate level) will remedy that. In particular, you need to be relatively comfortable with ordinal and cardinal arithmetic, proofs by transfinite induction, and with the distinction between $2^{\omega}$ vs. $\omega_1$, in order to digest many mid-level results in model theory and proof theory.

Carl Mummert
  • 81,604
  • What do you think about the book The Theory of Sets and Transfinite Arithmetic by Alexander Abian? According to Wikipedia he had some weird theories before he passed away, but I find that his book reads very well (in the since that he has good grammar and thought formation). – JimmyJackson Oct 11 '13 at 19:03
  • 2
    Note that the current (2011) edition of Kunen's Set Theory has been reorganized. The material on basic set theory no longer appears in this text but has been moved to a companion volume by the same author, entitled The Foundations of Mathematics. Both volumes are now available as inexpensive print-on-demand paperbacks. I've just finished reading the set theory chapter in Foundations and would also recommend it. – Nate Eldredge Apr 29 '14 at 14:32
4

Have a look at the Teach Yourself Logic Study Guide which, among other things, has a map of how the elements of the standard math logic curriculum fit together, and gives a lot of reading suggestions to explore.

http://www.logicmatters.net/tyl

That will reveal that, once you have nailed down the basics of first-order logic and elementary model theory (so you know about the ideas of e.g. a formal language, a formal deductive system, an axiomatized formal theory, completeness, compactness ...), you can branch off in various directions without worrying a great deal about the others, at least at the outset. For just one example: enthusiasts for recursion theory may need to know very little set theory -- and likewise the other way about (as Asaf commented as I was typing this, you can be a serious set-theorist while knowing very little recursion theory.)

Peter Smith
  • 54,743
  • 1
    I think this understates the relationships between the fields. It is true that, at the middle level, one can make a lot of progress in learning any one area with only a basic background in the others. But, for example, descriptive set theorists must know significant amounts of hyperarithmetical theory, and classical recursion theory includes set theoretic topics such as Turing degree determinacy. Proof theory often studies systems where recursion theory is vital (e.g. reverse math and constructive math). So, at the research level, the relationships become important again. – Carl Mummert Oct 11 '13 at 10:45
  • Oh yes, @CarlMummert, I wouldn't dissent at all from that. I was assuming the OP was at no more than "the middle level" ... – Peter Smith Oct 11 '13 at 12:35
  • @PeterSmith Thanks for this resource! I will give a more thorough read after I finish my homework. But, I definitely agreed with the review of Mendelson, it look much more difficult than it is. However, I don't find it to be too dry I have become accustom to his typography, and the exercises are fun. – JimmyJackson Oct 11 '13 at 18:59
1

I recommend Carnap's "Introduction to Symbolic Logic and its Applications". It is quite a bit more advanced than a normal 'introductory' text. He introduces simple type theory, and higher-order logic. It is a good book to transition from basic logic into more advanced topics.

Nino Cocchiarella
  • 11