Matemaattinen logiikka

Matemaattinen logiikka viittaa kahteen erilliseen tutkimusalueeseen: toisaalta formaalisen logiikan menetelmien soveltamiseen matematiikkaan ja matemaattiseen päättelyyn, ja toisaalta matemaattisten menetelmien soveltamiseen formaalisen logiikan esittämisessä ja analysoinnissa.

Varhaisin matematiikan ja geometrian käyttö logiikassa ja filosofiassa löytyy jo antiikin Kreikasta Eukleideelta, Platonilta ja Aristoteleelta. Rohkein yritys soveltaa logiikkaa matematiikkaan on epäilemättä ollut filosofi-loogikoiden Gottlob Frege ja Bertrand Russell logisismi. Heidän ajatuksensa oli, että matemaattiset teoriat olivat loogisia tautologioita, ja he pyrkivät osoittamaan tämän palauttamalla matematiikan logiikkaan. Tämä kuitenkin epäonnistui, mistä esimerkkinä Fregen ohjelman lamaannuttanut Russellin paradoksi ja Hilbertin ohjelman romuttanut Gödelin epätäydellisyyslause.

Sekä Hilbertin ohjelma että Gödelin vastine siihen olivat riippuvaisia toisesta matemaattisen logiikan osa-alueesta, matematiikan soveltamisesta logiikkaan todistusteorian muodossa. Vaikka epätäydellisyysteoreema oli luonteeltaan negatiivinen, Gödelin täydellisyyslause oli malliteorian tulos ja osoittaa, kuinka lähellä logisismi oli osoittautua todeksi: jokainen täsmällisesti määritelty matemaattinen teoria voidaan esittää ensimmäisen kertaluvun logiikan teorialla; Fregen todistuskalkyyli pystyi kuvaamaan koko matematiikan, vaikka ei vastaakaan sitä. Näin matemaattisen logiikan kaksi osa-aluetta osoittautuvat toisiaan täydentäviksi.

Jos todistusteoria ja malliteoria ovatkin olleet matemaattisen logiikan perusta, ne ovat muodostaneet vasta kaksi sen neljästä tukipilarista. Joukko-oppi sai alkunsa Georg Cantorin äärettömyyden tutkimuksista ja se on tuottanut monet matemaattisen logiikan haastavimmista ja merkittävimmistä ongelmista (kuten Cantorin lause, valinta-aksiooma ja kontinuumihypoteesi). Rekursioteoria kuvaa laskentaa logiikan ja aritmetiikan avulla. Sen klassisimpia saavutuksia ovat Alan Turingin Entscheidungsproblemin osoittaminen ratkaisemattomaksi sekä Churchin-Turingin teesi. Nykyisin rekursioteoria tutkii ennen kaikkea monimutkaisuuksia ja ongelmien (tehokasta) ratkeavuutta.

Kirjallisuutta

Opiskelijoiden tekstit

• Walicki, Michał (2011), Introduction to Mathematical Logic, Singapore: World Scientific Publishing, ISBN 978-981-4343-87-9.

• Boolos, George; Burgess, John; Jeffrey, Richard (2002), Computability and Logic (4th ed.), Cambridge: Cambridge University Press, ISBN 978-0-521-00758-0.

• Crossley, J.N.; Ash, C.J.; Brickhill, C.J.; Stillwell, J.C.; Williams, N.H. (1972), What is mathematical logic?, London-Oxford-New York: Oxford University Press, ISBN 978-0-19-888087-5, Zbl 0251.02001.

• Enderton, Herbert (2001), A mathematical introduction to logic (2nd ed.), Boston, MA: Academic Press, ISBN 978-0-12-238452-3.

• Fisher, Alec (1982), Formal Number Theory and Computability: A Workbook (1st ed.), USA: Oxford University Press, ISBN 978-0-19-853188-3. Suitable as a first course for independent study.

• Hamilton, A.G. (1988), Logic for Mathematicians (2nd ed.), Cambridge: Cambridge University Press, ISBN 978-0-521-36865-0.

