Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would like to know more about the foundations of mathematics, but I can't really figure out where it all starts. If I look in a book on axiomatic set theory, then it seems to be assumed that one already have learned about languages. If I look in a book about logic and structure, it seems that it is assumed that one has already learned about set theory. And some books seem to assume a philosophical background. So where does it all start?

Where should I start if I really wanted to go back to the beginning?

Is it possible to make a bullet point list with where one start? For example:

  • Logic
  • Language
  • Set theory

EDIT: I should have said that I was not necessarily looking for a soft or naive introduction to logic or set theory. What I am wondering is, where it starts. So for example, it seems like predicate logic comes before set theory. Is it even possible to say that something comes first?

share|improve this question
2  
I don't personally feel that formalism is "the beginning" of mathematics, but I like Herbert Enderton's books A mathematical introduction to logic and Elements of set theory. I think they are sufficiently foundationally oriented to be non-"naive" introductions to these subjects, but I was also able to learn a lot from them without ever personally caring about what ought to come "first". (AFAIK they can be profitably read in either order. But maybe a foundations-oriented specialist would disagree with this assessment.) –  leslie townes May 4 '12 at 2:35
2  
Nontechnical comment but maybe useful for orientation: Only one Fields medal has been awarded for work on foundations - to Paul Cohen. It seems math is buoyant, hardly requiring foundations to be useful –  alancalvitti May 4 '12 at 3:41
5  
@alancalvitti: And the most publishing mathematician alive today is Shelah with over a thousand publications... So it seems that foundational research is something that there is a lot to say about. –  Asaf Karagila May 4 '12 at 4:44
5  
Furthermore, why do you measure the importance of a topic by the number of field laureates? Since when prizes where such measure? Why not other important prizes, Abel/Erdos/Wolf prizes as well? –  Asaf Karagila May 4 '12 at 5:18
3  
@AsafKaragila, thank you! –  Mariano Suárez-Alvarez May 4 '12 at 21:07

9 Answers 9

up vote 13 down vote accepted
+50

There are different ways to build a foundation for mathematics, but I think the closest to being the current "standard" is:

