Where to begin with foundations of mathematics 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?
 A: 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.
A: 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.
A: 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. 
A: 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.
A: 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!
A: There are different ways to build a foundation for mathematics, but I think the closest to being the current "standard" is:


*

*Philosophy (optional)

*Propositional logic

*First-order logic (a.k.a. "predicate logic")

*Set theory (specifically, ZFC)

*Everything else
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.)
A: "...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.
A: 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.