• Ebbinghaus, H.-D.; Flum, J.; Thomas, W. (1994), Mathematical Logic (2nd ed.), New York: Springer, ISBN 978-0-387-94258-2.

• Katz, Robert (1964), Axiomatic Analysis, Boston, MA: D. C. Heath and Company.

• Mendelson, Elliott (1997), Introduction to Mathematical Logic (4th ed.), Lontoo: Chapman & Hall, ISBN 978-0-412-80830-2.

• Rautenberg, Wolfgang (2010), A Concise Introduction to Mathematical Logic (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6.

• Schwichtenberg, Helmut (2003–2004), Mathematical Logic (PDF), München, Saksa: Mathematisches Institut der Universität München, retrieved 2016-02-24.

• Shawn Hedman, A first course in logic: an introduction to model theory, proof theory, computability, and complexity, Oxford University Press, 2004, ISBN 0-19-852981-3. Covers logics in close relation with computability theory and complexity theory

• van Dalen, Dirk (2013), Logic and Structure, Universitext, Berliini: Springer-Verlag, doi:10.1007/978-1-4471-4558-5, ISBN 978-1-4471-4557-8.

Valmistuneiden tekstit

• Andrews, Peter B. (2002), An Introduction to Mathematical Logic and Type Theory: To Truth Through Proof (2nd ed.), Boston: Kluwer Academic Publishers, ISBN 978-1-4020-0763-7.

• Barwise, Jon, ed. (1989). Handbook of Mathematical Logic. Studies in Logic and the Foundations of Mathematics. North Holland. ISBN 978-0-444-86388-1..

• Hodges, Wilfrid (1997), A shorter model theory, Cambridge: Cambridge University Press, ISBN 978-0-521-58713-6.

• Jech, Thomas (2003), Set Theory: Millennium Edition, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-3-540-44085-7.

• Kleene, Stephen Cole.(1952), Introduction to Metamathematics. New York: Van Nostrand. (Ishi Press: 2009 reprint).

• Kleene, Stephen Cole. (1967), Mathematical Logic. John Wiley. Dover reprint, 2002. ISBN 0-486-42533-9.

• Shoenfield, Joseph R. (2001) [1967], Mathematical Logic (2nd ed.), A K Peters, ISBN 978-1-56881-135-2.

• Troelstra, Anne Sjerp; Schwichtenberg, Helmut (2000), Basic Proof Theory, Cambridge Tracts in Theoretical Computer Science (2nd ed.), Cambridge: Cambridge University Press, ISBN 978-0-521-77911-1.

Tutkimukset, kyselyt

• Augusto, Luis M. (2017). Logical consequences. Theory and applications: An introduction. London: College Publications. ISBN 978-1-84890-236-7.

• Cohen, P. J. (1966), Set Theory and the Continuum Hypothesis, Menlo Park, CA: W. A. Benjamin.

• Cohen, Paul Joseph (2008) [1966]. Set theory and the continuum hypothesis. Mineola, New York: Dover Publications. ISBN 978-0-486-46921-8..

• J.D. Sneed, The Logical Structure of Mathematical Physics. Reidel, Dordrecht, 1971 (revised edition 1979).

• Davis, Martin (1973), "Hilbert's tenth problem is unsolvable", The American Mathematical Monthly, 80 (3): 233–269, doi:10.2307/2318447, JSTOR 2318447, reprinted as an appendix in Martin Davis, Computability and Unsolvability, Dover reprint 1982.

• Felscher, Walter (2000), "Bolzano, Cauchy, Epsilon, Delta", The American Mathematical Monthly, 107 (9): 844–862, doi:10.2307/2695743, JSTOR 2695743.

• Ferreirós, José (2001), "The Road to Modern Logic-An Interpretation" (PDF), Bulletin of Symbolic Logic, 7 (4): 441–484, doi:10.2307/2687794, hdl:11441/38373, JSTOR 2687794.

• Hamkins, Joel David; Benedikt Löwe (2007), "The modal logic of forcing", Transactions of the American Mathematical Society, 360 (4): 1793–1818, arXiv:math/0509616, doi:10.1090/s0002-9947-07-04297-3

• Katz, Victor J. (1998), A History of Mathematics, Addison–Wesley, ISBN 978-0-321-01618-8.

• Morley, Michael (1965), "Categoricity in Power", Transactions of the American Mathematical Society, 114 (2): 514–538, doi:10.2307/1994188, JSTOR 1994188.

• Soare, Robert I. (1996), "Computability and recursion", Bulletin of Symbolic Logic, 2 (3): 284–321, CiteSeerX 10.1.1.35.5803, doi:10.2307/420992, JSTOR 420992.

• Solovay, Robert M. (1976), "Provability Interpretations of Modal Logic", Israel Journal of Mathematics, 25 (3–4): 287–304, doi:10.1007/BF02757006.

• Woodin, W. Hugh (2001), "The Continuum Hypothesis, Part I", Notices of the American Mathematical Society, 48 (6). PDF

Tieteelliset julkaisut

• Burali-Forti, Cesare (1897), A question on transfinite numbers, reprinted in van Heijenoort 1976, pp. 104–111.

• Dedekind, Richard (1872), Stetigkeit und irrationale Zahlen. English translation of title: "Consistency and irrational numbers".

• Dedekind, Richard (1888), Was sind und was sollen die Zahlen? Two English translations:

• 1963 (1901). Essays on the Theory of Numbers. Beman, W. W., ed. and trans. Dover.

• 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed., Oxford University Press: 787–832.

• Fraenkel, Abraham A. (1922), "Der Begriff 'definit' und die Unabhängigkeit des Auswahlsaxioms", Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse, pp. 253–257 (saksaksi), reprinted in English translation as "The notion of 'definite' and the independence of the axiom of choice", van Heijenoort 1976, pp. 284–289.

• Frege, Gottlob (1879), Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens. Halle a. S.: Louis Nebert. Translation: Concept Script, a formal language of pure thought modelled upon that of arithmetic, by S. Bauer-Mengelberg in Jean Van Heijenoort, ed., 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931. Harvard University Press.

• Frege, Gottlob (1884), Die Grundlagen der Arithmetik: eine logisch-mathematische Untersuchung über den Begriff der Zahl. Breslau: W. Koebner. Translation: J. L. Austin, 1974. The Foundations of Arithmetic: A logico-mathematical enquiry into the concept of number, 2nd ed. Blackwell.

• Gentzen, Gerhard (1936), "Die Widerspruchsfreiheit der reinen Zahlentheorie", Mathematische Annalen, 112: 132–213, doi:10.1007/BF01565428, reprinted in English translation in Gentzen's Collected works, M. E. Szabo, ed., North-Holland, Amsterdam, 1969.

• Gödel, Kurt (1929), Über die Vollständigkeit des Logikkalküls, doctoral dissertation, Wienin yliopisto. English translation of title: "Completeness of the logical calculus".

• Gödel, Kurt (1930), "Die Vollständigkeit der Axiome des logischen Funktionen-kalküls", Monatshefte für Mathematik und Physik, 37: 349–360, doi:10.1007/BF01696781. English translation of title: "The completeness of the axioms of the calculus of logical functions".

• Gödel, Kurt (1931), "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monatshefte für Mathematik und Physik, 38 (1): 173–198, doi:10.1007/BF01700692, see On Formally Undecidable Propositions of Principia Mathematica and Related Systems for details on English translations.

• Gödel, Kurt (1958), "Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes", Dialectica. International Journal of Philosophy, 12 (3–4): 280–287, doi:10.1111/j.1746-8361.1958.tb01464.x, reprinted in English translation in Gödel's Collected Works, vol II, Solomon Feferman et al., eds. Oxford University Press, 1990.

• van Heijenoort, Jean, ed. (1976) [1967], From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931 (3rd ed.), Cambridge, Mass: Harvard University Press, ISBN 978-0-674-32449-7, (pbk.)

• Hilbert, David (1899), Grundlagen der Geometrie, Leipzig: Teubner, English 1902 edition (The Foundations of Geometry) republished 1980, Open Court, Chicago.

• David, Hilbert (1929), "Probleme der Grundlegung der Mathematik", Mathematische Annalen, 102: 1–9, doi:10.1007/BF01782335. Lecture given at the International Congress of Mathematicians, 3 September 1928. Published in English translation as "The Grounding of Elementary Number Theory", in Mancosu 1998, pp. 266–273.

• Hilbert, David; Bernays, Paul (1934). Grundlagen der Mathematik. I. Die Grundlehren der mathematischen Wissenschaften. 40. Berliini, New York: Springer-Verlag. ISBN 978-3-540-04134-4. JFM 60.0017.02. MR 0237246.

• Kleene, Stephen Cole (1943), "Recursive Predicates and Quantifiers", American Mathematical Society Transactions, 54 (1): 41–73, doi:10.2307/1990131, JSTOR 1990131.

• Lobachevsky, Nikolai (1840), Geometrishe Untersuchungen zur Theorie der Parellellinien (saksaksi). Reprinted in English translation as "Geometric Investigations on the Theory of Parallel Lines" in Non-Euclidean Geometry, Robert Bonola (ed.), Dover, 1955. ISBN 0-486-60027-0

• Löwenheim, Leopold (1915), "Über Möglichkeiten im Relativkalkül", Mathematische Annalen, 76 (4): 447–470, doi:10.1007/BF01458217, ISSN 0025-5831 (saksaksi). Translated as "On possibilities in the calculus of relatives" in Jean van Heijenoort, 1967. A Source Book in Mathematical Logic, 1879–1931. Harvard Univ. Press: 228–251.

• Mancosu, Paolo, ed. (1998), From Brouwer to Hilbert. The Debate on the Foundations of Mathematics in the 1920s, Oxford: Oxford University Press.

• Pasch, Moritz (1882), Vorlesungen über neuere Geometrie.

• Peano, Giuseppe (1889), Arithmetices principia, nova methodo exposita (latinaksi), excerpt reprinted in English translation as "The principles of arithmetic, presented by a new method", van Heijenoort 1976, pp. 83 97.

• Richard, Jules (1905), "Les principes des mathématiques et le problème des ensembles", Revue Générale des Sciences Pures et Appliquées, 16: 541 (ranskaksi), reprinted in English translation as "The principles of mathematics and the problems of sets", van Heijenoort 1976, pp. 142–144.

• Skolem, Thoralf (1920), "Logisch-kombinatorische Untersuchungen über die Erfüllbarkeit oder Beweisbarkeit mathematischer Sätze nebst einem Theoreme über dichte Mengen", Videnskapsselskapet Skrifter, I. Matematisk-naturvidenskabelig Klasse, 6: 1–36.

• Tarski, Alfred (1948), A decision method for elementary algebra and geometry, Santa Monica, Kalifornia: RAND Corporation

• Turing, Alan M. (1939), "Systems of Logic Based on Ordinals", Proceedings of the London Mathematical Society, 45 (2): 161–228, doi:10.1112/plms/s2-45.1.161, hdl:21.11116/0000-0001-91CE-3

• Zermelo, Ernst (1904), "Beweis, daß jede Menge wohlgeordnet werden kann", Mathematische Annalen, 59 (4): 514–516, doi:10.1007/BF01445300 (saksaksi), reprinted in English translation as "Proof that every set can be well-ordered", van Heijenoort 1976, pp. 139–141.

• Zermelo, Ernst (1908a), "Neuer Beweis für die Möglichkeit einer Wohlordnung", Mathematische Annalen, 65: 107–128, doi:10.1007/BF01450054, ISSN 0025-5831 (saksaksi), reprinted in English translation as "A new proof of the possibility of a well-ordering", van Heijenoort 1976, pp. 183–198.

• Zermelo, Ernst (1908b), "Untersuchungen über die Grundlagen der Mengenlehre", Mathematische Annalen, 65 (2): 261–281, doi:10.1007/BF01449999.