Knaster–Tarski theorem
In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following: Let (L, ≤) be a complete lattice and let f : L
Tarski's high school algebra problem
In mathematical logic, Tarski's high school algebra problem was a question posed by Alfred Tarski. It asks whether there are identities involving addition, multiplication, and exponentiation over the
Gödel's speed-up theorem
In mathematics, Gödel's speed-up theorem, proved by Gödel, shows that there are theorems whose proofs can be drastically shortened by working in more powerful axiomatic systems. Kurt Gödel showed how
Kanamori–McAloon theorem
In mathematical logic, the Kanamori–McAloon theorem, due to , gives an example of an incompleteness in Peano arithmetic, similar to that of the Paris–Harrington theorem. They showed that a certain fin
Kleene's recursion theorem
In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephe
Tennenbaum's theorem
Tennenbaum's theorem, named for Stanley Tennenbaum who presented the theorem in 1959, is a result in mathematical logic that states that no countable nonstandard model of first-order Peano arithmetic
Compression theorem
In computational complexity theory, the compression theorem is an important theorem about the complexity of computable functions. The theorem states that there exists no largest complexity class, with
Post's theorem
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
Robinson's joint consistency theorem
Robinson's joint consistency theorem is an important theorem of mathematical logic. It is related to Craig interpolation and Beth definability. The classical formulation of Robinson's joint consistenc
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of provability in formal axiomatic theories. These results, published by Kurt Gödel in 1931, a
Categorical theory
In mathematical logic, a theory is categorical if it has exactly one model (up to isomorphism). Such a theory can be viewed as defining its model, uniquely characterizing its structure. In first-order
Łoś–Vaught test
In model theory, a branch of mathematical logic, the Łoś–Vaught test is a criterion for a theory to be complete, unable to be augmented without becoming inconsistent. For theories in classical logic,
König's theorem (set theory)
In set theory, König's theorem states that if the axiom of choice holds, I is a set, and are cardinal numbers for every i in I, and for every i in I, then The sum here is the cardinality of the disjoi
Löb's theorem
In mathematical logic, Löb's theorem states that in Peano arithmetic (PA) (or any formal system including PA), for any formula P, if it is provable in PA that "if P is provable in PA then P is true",
Borel determinacy theorem
In descriptive set theory, the Borel determinacy theorem states that any Gale–Stewart game whose payoff set is a Borel set is determined, meaning that one of the two players will have a winning strate
Löwenheim–Skolem theorem
In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem. The precise formulation is given below. I
Rice's theorem
In computability theory, Rice's theorem states that all non-trivial semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the pro
Wilkie's theorem
In mathematics, Wilkie's theorem is a result by Alex Wilkie about the theory of ordered fields with an exponential function, or equivalently about the geometric nature of exponential varieties.
Bourbaki–Witt theorem
In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed point theorem for partially ordered sets. It states that if X is a non-empty ch
Szpilrajn extension theorem
In order theory, the Szpilrajn extension theorem (also called the order-extension principle), proved by Edward Szpilrajn in 1930, states that every strict partial order is contained in a total order.
Herbrand's theorem
Herbrand's theorem is a fundamental result of mathematical logic obtained by Jacques Herbrand (1930). It essentially allows a certain kind of reduction of first-order logic to propositional logic. Alt
Tarski's theorem about choice
In mathematics, Tarski's theorem, proved by Alfred Tarski, states that in ZF the theorem "For every infinite set , there is a bijective map between the sets and " implies the axiom of choice. The oppo
Paris–Harrington theorem
In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, is true, but not provable in Peano ar
Richardson's theorem
In mathematics, Richardson's theorem establishes the undecidability of the equality of real numbers defined by expressions involving integers, π, and exponential and sine functions. It was proved in 1
Banach–Tarski paradox
The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite numb
Compactness theorem
In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model t
List of set identities and relations
This article lists mathematical properties and laws of sets, involving the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion. It
Schröder–Bernstein theorem for measurable spaces
The Cantor–Bernstein–Schroeder theorem of set theory has a counterpart for measurable spaces, sometimes called the Borel Schroeder–Bernstein theorem, since measurable spaces are also called Borel spac
Lusin's separation theorem
In descriptive set theory and mathematical logic, Lusin's separation theorem states that if A and B are disjoint analytic subsets of Polish space, then there is a Borel set C in the space such that A
Codd's theorem
Codd's theorem states that relational algebra and the domain-independent relational calculus queries, two well-known foundational query languages for the relational model, are precisely equivalent in
Tarski's undefinability theorem
Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1933, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informall
Cantor's theorem
In mathematical set theory, Cantor's theorem is a fundamental result which states that, for any set , the set of all subsets of the power set of has a strictly greater cardinality than itself. For fin
Frege's theorem
In metalogic and metamathematics, Frege's theorem is a metatheorem that states that the Peano axioms of arithmetic can be derived in second-order logic from Hume's principle. It was first proven, info
Deduction theorem
In mathematical logic, a deduction theorem is a metatheorem that justifies doing conditional proofs—to prove an implication A → B, assume A as an hypothesis and then proceed to derive B—in systems tha
Rice–Shapiro theorem
In computability theory, the Rice–Shapiro theorem is a generalization of Rice's theorem, and is named after Henry Gordon Rice and Norman Shapiro.
Schröder–Bernstein theorem
In set theory, the Schröder–Bernstein theorem states that, if there exist injective functions f : A → B and g : B → A between the sets A and B, then there exists a bijective function h : A → B. In ter
Easton's theorem
In set theory, Easton's theorem is a result on the possible cardinal numbers of powersets. (extending a result of Robert M. Solovay) showed via forcing that the only constraints on permissible values
Lindström's theorem
In mathematical logic, Lindström's theorem (named after Swedish logician Per Lindström, who published it in 1969) states that first-order logic is the strongest logic (satisfying certain conditions, e
Church–Rosser theorem
In lambda calculus, the Church–Rosser theorem states that, when applying reduction rules to terms, the ordering in which the reductions are chosen does not make a difference to the eventual result. Mo
Beth definability
In mathematical logic, Beth definability is a result that connects implicit definability of a property to its explicit definability. Specifically Beth definability states that the two senses of defina
Well-ordering theorem
In mathematics, the well-ordering theorem, also known as Zermelo's theorem, states that every set can be well-ordered. A set X is well-ordered by a strict total order if every non-empty subset of X ha
Craig's theorem
In mathematical logic, Craig's theorem states that any recursively enumerable set of well-formed formulas of a first-order language is (primitively) recursively axiomatizable. This result is not relat
Completeness of atomic initial sequents
In sequent calculus, the completeness of atomic initial sequents states that initial sequents A ⊢ A (where A is an arbitrary formula) can be derived from only atomic initial sequents p ⊢ p (where p is
Cut-elimination theorem
The cut-elimination theorem (or Gentzen's Hauptsatz) is the central result establishing the significance of the sequent calculus. It was originally proved by Gerhard Gentzen in his landmark 1934 paper
Gödel's completeness theorem
Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic. The completeness th
Ultraproduct
The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direc
Barwise compactness theorem
In mathematical logic, the Barwise compactness theorem, named after Jon Barwise, is a generalization of the usual compactness theorem for first-order logic to a certain class of infinitary languages.
Goodstein's theorem
In mathematical logic, Goodstein's theorem is a statement about the natural numbers, proved by Reuben Goodstein in 1944, which states that every Goodstein sequence eventually terminates at 0. Kirby an
Halpern–Läuchli theorem
In mathematics, the Halpern–Läuchli theorem is a partition result about finite products of infinite trees. Its original purpose was to give a model for set theory in which the Boolean prime ideal theo
Cantor's diagonal argument
In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument, the anti-diagonal argument, the diagonal method, and Cantor's diagonalization proof, w
Von Neumann paradox
In mathematics, the von Neumann paradox, named after John von Neumann, is the idea that one can break a planar figure such as the unit square into sets of points and subject each set to an area-preser
Extension by new constant and function names
In mathematical logic, a theory can be extended withnew constants or function names under certain conditions with assurance that the extension will introduceno contradiction. Extension by definitions