Browse By

All Logic and Foundations

Proved results about formal systems, provability and the limits of what a system of axioms can settle. Belongs here: foundational theorems such as those establishing incompleteness or independence. Does not belong here: results in an ordinary branch that happen to be proved by formal methods.

Facts

Comparison

Era Of Emergence

1850 1

All Logic and Foundations

90 entries

Branch

Topic Area

Proved

Proved By

Named After

Statement Form

Proved By (Other Fields)

Matiyasevich's Theorem

Morley's Categoricity Theorem

Myhill Isomorphism Theorem

Myhill-Nerode Theorem

Omitting Types Theorem

Paris-Harrington Theorem

Pataraia's Theorem

PCP Theorem

Post's Theorem

Proof by Exhaustion

Proof Without Words

Rice's Theorem

Rice-Shapiro Theorem

Richardson's Theorem

Robinson's Joint Consistency Theorem

Ryll-Nardzewski Theorem

Sahlqvist Correspondence Theorem

Savitch's Theorem

Sharp-P-Completeness of 01-Permanent

Shoenfield's Absoluteness Theorem

Silver's Theorem

Sipser-Lautemann Theorem

S-m-n Theorem

Solovay's Theorem

Soundness Theorem

Space Hierarchy Theorem

Tarski's Undefinability Theorem

Tarski-Seidenberg Theorem

Tennenbaum's Theorem

Time Hierarchy Theorem

Toda's Theorem

Trakhtenbrot's Theorem

Transfinite Recursion Theorem

Turing's Proof

Undecidability of the Halting Problem

Valiant-Vazirani Theorem

Vaught's Theorem

Wilkie's Theorem

Zermelo's Well-Ordering Theorem

Zorn's Lemma