So it looks like you're interested in learning the fundamentals of classical logic and set theory, and then paving your way towards measure theory. If you don't have a solid background in set theory, then you probably don't have a strong background in real analysis either, which to my understanding is needed for measure theory. (I don't know how you can do measure theory without even knowing what the Riemann integral is).
You should take a look at Real mathematical analysis by Pugh. You're going to need to know basic stuff like basic set theory and functions and such as a prereq, but it's a very lucid introduction to real analysis with metric space topology and compactness and connectedness and all that. It was the first book I found that had a good explanation of Dedekind cuts (Rudin's Principles of Mathematical Analysis has a very terse description. Pugh, on the other hand, has pictures!)
For measure theory, I haven't read very far through them but here is a 4-volume set on Measure theory available for free online from D.H. Fremlin. It has some introductory set theory stuff if I recall, which might be a good starting point if your grasp on logic is strong enough.
For basic logic, How to Prove It: A Structured Approach by Velleman is my personal favorite.
Cohn's Measure Theory is good for measure theory. Rudin's Real and Complex Analysis is more standard, but less gentle, in my impression.
Measure theory is good to know, but it's quite different from set theory and logic, and doesn't require you to know them. You don't necessarily have to learn it last, and from my perspective it's easier and you should learn it first. It's certainly the "foundation of some maths" in the sense that it's a fundamental tool in analysis, but most of the time I think people use "foundations of math" to refer just to set theory and logic.
Can you say why you think it should be learned first? The measure theory I have seen seems to always involve sets (measurable functions, sigma-algebras etc), maybe I am just confused about something.
Of course it involves sets, but the kind of set theory you need for that is rather limited, because measure theory deals with very special cases, compared to which set theory proper looks pathological. So, it's a prerequisite to know about countable and uncountable, union and intersection, open and closed and compact, but not the contents of a course in set theory, which gets quite a bit more complicated. I know very little set theory and never studied logic.
Edit: nhamann is right, you need a first course in analysis before you'll understand measure theory. I used Rudin, but I'm not partisan in favor of it. But you've got to learn analysis first. Or you will get confused. Do not pass Go, do not collect $200.
The thing about foundations is that they're mysterious, even at the research level, but when you're working on classical special cases it doesn't matter. In the same way that you can do arithmetic even though you can't prove the axioms of arithmetic are consistent. Measure spaces are very much nicer than sets. And often it's safe to think of the reals as a guiding example. In set theory, thinking of familiar sets as guiding examples is dangerous, which is why I think it's a harder subject, but that may be my idiosyncrasy. The point is, measure theory and set theory are independent from the point of view of the learner -- learn whichever you like first, but one isn't a prerequisite for the other.
A very excellent recent book, with fascinating new ideas and superior readable intros into many themes, is the new edition of Manin's "course in mathematical logic". So I'd recommend that. But: Why "foundations"? Like "foundational themes" in th. physics, "foundations" are not an appropriate place to start, they are a bundle of very advanced research areas whose intuitions and ideas come from core fields of research. "Foundations" in the sense of "what is it, really?" can be exprerienced probably much better by studying a good piece of core math, like number theory. Cox' "Primes of the form x^2 +n*y^2" or Khinchin's "Three Pearls of Number Theory" is what I would suggest. If your mind prefers geometry, I'd suggest to browse a good library for some of the great projective geometry textbooks from the early 20th century.
Principles of Arithmetic and Geometry by Carl Allendoerfer
If you are looking for a book that begins before even numbers begin, then this is it.
The book starts with basic logic, then moves to define basic set theory very clearly, then proceeds to explain how set theory is the foundation of our whole number system, and finally moves to defining all elementary operations using what you've learned. He goes into great depth of defining all the various kinds of correspondences, cardinality, and other crucial ideas that usually get ignored early on.
Allendoerfer stresses the importance of developing abstract thinking and really makes you feel confident and excited about the abstract nature of mathematics, rather than hinging to real world examples. The truth is that, in order to be a useful mathematician you must be comfortable and skilled with abstract thinking. Whereas most professors shy away from this and want you to wait until much later to develop these skills, Allendoerfer makes it very clear that, no matter what your age is or experience, you are ready to think abstractly about nature and about mathematics.
Every chapter is full of exercises with all answers provided, as well as a test at the end of each chapter and recommendations on what to do if you struggled.
I have yet to find any book that does such a good job at explaining these foundations as Allendoerfer. This book is a god-send for those of you out there that are trying to self-teach mathematics, especially modern mathematics, and are willing to begin at the beginning. (Arithmetic is NOT even the beginning!)
When this book is completed, I highly recommend his Freshman Mathematics book and also his Principles of Modern Mathematics.
Perhaps not, but one of the topics I am interested in (probability) relies on it. Maybe foundations of math refers to something more technical than I knew, but measure theory is the foundation of some maths, right?
The problem with that reasoning is that all theories are the foundation of some maths. Your post is probably better titled "Learning the fundamentals of math" as opposed to "foundations", which evokes things like metamathematics and logic and computability foundational issues.
Note: Before reading my comment, I don't know jack shit about mathematics and much else. I'm still struggling with basic algebra. But I've got the same questions as you and compiling a lot of stuff to educate myself. Here are some ideas and links.
One of the most important concepts for the foundations of mathematics is recursion. Naturally, you'll have to fall back on some circular definition if you seek answers without dissent, progress ad infinitum or assumption. That is, you have to rely on a recursive axiomatic definition (e.g. factorial n = if n == 0 then 1 else n * factorial (n - 1)). I was told that learning a functional programming language like Haskell can be very helpful.
Addition Recursively:
Let n' be the successor of n, that is the number following n in the natural numbers, so 0'=1, 1'=2. Define a + 0 = a. Define the general sum recursively by a + (b') = (a + b)'. Hence 1+1=1+0'=(1+0)'=1'=2.
Addition Set Theoretic:
Let N(S) be the cardinality of a set S. Take two disjoint sets A and B, with N(A) = a and N(B) = b. Then a + b is defined as N(A U B).
That's from Wiki: http://en.wikipedia.org/wiki/Addition#Addition_of_natural_and_real_numbers
Some sentence I found really interesting is the following by Eliezer Yudkowsky:
A decision procedure is a finite specification of all truths of euclidean geometry; I can use that finite fact anywhere I could use any truth of geometry.
If you go outside of mathematics into decision theory and programming you'll be able to create finite statements as a kind of infinite workaround to Gödel's incompleteness theorems.
So I have no idea about measure theory but it sounds like some top-level concept, not what you want right now but something you'll have to get back to later to prove the consistency of other concepts.
Well, I've no clue but that sounds right right now ;-)
More links:
(I've links and stuff about a lot of fields, just ask if you need something.)
This LW thread seems relevant.
In particular this summary of resources has sections on logic and foundations. There's a little bit of difference between that thread topic and my topic, which is that I am interested in learning the fundamentals of math for themselves (and doing further math) rather than only LW relevant math.
The links I posted in that thread are, to my knowledge, the best free online resources. If you go through Cook's lecture notes, and then continue with the foundations text by Podnieks, it will be pretty much what you're looking for, up to and including the basics of set theory. I'm not familiar with literature in measure theory, though.
Regarding your stated preferences, I'm not sure if you can find math textbooks that use formal context-free grammar to define well-formed formulas. However, it's typically done using recursive definitions that are trivial to formalize as CFGs, so it shouldn't be a problem. In addition, I don't understand what benefit you see in formalizations of propositional logic with only two operators. It will just complicate the exposition and make it less understandable. (And why stop there? You can do it with only one.)
Your road map is helpful. Thanks :)
I didn't mean to say that you couldn't use what you had derived later on, but if you can define a theory with with 1 operator, why do it with more? Is there a formal concept of an alias in math (for example, "a implies b" could be an alias for "(not a) or b")?
jsalvatier:
I didn't mean to say that you couldn't use what you had derived later on, but if you can define a theory with with 1 operator, why do it with more?
Because it's far easier to work that way. You don't need ten different digits to work with natural numbers either, but we still do it for convenience. When you see the formula (p&q)->r, it's much easier to figure out what's going on than if it's in the form ((p|q)|(p|q))|(r|r). (Here "|" is the Sheffer symbol, i.e. NAND, which is by itself functionally complete.)
Is there a formal concept of an alias in math (for example, "a implies b" could be an alias for "(not a) or b")?
Math texts often introduce some notational aliases to make the text more readable, and logic texts do it almost invariably. For example, in the standard syntax of first-order logic, "+" is a binary function symbol, and "=" is a binary predicate, but it's still customary to introduce easier to read notation "x+y" and "x=y" where it should be "+xy" and "=xy". However, these conventions don't have any implications for the actual results being proven and discussed; the theorems still talk about formulas containing "+xy", and you just translate on the fly between that notation and the intuitive one as necessary.
In contrast, introducing additional operators into your definition of logic formulas changes things significantly, since now all your proofs have to account for these additional sorts of well-formed formulas, and also the formal proof system you use must be able to handle them. On the other hand, a good choice of a non-minimal functionally complete set of operators will make the entire work much easier to handle. So in practice, a non-minimal set is normally used. You can also use notation conventions like p->q instead of (~p v q) as long as their relations with the formal syntax are clear and simple enough. (Which definitely wouldn't be the case if you based the entire logic on just NAND and then tried to define AND, OR, etc. as notational aliases.)
I hope I am not imposing, but Cook's notes have confused me. The first set introduces a syntax which is fine, but then it introduces semantics and starts using several terms that haven't yet been defined (iff, maps and sets) are these part of meta-theory and conceptually different from being part of propositional logic? What am I missing?
Yes, these are concepts from the meta-theory, i.e. the language in which you speak about the formal logic you're defining. When you define, say, sets of formulas, or maps (i.e. functions) from atoms to truth values, these objects exist outside of the formal system (i.e logic) under discussion.
Now of course, you can ask how come we're talking about sets (and functions and other objects which are sets), when we're just defining the formal logic we'll use to axiomatize the set theory. The answer is that you have to start from somewhere; you can't start speaking if you don't already have a language. For this, you use the existing mathematics whose logical foundations are imperfectly formalized and intuitive. This trails off into deep philosophical issues, but you can look at it this way: before embarking on meta-mathematics, imperfectly formalized mathematics is the most rigorous logical tool available, and we're trying to "turn it against itself," to see what it has to say about its own foundations.
Does one need meta-theory to work from propositional logic to set theory? Can I safely ignore those parts (perhaps coming back later) if my goal is to learn do theory and not to say something about theory?
The meta-theory parts, so that I am learning just how to make proofs in theory X (e.g. propositional logic), and not learning how to prove things things about theory X proofs. Introduction to Mathematical Logic claims that all theories can be formalized; learning how to work in a theory first and then later possibly coming back to learn how to prove things about proofs in that theory seems like a good way to avoid being confused, and that's largely my goal. Does that clarify?
That depends on what you want to use formal logic for. If you just want some operational knowledge of propositional logic for working with digital circuits, then yes, any digital systems textbook will teach you that much without any complex math. Similarly, you can learn the informal basics of predicate logic by just figuring out how its formulas map onto English sentences, which will enable you to follow its usual semi-formal usage in regular math prose. But if you want to actually study math foundations, then you need full rigor from the start.
Perhaps there is some confusion about what it is precisely that you want to learn. Could you list some concrete mathematical problems and theories that you'd like to understand, or some applications for which you'd like to learn the necessary math?
This mostly started because I was trying to learn stochastic differential equations and to a lesser extent topology. I became unsatisfied with my understanding of set theory (not sure how to answer questions like "when I construct a set, what am I iterating over?"), and to a lesser extent measure theory. When I went to get the foundations of set theory, I realized I wasn't even very familiar with first order logic, and I continued down the rabbit hole.
At the moment I am not especially interested in questions like "is this theory consistent". I am primarily interested in how one does the fundamental theories of math in a way that bottoms out, meaning I can see and enumerate the notions or procedures I am just taking for granted or defining. If propositional logic was just constructing a specific context free grammer and saying statements constructed in this manner are called 'proofs' for this grammar I think that would satisfy me (though it doesn't look like this is all logic involves). I could easily be using the phrase "foundations of math" incorrectly; please tell me if I am.
Then foundations texts are not what you're looking for. If I understand you correctly, you seem to be confused about the way sets and other basic constructs are used in normal mathematical prose, and you'd like to learn formal logic and formal proof systems, and then use this knowledge to tackle your problem.
Unfortunately, that's not a feasible way to go, because to learn metamathematics, you first have to be proficient in regular mathematics -- and even when you learn it, it won't help you in understanding standard human-friendly math texts, except insofar as the experience improves your general math skills. Moreover, formal set theory is about esoteric questions that are very rarely relevant for non-foundational areas like differential equations, in which informal naive set theory is nearly always adequate. (In topology you might run into foundational issues, depending on what exactly you're after.)
So, what you really need is an introductory text about classical mathematical reasoning. I'm not familiar with any such books in English, but the book nhamman recommended (How to Prove It) seems to be exactly what you're looking for, judging by the Google preview.
Thanks for your help, I think you've clarified a lot for me.
Would you classify propositional logic/first-order-logic as necessarily metamathematical?
I'm not sure what you mean by "necessarily metamathematical."
Propositional logic isn't powerful enough to be of that much use in metamathematics. Its main applications are technical. Most notably, it's the fundamental basis for digital systems, but it's also used in various methods for optimization, formal verification, etc. Consequently, it also has huge importance in theoretical computer science.
First-order logic, on the other hand, is principally a tool of metamathematics. Sometimes it's used in a semi-formal way as a convenient shorthand for long and cumbersome natural-language sentences. But its principal applications are metamathematical, and its significance stems from the fact that it's powerful enough to formalize "normal" mathematics, which then enables you to reason about that formalism mathematically, and thus examine the foundations of math using mathematical reasoning. (Hence the "meta.")
I don't understand why this should be significantly easier, but I'll take your word for it; a formal system is a formal system, I suppose.
Take the axioms of ZFC, Peano arithmetic, or some other familiar theory and try writing them down in a logic formalism that features only the NAND connective, and you'll see what I'm talking about. (Better yet, try devising a formal proof system using such formalism!)
Much updated here: http://lesswrong.com/lw/2un/references_resources_for_lesswrong/
For example: Metamath (Constructs mathematics from scratch, starting from ZFC set theory axioms) and The Haskell Road to Logic, Maths and Programming... and check this graphic: http://space.mit.edu/home/tegmark/toe.gif
Set Theory and the Continuum Hypothesis by Paul Cohen is good, and starts from a pretty low level if I recall, but you'll want experience in formal reasoning before reading through it. Do you have any experience with formal math?
At the risk of performing necromancy, I'd like to point out that the video was highly contested afterward on the IAS Foundations of Mathematics mailing list. Many people thought the talk wasn't a reasonable explanation of the current state of affairs in FOM.
I'm not an expert in this, however.
This video turned out to be very interesting (to my naive eyes anyway). It also gives a nice description of formal theories.
I have recently become interested in the foundations of math. I am interested in tracing the fundamentals of math in a path such as: propositional logic -> first order logic -> set theory -> measure theory. Does anyone have any resources (books, webpages, pdfs etc.) they would like to recommend?
This seems like it would be a popular activity among LWers, so I thought this would be a good place to ask for advice.
My criteria (feel free to post resources which you think others who stumble across this might be interested in):