When rigorously followed (e.g., in a Hilbert system), classical logic does not depend on set theory in any way (rather, it's the other way around), and I believe the only use of languages in low-level theories is to prove things about the theories (e.g., the deduction theorem) rather than in the theories. (While proving such metatheorems can make your work easier afterwards, it is not strictly necessary.)

share|improve this answer
    
Thanks for the answer. This was exactly what I was asking for. –  Thomas May 4 '12 at 13:57

I strongly urge you to look at Goldrei [9] and Goldrei [10]. I learned about these books by chance in Fall 2011. Among foundational books, I think Goldrei's books must rate as among the best books I've ever come across relative to how little well-known they are. In particular, Goldrei [10] has been invaluable to me for some things I was working on a few months ago.

In case my personal situation could be of some help, in what follows I'll outline the approach I've been taking for what you asked about.

I too am trying to improve my understanding of ground-level foundational matters, at least I was this past Fall and Winter. (During the past few months I've been spending all my free time on something else, which is related to a subject taken by some students I've been tutoring.) I started with Lemmon's book [1], which was the text for a philosophy department's beginning symbolic logic course I took in 1979 (but I'd forgotten much of the material), and I very carefully read the text material and pretty much worked every single problem in the book.

After this I began reading/working through Mates [2], which was the standard beginning graduate level philosophy symbolic logic text where I was an undergraduate (but when I took the class, also in 1979, the instructor used a different text). However, I quickly decided that I was wasting my time because I had zero interest in many of the topics Mates [2] deals with and it was becoming clear to me that, after my extensive work with Lemmon [1], I could easily skip Mates [2] and precede to something at the "next level".

I then began Hamilton [3]. I got through the first couple of chapters, doing all the exercises (propositional logic), and then I decided to take a temporary detour and study a little deeper Hilbert style (non-standard) propositional calculus before continuing into Hamilton's predicate calculus chapter. I spent about 10 weeks on this, and have a nearly finished 50+ manuscript on how I think the subject should be presented, motivated by what seems to me to be major pedagogical shortcomings in the existing literature, especially in Hamilton's book. (Goldrei [10], which I didn't discover until later, is an exception.) In this regard, see my answer at [11]. However, at the start of the Spring 2012 semester I had to stop because some students I was tutoring in Fall 2011 wanted me to work with them this semester in a subject that I needed a lot of brush-up with (vector calculus). (I work full time, not teaching, so I have a limited amount of free time to devote to math.)

My intent is to return to Hamilton [3], a book I've had for over 20 years and have always wanted to work through. After Hamilton's book, I'm thinking I'll quickly work through Machover [4], which should be easy as I've already read through much of Machover's book at this point. After these "preliminaries", my goal is to very carefully work through Boolos/Burgess/Jeffrey [5], a (later edition of a) book I actually had a reading course out of in Spring 1990 but, due to other issues at the time, I wasn't able to do much justice to and I feel bad about it to this day.

After this (or perhaps at the same time), I intend to very carefully work through Enderton [6], a book that was strongly recommended to me back in 1986 when I was in a graduate program (different from 1990) with the intention of doing research in either descriptive set theory or in set-theoretic topology, but I had to leave after not passing my Ph.D. exams (two tries).

I have several other logic books, but probably the most significant for possible future study, should I continue, are Ebbinghaus/Flum/Thomas [7] and van Dalen [8]. Each of these is approximately the same level as Boolos/Burgess/Jeffrey [5] and Enderton [6], but they appear to offer more emphasis on some topics (e.g. model theory and intuitionism).

Everything I've mentioned is mathematical logic because set theory (naive set theory, at least) is something I've picked up a lot of in other math courses and on my own. What I'm really looking for is sufficient background in logic to understand and read about things like transitive models of ZF, forcing, etc.

[1] E. J. Lemmon, Beginning Logic (1978)

http://www.amazon.com/dp/0915144506

[2] Benson Mates, Elementary Logic (1972)

http://www.amazon.com/dp/019501491X

[3] A. G. Hamilton, Logic for Mathematicians (1988)

http://www.amazon.com/dp/0521368650

[4] Moshe Machover, Set Theory, Logic and their Limitations (1996)

http://www.amazon.com/dp/0521479983

[5] George S. Boolos, John P. Burgess, and Richard C. Jeffrey, Computability and Logic (2007)

http://www.amazon.com/dp/0521701465

[6] Herbert Enderton, A Mathematical Introduction to Logic (2001)

http://www.amazon.com/dp/0122384520

[7] H.-D. Ebbinghaus, J. Flum, and W. Thomas, Mathematical Logic (1994)

http://www.amazon.com/dp/0387942580

[8] Dirk van Dalen, Logic and Structure (2008)

http://www.amazon.com/dp/3540208798

[9] Derek C. Goldrei, Classic Set Theory for Guided Independent Study (1996)

http://www.amazon.com/dp/0412606100

[10] Derek C. Goldrei, Propositional and Predicate Calculus: A Model of Argument (2005)

http://www.amazon.com/gp/product/1852339217

[11] Proving $(p \to (q \to r)) \to ((p \to q) \to (p \to r))$

share|improve this answer

"...mathematics is so rich and infinite that it is impossible to learn it systematically, and if you wait to master one topic before moving on to the next, you'll never get anywhere. Instead, you'll have tendrils of knowledge extending far from your comfort zone. Then you can later backfill from these tendrils, and extend your comfort zone; this is much easier to do than learning "forwards"."

-Ravi Vakil

Even though this might not be directly relevant, it might be another opinion on the matter. For what it is worth, I think my mind works like this.

http://math.stanford.edu/~vakil/potentialstudents.html This page has many more nice ideas.

share|improve this answer
    
Thanks for the answer. So are you saying that it is a matter of opinion whether something comes before anything? And are you saying that in your opinion, it is impossible to say that for example language comes before set theory? –  Thomas May 4 '12 at 1:07
    
No, I thought you wanted to begin learning from the bottom(whatever that is) and gradually build up everything. I was just offering an opinion that this was impractical. –  Ravi Donepudi May 4 '12 at 1:11
    
Ok, so it is possible (technically) to truly start at the beginning? –  Thomas May 4 '12 at 1:16
1  
Or in a way, to percieve what the "bottom of all things mathematical" is, you need to have a much clearer idea of things "above". For example, the need for set theory as the "bottom" did not arise more than 150-200 years ago to explain the pathologies of analysis. And then came logic to explain the mishaps in set theory. The notion of rigor/foundation grows more and more clear with advances in other fields. I do not think we can pin down a bottom, truly. –  Ravi Donepudi May 4 '12 at 1:17
2  
Great quote! I feel that way most of the time. Being pulled away from the comfort zone, being pulled back to the basics, feeling better, going out, and back, and forth, and back... –  Pedro Tamaroff May 4 '12 at 1:19

The foundations of mathematics starts with mathematics. This sounds trivial but may help you understand what you're looking for. Nobody ever sat down and said, "I think I'll do foundations today." They started out doing math, and tripped over something that looked like it had an easy answer, and turned out not to.

I think you should read about Cantor and his ideas, in whatever sources you find intelligible. Cantor was studying infinite sets and noticed they weren't all the same size. Prior to 1900, he made a rather simple conjecture which came to be called the Continuum Hypothesis. Godel's work in the 1940s and Cohen's in the 1960s are related to Cantor's conjecture.

The problem with jumping straight into books on set theory and logic is that generally they present solutions and what is known, rather than the mathematical problems that foundations are supposed to help solve.

The first chapter of Smullyan and Fitting's Set theory and the continuum problem is a notable exception. I'm sure there are others.

share|improve this answer

A lot of people recommend Paul Halmos's book Naive Set Theory. The appendix of John Kelley's General Topology is an extremely clear and concise introduction to axiomatic set theory that assumes nothing; it is also quite short. I liked J. Barkley Rosser's book on Mathematical Logic.

share|improve this answer
    
Thanks for the answer. I added more to my question. I have looked at several "naive" or soft introductions to set theory, but I was wondering more about if it is possible to say that something comes before set theory. –  Thomas May 4 '12 at 1:06

The best book I know to begin with for the foundations of mathematics is a little known book that should be MUCH more widely known then it is: Robert Wolfe's A Tour Through Mathematical Logic. It's a beautifully written survey of all the major areas of the foundations of mathematics,from basic propositional logic to computability theory to axiomatic set theory to model theory and ending with a wonderful introduction to forcing and the Continuum Hypothesis. All of it comes with lots of terrific historical notes and full references for further reading. I was utterly fascinated with the story it told and couldn't put it down. It certainly shouldn't be the only book you read on the subject,but it certainly is the best place to start and a terrific supplement to any of the standard textbooks. The references therein will direct you to further study.

share|improve this answer

If we have set theory, we can use it to construct formal logic. If we have formal logic, we can talk about set theory.

It's circular, of course, but that's not really an issue. If you really must have a "starting point", you can make whichever metamathematical assertion you want about which one describes mathematics in the "real world".

The main thing to keep in mind if you're focused on thinking about this is to avoid the danger of level slipping. e.g. if you've decided metamathematics is set theory, and you use that to construct formal logic, and then you use formal logic to talk about set theory, then sometimes you have to pay careful attention to the fact that the former set theory and the latter set theory are different. e.g. so you don't fall prey to Skolem's paradox. Occasionally, you have to follow the circle through to one more level than that!

As a practical point, be aware that there are practical applications for using set theory to construct formal logic -- the model theory internal to a set theoretic universe can be used to talk about other structures that you construct out of sets.

Conversely, there are also practical applications for using formal logic to talk about set theory -- for example, non-standard analysis is most conveniently founded in such a manner.

So whichever way you go about things, you really should traverse at least one full revolution through "logic -> set theory -> logic" circle.

share|improve this answer
1  
We do not need set theory to construct formal logic. Check for example Chiswell's Introduction to Logic. –  Trismegistos Feb 4 at 14:20

I am just an amateur at this, but I suggest that the beginner not get bogged down with language and philosophy right away. I suggest the following order for learning the foundations of mathematics:

  • Propositional logic
  • Predicate logic
  • Set theory
  • Number theory (starting with Peano's Axioms)

Almost everything else in mathematics (algebra, analysis and geometry) follows from these beginnings.

You might have a look at my DC Proof software available free at http://www.dcproof.com. It includes a tutorial that follows in the above steps. My program is based on a simplified, non-standard presentation of formal logic and set theory. As such, I wouldn't call it a definitive, though I wouldn't call it "soft or naive" either. (It is based on the simplifying assumption that most if not all of mathematical theory is based on some underlying set(s). This neatly avoids a number of prickly issues of formal logic and set theory for the beginner.) At the very least, I think it will put you in the right frame of mind for a serious study of a more standard presentation -- you will at least know what questions to ask!

share|improve this answer

There is a certain amount of inherent circularity in the subject, since we use the theory of sets to model the theory of models to model the theory of inference.

That said, it is not vicious circularity, and you can break out of it if you really really want. It has been done, and it is not really any clearer. A beginner is not in a position to do it.

I would suggest starting with a "soft" book on Logic. I used "Language, Proof, and Logic" way back when. It covers the propositional calculus, first order logic, semantics in terms of models, soundness, completeness, and even some "advanced" topics like models of set theory, Skolem's paradox, and a description of Godel's incompleteness theorem. I say it is "soft" because it often uses "natural language" to describe the mathematical constructs "conceptually". This is not a bad thing, especially for a field like logic, where the first steps are to figure out what roles the various pieces play (why you need sets to model, why you need models for semantics, why you need semantics for languages). It has lots of problems, too. It comes with software you can use to practice proof writing and exploring model theory (but it's from 2002, so I don't know if it will work with modern Windows)

Also note the book is like 900 pages long. Since you did Lemmon, you can start on part 2, which covers the first order logic.

After you have a grasp of what all the pieces "do", you will be well-equipped to pick your next field of study.

That said, you've gotten as far as descriptive set theory, so you can clearly handle some unmotivated formalism. Even in that case, I would suggest Language, Proof, and Logic, as a sort of handbook for intuition on the topic.

When I took mathematical logic, we used Enderton, with extracts from Ebbinghaus. Both are great, and Enderton was awesome! He used to post on sci.logic and answer beginners' questions (like mine) with great enthusiasm.

share|improve this answer
    
It looks like "Language, Proof, and Logic" is quite basic but it uses Fitch System for proofs which seems to be very handy. –  Trismegistos Feb 4 at 15:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.