Theorem of the Day  

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.

1. Cook's Theorem on NP-completeness (14)
2. The Well-Ordering Theorem (17)
3. The Axiom of Choice (cf. 17)
4. The Banach–Tarski Paradox (cf. 17)
5. Cantor's Uncountability Theorem (22)
6. Cantor's Theorem (23)
7. The DPRM Theorem (43)
8. Goodstein's Theorem (73)
9. Gödel's First Incompleteness Theorem (74)
10. Gödel's Second Incompleteness Theorem (75)
11. Lamé's Theorem (87)
12. The Parking Function Formula (103)
13. The Pumping Lemma (105)
14. The Robbins Problem (110)
15. De Morgan's Laws (111)
16. The Lucas–Lehmer Test (127)
17. Vaughan Pratt's Theorem (138)
18. Strassen's Matrix Theorem (139)
19. The Robinson–Schensted–Knuth Correspondence (143)
20. Quadratic Nonresidue is Zero-Knowledge Provable (161)
21. Haken's Unknot Theorem (166)
22. The Max-Flow Min-Cut Theorem (168)
23. The Greibach Normal Form Theorem (180)
24. The Insolvability of the Entscheidungsproblem (186)
25. Karp's Theorem (Detail) (187)
26. The Rotation Distance Bound (192)
27. The Cantor–Bernstein–Schröder Theorem (196)
28. Kuratowski's 14-Set Theorem (239)
29. Countability of the Rationals (255)
30. Turing-completeness of Conway's Game of Life (266)