What are the prerequisites for studying mathematical logic?

I am looking to study mathematical logic, however, I find that introductory books are very daunting, which kind of disheartens me. You see, slowly but surely, I started to realize that the maths which I have learned did not just pop out of thin air, but is a collection of systems, which must of been developed via some other system, i.e, maths did not develop itself.

So I began to look into the origins of mathematics, and read that it was developed via a type of logic, which exists sort of by 'default', via a set of axioms, and then of course I looked up the definition of axioms.

So given that I'd be studying a type of logic whose origins are self evident axioms, naturally I believed there would be no prerequisites. However, in looking up mathematical logic, I have come across things such as Boolean algebra, sets, first order logic, some other type of logic, called 'traditional logic', as well as references to a sort of calculus, though not in a mathematical sense, I think.

So all in all, I am trying to develop a type of mental spider web, and I am trying to find out the strands which lye at the absolute bounds so that I may learn this mystique logic. Though I have no idea where to start.

Side note: This is the book I have started reading: http://www.dainf.cefetpr.br/~kaestner/Logica/MaterialAdicional/announceRautemberg.pdf

Credit goes to Wolfgang Rautenberg.

Solution 1:

If you have mathematical background, I recommend Hannes Leitgeb's Mathematical Logic lecture notes, which introduces modern first-order logic up to Godel's first incompleteness theorem, with a conventional kind of deductive system, and has exercises and solutions.

Another good reference is Stephen Simpson's Mathematical Logic lecture notes for his Math 557 course, which covers some basic model theory and proof theory. Stephen uses an unconventional deductive system, and so his proof of the semantic completeness theorem is also different from the conventional.

If you just want to know precisely how to perform absolutely rigorous logical reasoning in practice, I strongly recommend learning this programming-inclined variant of Fitch-style natural deduction. There are many reasons for this. Firstly, it is practical, unlike many deductive systems that are easy to analyze but totally impractical to use (such as Hilbert-style or tree-style systems). Secondly, it is quite self-explanatory (every logician can understand it even without knowing it). Thirdly, its use of restricted quantifiers makes it much more intuitive and user-friendly than standard first-order logic with unrestricted quantifiers.

The best alternative I have found as of today is in Language, Proof and Logic (see sections 6,13 on "Formal Proofs"). This system is also a Fitch-style system. In my opinion, its ∃-elim mechanism is not convenient for practical use, compared to mine. But its main deficiency is that it does not have restricted quantifiers. Incidentally, this issue also shows up in non-conventional quantifiers (section 14.4), which are most naturally viewed as special restricted quantifiers.

If you have a bit of programming background, you might enjoy reading simple computability proofs of the generalized syntactic incompleteness theorem, which are based on a very neat idea from Stephen Cole Kleene's Mathematical Logic. A more conventional approach can be found in Peter Smith's excellent Godel without tears that also includes a bit about provability logic.

For a really concise reference that covers quite a lot of stuff that is not covered by the others, I recommend A Concise Introduction to Mathematical Logic by Wolfgang Rautenberg, but this is not so suitable for a first introduction to logic.

Solution 2:

I would recommend starting with expositional material and history, coupled with some introductory maths textbooks. The history will give you context and you might start to see how there hasn't been a linear progression of mathematics from some pure logic to now - rather, our current formal logic is a fairly recent attempt to be more confident in the foundations of our mathematical intuitions.

Then the exposition will give you insight into what mathematical logic is, without you having to grapple with whether you personally can do it. But all of this will be too vague unless you really try and do maths. I think that's what the comments are getting at - you just need to immerse yourself in the world that is maths to see how it all fits together. The links in the spider web are many and diverse, and impossible to see from the outside.

I would recommend starting with early attempts at logic and foundations, such as Euclid's Elements - this was the start of it all. Also consider doing set theory, as lots of logical issues were attempted to be resolved by it - a good exposition is 'Logicomix' - Apostolos Doxiadis.

To find a real example of fairly modern axiomatics, try reading Paul Halmos' 'Naive Set Theory'; this is a well-written and well-explained use of axioms to build a theory.

Best of luck - in such a venture, rather than finding the best starting place, I would simply recommend that you start. Once you're in, you can start to navigate.