
Theorems from Logic and Computer Science
This is a subset of the complete theorem list for the convenience of those who are looking for a particular result in the areas of logic and computer science.
Numbers in brackets are those from the complete listing.
 Cook's Theorem on NPcompleteness (14)
 The WellOrdering Theorem (17)
 The Axiom of Choice (cf. 17)
 The Banach–Tarski Paradox (cf. 17)
 Cantor's Uncountability Theorem (22)
 Cantor's Theorem (23)
 The DPRM Theorem (43)
 Goodstein's Theorem (73)
 Gödel's First Incompleteness Theorem (74)
 Gödel's Second Incompleteness Theorem (75)
 The Parking Function Formula (103)
 The Pumping Lemma (105)
 The Robbins Problem (110)
 De Morgan's Laws (111)
 The Lucas–Lehmer Test (127)
 Vaughan Pratt's Theorem (138)
 Strassen's Matrix Theorem (139)
 The Robinson–Schensted–Knuth Correspondence (143)
 Quadratic Nonresidue is ZeroKnowledge Provable
(161)
 Haken's Unknot Theorem (166)
 The MaxFlow MinCut Theorem (168)
 The Greibach Normal Form Theorem (180)
 The Insolvability of the Entscheidungsproblem (186)
 Karp's Theorem (Detail) (187)
 The Rotation Distance Bound (192)
 The Cantor–Bernstein–Schröder Theorem (196)
 Kuratowski's 14Set Theorem (239)
