Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

Vladimir_M comments on Learning the foundations of math - Less Wrong

4 Post author: jsalvatier 24 October 2010 07:29PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (31)

You are viewing a single comment's thread. Show more comments above.

Comment author: Vladimir_M 25 October 2010 01:10:48AM *  0 points [-]

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.

Comment author: jsalvatier 25 October 2010 01:19:46AM 0 points [-]

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?

Comment author: Vladimir_M 25 October 2010 01:35:54AM 0 points [-]

I'm not sure I understand your question. What exactly would you want to skip, and why?

Comment author: jsalvatier 25 October 2010 02:49:00AM 0 points [-]

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?

Comment author: Vladimir_M 25 October 2010 03:28:30AM *  0 points [-]

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?

Comment author: jsalvatier 25 October 2010 04:31:08AM 0 points [-]

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.

Comment author: Vladimir_M 25 October 2010 05:05:52AM *  1 point [-]

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.

Comment author: jsalvatier 25 October 2010 04:09:45PM *  0 points [-]

Thanks for your help, I think you've clarified a lot for me.

Would you classify propositional logic/first-order-logic as necessarily metamathematical?

Comment author: Vladimir_M 25 October 2010 07:19:29PM *  1 point [-]

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.")

Comment author: jsalvatier 25 October 2010 11:16:31PM 0 points [-]

Thanks, that clears up quite a bit.