# 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.

Credit goes to Wolfgang Rautenberg.

• it helps to deep into the classical formal system like 1) Euclidean Geometry, 2) Group's Theory, 3) Vector Space's Theory, 4) Real Analysis and 5) Topology. There, you'll find the right arena of logic's heuristics and applications – janmarqz Dec 15 '15 at 17:43
• Not exactly what you are asking for, but you might also be interested in axiomatic set theory. – Gyro Gearloose Dec 15 '15 at 17:44
• This has been asked in several incarnations on this site - did you locate any of them? – Carl Mummert Dec 15 '15 at 20:59
• To get you started, may I humbly suggest the tutorial that comes with my free proof-checking software. It will introduce you to basic methods of proof, symbolic logic, predicate logic and elementary set and number theory that have been simplified to meet the needs of the mathematics undergrad. Visit my website at dcproof.com. There, you will find, a list of features, testimonials, video demo and a free, full-function download. Using it, you will probably get off to a quicker start writing mathematical proofs (if that is your goal) than with any book devoted to logic or set theory. – Dan Christensen Dec 21 '15 at 4:54
• Hey Dan Christensen. I don't know how, but I must of missed you're comment. Thanks for telling me about your program. I'll be sure to check it out, and when I do i'll email you. That will probably be a few months from now though, as I need to finish up on my logic :) – Jim Jam Mar 7 '16 at 0:19

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. Fourthly, I have been unable to find online a freely available correct precise description for a practical deductive system for full first-order logic.

The best alternative I have found as of today is Stanford's online introduction to logic, but it chose to use complicated existential-introduction/elimination rules. That system will become a bit more usable if you replace those two rules by the following rules:

$\begin{array}{lll} P[t] \\\hline \exists x ( P[x] ) \end{array}$   where $t$ is a term and $x$ does not occur in $P[t]$.

$\begin{array}{lll} \exists x ( P ) \\ \forall x ( P \to Q ) \\\hline Q \end{array}$   where $x$ does not occur in $Q$.

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.

• @user108262: Yes I spent a long time trying to find good references that start from scratch and don't assume that their readers already know a lot of mathematics. I somehow learnt logic on my own but I wanted to be able to tell others where to start! – user21820 Mar 5 '16 at 14:57
• Just wanted to say thank you again for the book. I was 2 days deep into another book about logic, and I don't think in comparison, that the book went into enough detail. The book you provided, though more detailed, bears more intellectual fruit = better. Anyway, you gave the greatest type of gift that one could give, so thanks :) – Jim Jam Mar 7 '16 at 0:08
• @OppaHilbertStyle: I have just read snippets from the two books you asked about. It seems to me that the one by Tarski it is not helpful to people who have weak logic background. The one by Robert et al. has a good explanation of symbols and references, though their attempt to tie logic to English examples result in many parts that are misleading or even downright wrong. So neither of them get my recommendation. – user21820 Dec 13 '16 at 7:06
• I originally recommended Introduction to Logic by Patrick Suppes for very basic introductory material, but it uses old notation and is hard to search. Future readers might still be interested in some interesting bits (like section 8.5 on division by zero). – user21820 Jul 4 '17 at 10:51
• @BillyRubina: I changed my mind after a closer look revealed what I would consider as errors (wrong if interpreted in the natural way). This was after a few people tried studying it and asked me about it. The errors were not obvious on first glance. In any case, come to the Logic chat-room for any inquiries you may have, and I'll be glad to help you. =) – user21820 May 26 '18 at 16:15

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.

• Hello Alexander, thank you very much for your advice and recommendations. I'll pick up a copy of that book, 'Naive Set Theory', that you recommended, and I think you're certainly right in that one should not find an 'ultimate starting point', but to just start somewhere appropriate in which one can start to navigate; good advice! – Jim Jam Dec 21 '15 at 18:47

This is an old question, butlet me plug my favorite logic textbook: "Computability and Logic" by Boolos, Burgess, and Jeffrey. As the name implies, it has a strong computability-theoretic focus which you may not be interested in; however, it also has a self-contained treatment of first-order logic logic (chapters 9-10 and 12-14) which I found the clearest by far of the books I had access to when I was first learning this stuff. Its presentation of Godel's theorems (chapters 11 and 15-18, building on chapters 1-4 and 6-7) is also excellent, in my opinion. (And besides, computability theory is really cool.)

It ends with a collection of further topics; some of this material is usually only covered in more advanced and specialized courses, but it's actually quite accessible, so it's nice to have it in one place in a more introductory text. I'm not sure I would have chosen those exact topics to include rather than others, but it's certainly a reasonable selection.

• I too certainly recommend anything written by Boolos! And yes I love the computability viewpoint applied to proof theory. =) – user21820 Mar 9 '18 at 15:48
• This also is always my first suggestion. Very well written. I plug it in logic chat all the time. – David Reed Apr 23 '18 at 4:57