Timeline of mathematical logic
A timeline of mathematical logic; see also history of logic.
19th century
- 1847 – Boolean algebra.
- 1854 – George Boole perfects his ideas, with the publication of An Investigation of the Laws of Thought.
- 1874 – His proof does not use his famous diagonal argument, which he published in 1891.
- 1895 – Georg Cantor publishes a book about set theory containing the arithmetic of infinite cardinal numbers and the continuum hypothesis.
- 1899 – Georg Cantor discovers a contradiction in his set theory.
20th century
- 1904 - Edward Vermilye Huntington develops the back-and-forth method to prove Cantor's result that countable dense linear orders (without endpoints) are isomorphic.
- 1908 – Ernst Zermelo axiomatizes set theory, thus avoiding Cantor's contradictions.
- 1915 - Löwenheim-Skolem theorem, implicitly using the axiom of choice.
- 1918 - C. I. Lewis writes A Survey of Symbolic Logic, introducing the modal logic system later called S3.
- 1920 - Löwenheim-Skolem theorem using the axiom of choiceexplicitly.
- 1922 - Löwenheim-Skolem theoremwithout the axiom of choice.
- 1929 - Mojzesj Presburger introduces Presburger arithmetic and proving its decidability and completeness.
- 1928 - Hilbert and Wilhelm Ackermann propose the Entscheidungsproblem: to determine, for a statement of first-order logicwhether it is universally valid (in all models).
- 1930 - completeness and countable compactnessof first-order logic for countable languages.
- 1930 - Oskar Becker introduces the modal logic systems now called S4 and S5 as variations of Lewis's system.
- 1930 - intuitionistic propositional calculus.
- 1931 – his incompleteness theoremwhich shows that every axiomatic system for mathematics is either incomplete or inconsistent.
- 1932 - C. I. Lewis and C. H. Langford's Symbolic Logic contains descriptions of the modal logic systems S1-5.
- 1933 - Kurt Gödel develops two interpretations of intuitionistic logic in terms of a provability logic, which would become the standard axiomatization of S4.
- 1934 - Thoralf Skolem constructs a non-standard model of arithmetic.
- 1936 - Alonzo Church develops the lambda calculus. Alan Turing introduces the Turing machine model proves the existence of universal Turing machines, and uses these results to settle the Entscheidungsproblem by proving it equivalent to (what is now called) the halting problem.
- 1936 - Anatoly Maltsev proves the full compactness theorem for first-order logic, and the "upwards" version of the Löwenheim–Skolem theorem.
- 1940 – Kurt Gödel shows that neither the continuum hypothesis nor the axiom of choice can be disproven from the standard axioms of set theory.
- 1943 - Church's Thesis" asserting the identity of general recursive functionswith effective calculable ones.
- 1944 - closure algebras.
- 1944 - computably enumerabledegrees lying in between the degree of computable functions and the degree of the halting problem.
- 1947 - word problem for semigroups.
- 1948 - McKinsey and Alfred Tarskistudy closure algebras for S4 and intuitionistic logic.
1950-1999
- 1950 - Boris Trakhtenbrot proves that validity in all finite models (the finite-model version of the Entscheidungsproblem) is also undecidable; here validity corresponds to non-halting, rather than halting as in the usual case.
- 1952 - Kleene presents "Turing's Thesis", asserting the identity of computability in general with computability by Turing machines, as an equivalent form of Church's Thesis.
- 1954 - categorical in any infinite cardinal at least equal to the language cardinality is complete. Łoś further conjectures that, in the case where the language is countable, if the theory is categorical in an uncountable cardinal, it is categorical in all uncountable cardinals.
- 1955 - hyperreals and prove the transfer principle.
- 1955 - finitely presented) group whose word problemis undecidable.
- 1955 - semantic tableaux.
- 1958 - William Boone independently proves the undecidability of the uniform word problem for groups.
- 1959 - Saul Kripke develops a semantics for quantified S5 based on multiple models.
- 1959 - Peano arithmeticare nonrecursive.
- 1960 - Solomonoff induction.
- 1961 – non-standard analysis.
- 1963 – Paul Cohen uses his technique of forcing to show that neither the continuum hypothesis nor the axiom of choicecan be proven from the standard axioms of set theory.
- 1963 - Saul Kripke extends his possible-world semantics to normal modal logics.
- 1965 - Morley's categoricity theoremconfirming Łoś' conjecture.
- 1965 - Andrei Kolmogorov independently develops the theory of Kolmogorov complexityand uses it to analyze the concept of randomness.
- 1966 - Ax-Grothendieck theorem: any injective polynomial self-map of algebraic varietiesover algebraically closed fields is bijective.
- 1968 - James Ax independently proves the Ax-Grothendieck theorem.
- 1969 - superstable theories.
- 1970 - Yuri Matiyasevich proves that the existence of solutions to Diophantine equations is undecidable
- 1975 - Reverse Mathematicsprogram.
See also
- History of logic
- History of mathematics
- Philosophy of mathematics
- Timeline of ancient Greek mathematicians
- Timeline of mathematics