Here, I present the literatures which have been very helpful for my researches and foundations of my understandings of mathematics. Those readers from other areas of mathematics are most welcome. I hope this page will make my academic trials more approachable, verifiable, and therefore scientific. Also, it would be my pleasure if the general readers could find some of the literatures here interesting and start to enjoy new ways of thinking.
I assume relatively little for readers of this page: only basics (say, a half-year serious study for each) of (naive) set theory, topology, linear algebra, elementary analysis, group theory, field theory, and probability theory are required.
Although it is a painful decision, in order to make this page fit in a reasonable complexity, I stick to minimalism and omit a number of good textbooks and surveys, which give us further more rich views of the fields. I strongly encourage interested readers to keep asking the surrounding people about good literatures (and, if possible, give them back what you have been learning so far!).
In order to understand my trials so far, it is enough to read:
Krajíček, J. (2019). Proof complexity. Cambridge, UK: Cambridge University Press, Encyclopedia of Mathematics and Its Applications 170.
and
Cook, S., & Nguyen, P. (2010). Logical foundations of proof complexity. New York, NY: Cambridge University Press, Perspectives in Logic.
To tackle [Cook & Nguyen], it suffices to know basics of mathematical logic (especially, proof theory, model theory, and theory of computation).
To understand [Krajíček], I encourage the readers to study also graph theory, finite model theory, and Buss's bounded arithmetics. As for the last topic, I recommend the original article:
Buss, S. (1986). Bounded arithmetic. Naples: Bibliopolis, Studies in Proof Theory, Lecture Notes 3.
Remark: One very strong point of [Krajíček] is that it gives a thorough list of references. I really encourage the readers to at least take a look on original texts every time they encounter interesting results. By the way, the errata is also very helpful.
Pudlák, P. The Lengths of proofs, in Handbook of Proof Theory, S. Buss (Ed.), Studies in Logic and the Foundations of Mathematics 137, Elsevier, Amsterdam (1998), 548-637.
↑ It is relatively short but touches various issues in Proof Complexity, and therefore I think it suits for the first reading of Proof Complexity. However, the readers should note the year of publication.
Pudlák, P. (2013). Logical foundations of mathematics and computational complexity: a gentle introduction, Cham: Springer, Springer Monographs in Mathematics.
↑This is one my favorite readings. The readers can learn the history and the important issues of proof complexity and computational complexity without getting into technical details. Corrections are also helpful.
To be honest, I am still on the way of seeking "the optimal way" (which might not exist) to learn basics of Mathematical Logic in English. Since there are so many good textbooks nowadays, it may be the best for the readers to go through all the available books and choose their favorites.
However, let me suggest one possible trial.
Read the following first:
Kunen, K. (2009). The Foundations of Mathematics. London: College Publications, Studies in Logic, Mathematical Logic and Foundations, vol. 19.
↑ I believe this gives us a clear picture why the first-order logic suffices to express modern set-theoretic foundation of mathematics. At the same time, the readers can get familiar with basic treatment of ordinals, which is a necessary knowledge to learn broad areas of mathematical logic. However, towards Proof Complexity, the readers still need supplements for Model Theory, Computability Theory, and Proof Theory. So,
・As for Model Theory, I recommend the following to learn basics:
Marker, D. (2002). Model Theory : An Introduction. NY: Springer New York, Graduate Texts in Mathematics, volume 217.
・As for Computability Theory, I suppose that the following book is very exciting:
Cooper, S. B. (2004). Computability Theory. New York: Chapman and Hall/CRC.
However, Part III of this book is a quite challenging reading and I strongly recommend the readers to consult with other literatures at the same time or just skip the part on the first read.
・As for Proof Theory, I believe that the first three chapters of the following book are very instructive:
Toshiyasu, A. (2020). Ordinal analysis with an introduction to proof theory. Springer Singapore, Logic in Asia: Studia Logica Library.
I presume the latter part of the book suits for readers interested in Ordinal Analysis.
To learn the very basics,
Sipser, M. (2013). Introduction to the Theory of Computation, Third edition. Boston, MA: Course Technology.
is recommended.
If one wants a more formal and yet still introductory textbook on Computational Complexity Theory, then I recommend the following:
Papadimitriou, C. H. (1994). Computational Complexity. MA: Addison-Wesley Publishing Company, Reading.
Based on them, I encourage ambitious readers to go through
Arora, S., & Barak, B. (2009). Computational Complexity -A Modern Approach-. New York: Cambridge University Press.
I strongly recommend the readers to use the printed version of the book, check the bibliography of each chapter, and tackle the original texts at the same time, too. I believe it is O.K. for readers to skip some chapters which look uninteresting for themselves temporarily, and then go back to them if necessary in the future.
I greatly appreciate Professor Jan Krajíček bringing me to the attention of [Papadimitriou] and discussing related topics with me.
I recommend
Diestel, R. (2016). Graph Theory, 5th edition, Heidelberg: Springer-Verlag, Graduate Texts in Mathematics, Volume 173.
（it is O.K. to skip Infinite Graph Theory and the Graph Minor Theorem for the purpose of this page). However, in order to understand some arguments in [Krajíček], it is good to know basics of expander graphs. I recommend the corresponding chapters of [Arora & Barak] for it.
I think it is better to tackle this subject after studying Graph Theory, Model Theory, and Computational Complexity Theory.
I recommend
Ebbinghaus, H-D., Flum, J. (2006). Finite model theory, Second revised and enlarged edition, Berlin: Springer-Verlag, Springer Monographs in Mathematics.
Just the chapters until "Descriptive Complexity Theory" suffice.
It is enough to read Chapters I and II of
Siegel, A. (2013). Combinatorial game theory, Providence, RI: American Mathematical Society, Graduate Studies in Mathematics 146.
It is enough to read Chapters 1-4 of
Luo, Z. (1994). Computation and reasoning: a type theory for computer science, Oxford, New York: Claredon Press, Oxford University Press.
If you know basics of lambda-calculus and a precise proof of Church-Rosser theorem, then the study would be smooth. As for the last issue, I recommend Appendix and the related chapers of the following：
Hindley, J, R., & Seldin, J,P. (2008). Lambda-Calculus and Combinators: An Introduction, New York: Cambridge University Press.
Thurston, W, P. On proof and progress in mathematics, in 18 Unconventional Essays on the Nature of Mathematics, R. Hersh (eds), Springer, New York (1994), 37-55. →arXiv
↑Although it is a critical essay, I personally feel it is quite encouraging. I recommend it to people who:
・will start to study mathematics in English,
・have been studying mathematics, but are now worrying about the future,
・would like to support mathematicians, but are wondering which kind of mathematics they should root for.
I deeply thank Professor Zdeněk Strakoš for his letting me know this essay and for related discussions with me.