User:Gregbard/Sandbox/Great theorems of logic

Great theorems of logic

• Proof of the uncountability of the set of all subsets of the set of natural numbers -- Cantor's diagonal proof
• Proof of the consistency of truth-functional propositional logic (Post 1920)
• Proof of the semantic completeness of truth-functional propositional logic
• Proof of the syntactic completeness of truth-functional propositional logic
• Proof of the decidability of truth-functional propositional logic (Post 1920)
• Proof of the consistency of first order monadic predicate logic
• Proof of the semantic completeness of first order monadic predicate logic
• Proof of the decidability of monadic predicate logic (Lowenheim 1915)
• Proof of the consistency of first order predicate logic (Hilbert-Ackermann 1928)
• Proof of the semantic completeness of first order predicate logic (Godel 1930)
• Proof of the undecidability of first order predicate logic (Church 1936) Church's theorem
• Post's functional completeness theorem
• Hilbert's map of geometry onto algebra.
• Lowenheim-Skolem theorem
• Cantor's theorem
• Gentzen's consistency proof
• Godel's first incompleteness theorem (1931)
• Godel's second incompleteness theorem (1931)
  • Godel's consistency theorem
• Godel's completeness theorem (1930)
• Turing's halting theorem
• Church-Turing thesis
• Davis-Putnam algorithm
• Banach-Tarski paradox
• Tarski's indefinability theorem
• Löb's theorem
• Church–Rosser theorem
• Decidability
  • Church (1956)
  • Quine (1953)
  • Kalmar (1936)
  • Meyer and Lambert (1967)