Stage 4 Foundations and Discrete Mathematics

Foundations and Discrete Mathematics:

Foundation:

• Benacerraf P. and Putnam H. Philosophy of Mathematics: Selected Readings
  
• Courant R. and Robbins H. What Is Mathematics? An Elementary Approach to Ideas and Methods
• Frege G. The Foundations of Arithmetic: A Logico-Mathematical Enquiry into the Concept of Number
• Gödel K. On Formally Undecidable Propositions of Principia Mathematica and Related Systems - Martin Hizel provides a online version here [.pdf], see also the errata.
• Kleene S.C. Introduction to Metamathematics
• Mac Lane S. Mathematics: Form and Function
• Russell B. The Principles of Mathematics (here for FREE!)
• Simpson S.G. Foundations of Mathematics [.pdf] (FREE!) - Interested reader may find his paper Logic and Mathematics worth reading.
• Whitehead A.N. and Russell B. Principia Mathematica (here for FREE!)
  Whitehead A.N. and Russell B. Principia Mathematica to *56 - First part of the landmark work.
• Wittgenstein L. Remarks on the Foundations of Mathematics

Logic:
According to Wikipedia, Enderton, Hamilton, and Mendelson are meant for undergraduate; while Andrews, Barwise (ed.) and Shoenfield are meant for graduate.

• Aigner M. and Ziegler G.M. Proofs from THE BOOK
• Andrews P.B. Introduction to Mathematical Logic and Type Theory
• Ash C.J., Crossely J.N., Brickhill C.J., Stillwell J.C. and Williams N.H. What is Mathematical Logic?
• Barwise J. (ed.) Handbook of Mathematical Logic - Not for beginners, mind you.
• Bilaniuk S. A Problem Course in Mathematical Logic (FREE!)
• Blackburn P., de Rijke M. and Venema Y. Modal Logic
• Blackburn P., van Benthem J. and Wolter F. Handbook of Modal Logic (FREE!)
• Bornat R. Proof and Disproof in Formal Logic: An Introduction for Programmers - Oxford Texts in Logic 2.
• Carney J.D. Introduction to Symbolic Logic
• Chiswell I. and Hodges W. Mathematical Logic - Oxford Texts in Logic 3.
• Church A. Introduction to Mathematical Logic
• Copi I.M. Symbolic Logic
• Enderton H.B. A Mathematical Introduction to Logic
• Hamiltion A.G. Logic for Mathematicians
• Hedman S. A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity - Oxford Texts in Logic 1.
• Herrmann R.A. Logic for Everyone (FREE!)
• Hilbert D. and Ackermann W. Principles of Mathematical Logic
• Hunter G. Metalogic
• Kleene S.C. Mathematical Logic
• Kunen K. The Foundations of Mathematics [.ps] (FREE!) - Includes set theory, model theory and proof theory. Readers are assumed to feel comfortable with abstract mathematical structures (groups and fields) and know basics calculus.
• Mac Lane S. and Moerdijk I. Sheaves in Geometry and Logic: A First Introduction to Topos Theory
• Manin Y.I. A Course in Mathematical Logic
• Mendelson E. Introduction to Mathematical Logic
• Rautenberg W. A Concise Introduction to Mathematical Logic
• Shoenfield J.R. Mathematical Logic
• Simpson S.G. Mathematical Logic [.pdf] (FREE!)
• Srivastava S.M. A Course on Mathematical Logic
• Takeuti G. Proof Theory
• Troelstra A.S. and Schwichtenberg H. Basic Proof Theory
• Walicki M. Introduction to Logic [.pdf] (FREE!)

Set Theory:

• Bell J.L. Set Theory: Boolean-Valued Models and Independence Proofs - Wikipedia suggests this as an alternative to Kunen.
• Cohen P.J. Set Theory and the Continuum Hypothesis - Cohen is notable for his solution of CH.
• Devlin K. The Joy of Sets: Fundamentals of Contemporary Set Theory
• Dixon P.G. Set Theory [.pdf] (FREE!)
• Drake F.R. Set Theory: An Introduction to Large Cardinals
• Foreman M., Kanamori A. and Magidor M. (eds.) Online Chapters in Handbook of Set Theory (FREE!)
• Hausdorff F. Set Theory - 'One of the most beautiful sources of set-theoretic wisdom,' Halmos.
• Hrbacek K. and Jech T. Introduction to Set Theory
• Jech T. Set Theory - David Fremlin kindly suggests that the 1978 version is more suitable for beginners than the Millennium Edition. He also recommends Kunen's same title.
• Komjáth P. and Totik V. Problems and Theorems in Classical Set Theory
• Kunen K. Set Theory
• Moore G.H. Zermelo's Axiom of Choice: Its Origins, Development, and Influence
• Suppes P. Axiomatic Set Theory - 'A recent and highly readable addition to the literature, with an extensive an up-to-date bibliography,' Halmos in 1960.
• Takeuti G. and Zaring W.M. Axiomatic Set Theory
• Takeuti G. and Zaring W.M. Introduction to Axiomatic Set Theory
• Tourlakis G. Lectures in Logic and Set Theory. Volume I: Mathematical Logic
  Tourlakis G. Lectures in Logic and Set Theory. Volume 2: Set Theory

Graph Theory:

• Agnarsson G. and Greenlaw R. Graph Theory: Modeling, Applications, and Algorithms
• Bang-Jensen J. and Gutin G. Digraphs: Theory, Algorithms and Applications (here for FREE!)
• Bollobas B. Modern Graph Theory
• Bondy J.A. and Murty U.S.R. Graph Theory (here for FREE!) - Discuss in their blog.
• Diestel R. Graph Theory (here for FREE!)
• Harary F. Graph Theory
• Hell P. and Nesetril J. Graphs and Homomorphisms - See their web for errata.
• Scheinerman E.R. and Ullman D.H. Fractional Graph Theory: A Rational Approach to the Theory of Graphs
• Tutte W.T. Graph Theory As I Have Known It
• West D.B. Introduction to Graph Theory
• 國立交通大學：圖論課程講義 (FREE!)

Combinatorics:

• Bender E.A. and Williamson S.G. Foundations of Combinatorics with Applications (here for FREE!)
• Berman G. Introduction to Combinatorics
• Bona M. Combinatorics of Permutations
• Kisacanin B. Mathematical Problems and Proofs: Combinatorics, Number Theory, and Geometry
• Lovasz L. Combinatorial Problems and Exercises
• Niven I.M. Mathematics of Choice: Or, How to Count Without Counting
• Ryser H. Combinatorial Mathematics
• Stanton D. and White Constructive Combinatorics
• Tucker A. Applied Combinatorics
• van Lint J.H. and Wilson R.M. A Course in Combinatorics
• Wilf H. Generatingfunctionology (FREE!)

Cryptography, Coding and Information Theory (not so pure):
First stage introductory discrete mathematics and basic linear algebra are usual assumed knowledge.

• Ash R.B. Information Theory - An introductory text.
• Bellare M. and Rogaway P. Introduction to Modern Cryptography (FREE!)
• Berlekamp E.R. Algebraic Coding Theory
• Coutinho S.C. The Mathematics of Ciphers: Number Theory and RSA Cryptography
• Goldreich O. The Foundations of Cryptography (FREE!)
• Goldwasser S. and Bellare M. Lecture Notes on Cryptography (FREE!)
• Hall J.I. Notes on Coding Theory (FREE!)
• Hamming R.W. Coding and Information Theory - If you are serious about this field (I mean you are not merely interested in cracking ciphers like those the Zodiac Killer used), you must learn Hamming error correcting codes, this is the origin.
• Hill R. A First Course in Coding Theory
• Humphreys J.F. and Prest M.Y. Numbers, Groups and Codes - Friendlier than Roman.
• Johnson O. Information Theory and the Central Limit Theorem
• Koblitz N. A Course in Number Theory and Cryptography
• Lysyanskaya A. Cryptography and Cryptanalysis (FREE!)
• MacKay D. Information Theory, Inference, and Learning Algorithms (FREE!) - Take a look, and give me a reason why you shouldn't download it if you are studying this subject.
• Menezes A.J., van Oorschot P.C. and Vanstone S.A. Handbook of Applied Cryptography (FREE!)
• Mollin R.A. An Introduction to Cryptography
• Pless V. Introduction to the Theory of Error-Correcting Codes
• Pretzel O. Error-Correcting Codes and Finite Fields
• Roman S. Coding and Information Theory - More advanced text, basic abstract algebra required.
• Salomaa A. Public-Key Cryptography
• Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C - See author's site.
• Smith L.S. Cryptography: The Science of Secret Writing - Elementary, suitable for non-mathematicians.
• van Lint J.H. Introduction to Coding Theory - Algebra and probability required.
• Vaudenay S. A Classical Introduction to Cryptography: Applications for Communications Security - See the web for extra material.