Communication
Free
Faster access than browser!

# List of mathematical logic topics

This is a list of mathematical logic topics, by Wikipedia page. [1]

## Ackermann function

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive.

## ACL2

ACL2 (A Computational Logic for Applicative Common Lisp) is a software system consisting of a programming language, an extensible theory in a first-order logic, and a mechanical theorem prover.

In set theory, AD+ is an extension, proposed by W. Hugh Woodin, to the axiom of determinacy.

## Affine logic

Affine logic is a substructural logic whose proof theory rejects the structural rule of contraction.

## Age (model theory)

In model theory, the age of a structure (or model) A is the class of all finitely generated structures that are embeddable in A (i.e. isomorphic to substructures of A).

## Alan Turing

Alan Mathison Turing (23 June 1912 – 7 June 1954) was an English computer scientist, mathematician, logician, cryptanalyst, philosopher, and theoretical biologist.

## Aleph number

In mathematics, and in particular set theory, the aleph numbers are a sequence of numbers used to represent the cardinality (or size) of infinite sets that can be well-ordered.

## Alfred Tarski

Alfred Tarski (January 14, 1901 &ndash; October 26, 1983), born Alfred Teitelbaum,School of Mathematics and Statistics, University of St Andrews,, School of Mathematics and Statistics, University of St Andrews.

## Algebra of sets

The algebra of sets defines the properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion.

## Algebraic logic

In mathematical logic, algebraic logic is the reasoning obtained by manipulating equations with free variables.

## Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

## Alonzo Church

Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science.

## Alternative set theory

Generically, an alternative set theory is an alternative mathematical approach to the concept of set.

## Amalgamation property

In the mathematical field of model theory, the amalgamation property is a property of collections of structures that guarantees, under certain conditions, that two structures in the collection can be regarded as substructures of a larger one.

## Analytic proof

In mathematics, an analytic proof is a proof of a theorem in analysis that only makes use of methods from analysis, and which does not predominantly make use of algebraic or geometrical methods.

## Analytic set

In descriptive set theory, a subset of a Polish space X is an analytic set if it is a continuous image of a Polish space.

## Analytical hierarchy

In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy.

## Arithmetical hierarchy

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them.

## Arithmetical set

In mathematical logic, an arithmetical set (or arithmetic set) is a set of natural numbers that can be defined by a formula of first-order Peano arithmetic.

## Arithmetization of analysis

The arithmetization of analysis was a research program in the foundations of mathematics carried out in the second half of the 19th century.

## Atomic model (mathematical logic)

In model theory, an atomic model is a model such that the complete type of every tuple is axiomatized by a single formula.

## Automated Mathematician

The Automated Mathematician (AM) is one of the earliest successful discovery systems.

## Automated theorem proving

Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs.

## Ax–Grothendieck theorem

In mathematics, the Ax–Grothendieck theorem is a result about injectivity and surjectivity of polynomials that was proved independently by James Ax and Alexander Grothendieck.

## Ax–Kochen theorem

The Ax–Kochen theorem, named for James Ax and Simon B. Kochen, states that for each positive integer d there is a finite set Yd of prime numbers, such that if p is any prime not in Yd then every homogeneous polynomial of degree d over the p-adic numbers in at least d2+1 variables has a nontrivial zero.

## Axiom of choice

In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that the Cartesian product of a collection of non-empty sets is non-empty.

## Axiom of countable choice

The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function.

## Axiom of dependent choice

In mathematics, the axiom of dependent choice, denoted by \mathsf, is a weak form of the axiom of choice (\mathsf) that is still sufficient to develop most of real analysis.

## Axiom of determinacy

In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962.

## Axiom of projective determinacy

In mathematical logic, projective determinacy is the special case of the axiom of determinacy applying only to projective sets.

## Axiom of real determinacy

In mathematics, the axiom of real determinacy (abbreviated as ADR) is an axiom in set theory.

## Axiom schema

In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom.

## Axiomatic system

In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems.

## Ł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.

## Back-and-forth method

In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions.

## 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.

## Begriffsschrift

Begriffsschrift (German for, roughly, "concept-script") is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book.

## Beth number

In mathematics, the infinite cardinal numbers are represented by the Hebrew letter \aleph (aleph) indexed with a subscript that runs over the ordinal numbers (see aleph number).

## Boolean algebra

In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively.

## Boolean algebra (structure)

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice.

## Boolean-valued model

In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory.

## Borel equivalence relation

In mathematics, a Borel equivalence relation on a Polish space X is an equivalence relation on X that is a Borel subset of X &times; X (in the product topology).

In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction.

## C-minimal theory

In model theory, a branch of mathematical logic, a C-minimal theory is a theory that is "minimal" with respect to a ternary relation C with certain properties.

## Calculus of constructions

In mathematical logic and computer science, the calculus of constructions (CoC) is a type theory created by Thierry Coquand.

## Cantor's diagonal argument

In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers.

## Cantor's theorem

In elementary set theory, Cantor's theorem is a fundamental result that states that, for any set A, the set of all subsets of A (the power set of A, denoted by \mathcal(A)) has a strictly greater cardinality than A itself.

## Cardinal number

In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets.

## Cardinality

In mathematics, the cardinality of a set is a measure of the "number of elements of the set".

## Cartesian product

In set theory (and, usually, in other parts of mathematics), a Cartesian product is a mathematical operation that returns a set (or product set or simply product) from multiple sets.

## Categorical logic

Categorical logic is the branch of mathematics in which tools and concepts from category theory are applied to the study of mathematical logic.

## Church–Rosser theorem

In mathematics and theoretical computer science, the Church–Rosser theorem states that, when applying reduction rules to terms in the lambda calculus, the ordering in which the reductions are chosen does not make a difference to the eventual result.

## Church–Turing thesis

In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions.

## Cirquent calculus

Cirquent calculus is a proof calculus which manipulates graph-style constructs termed cirquents, as opposed to the traditional tree-style objects such as formulas or sequents.

## Class (set theory)

In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share.

## Cointerpretability

In mathematical logic, cointerpretability is a binary relation on formal theories: a formal theory T is cointerpretable in another such theory S, when the language of S can be translated into the language of T in such a way that S proves every formula whose translation is a theorem of T. The "translation" here is required to preserve the logical structure of formulas.

## Combinatory logic

Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic.

## 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.

## Complement (set theory)

In set theory, the complement of a set refers to elements not in.

## Complete Boolean algebra

In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound).

## Complete theory

In mathematical logic, a theory is complete if, for every formula in the theory's language, that formula or its negation is demonstrable.

## Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.

## Computability logic

Computability logic (CoL) is a research program and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth.

## Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

## Computable function

Computable functions are the basic objects of study in computability theory.

## Computable measure theory

In mathematics, computable measure theory is the part of computable analysis that deals with effective versions of measure theory.

## Computable model theory

Computable model theory is a branch of model theory which deals with questions of computability as they apply to model-theoretical structures.

## Computation

Computation is any type of calculation that includes both arithmetical and non-arithmetical steps and follows a well-defined model, for example an algorithm.

## Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

## Conservative extension

In mathematical logic, a conservative extension is a supertheory of a theory which is often convenient for proving theorems, but proves no new theorems about the language of the original theory.

## Consistency

In classical deductive logic, a consistent theory is one that does not contain a contradiction.

## Constructible universe

In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted L, is a particular class of sets that can be described entirely in terms of simpler sets.

## Constructive analysis

In mathematics, constructive analysis is mathematical analysis done according to some principles of constructive mathematics.

## Constructive proof

In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object.

## Continuum (set theory)

In the mathematical field of set theory, the continuum means the real numbers, or the corresponding (infinite) cardinal number, \mathfrak.

## Continuum hypothesis

In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets.

## Cook–Levin theorem

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete.

## Coq

In computer science, Coq is an interactive theorem prover.

## Countable set

In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.

## Criticism of non-standard analysis

Non-standard analysis and its offshoot, non-standard calculus, have been criticized by several authors, notably Errett Bishop, Paul Halmos, and Alain Connes.

## Curry–Howard correspondence

In programming language theory and proof theory, the Curry–Howard correspondence (also known as the Curry–Howard isomorphism or equivalence, or the proofs-as-programs and propositions- or formulae-as-types interpretation) is the direct relationship between computer programs and mathematical proofs.

## Cut-elimination theorem

The cut-elimination theorem (or Gentzen's Hauptsatz) is the central result establishing the significance of the sequent calculus.

## Decidability (logic)

In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas, or, more precisely, an algorithm that can and will return a boolean true or false value that is correct (instead of looping indefinitely, crashing, returning "don't know" or returning a wrong answer).

## Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

## Deduction theorem

In mathematical logic, the deduction theorem is a metatheorem of propositional and first-order logic.

## Definable real number

Informally, a definable real number is a real number that can be uniquely specified by its description.

## Definable set

In mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements are precisely those elements satisfying some formula in the first-order language of that structure.

## Descriptive complexity theory

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.

## Descriptive set theory

In mathematical logic, descriptive set theory (DST) is the study of certain classes of "well-behaved" subsets of the real line and other Polish spaces.

## Determinacy

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies.

## Diagonal lemma

In mathematical logic, the diagonal lemma or fixed point theorem establishes the existence of self-referential sentences in certain formal theories of the natural numbers—specifically those theories that are strong enough to represent all computable functions.

## Dialectica space

Dialectica spaces are a categorical way of constructing models of linear logic.

## Differentially closed field

In mathematics, a differential field K is differentially closed if every finite system of differential equations with a solution in some differential field extending K already has a solution in K. This concept was introduced by.

## Diophantine set

In mathematics, a Diophantine equation is an equation of the form P(x1,..., xj, y1,..., yk).

## Direct proof

In mathematics and logic, a direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually axioms, existing lemmas and theorems, without making any further assumptions.

## E theorem prover

E is a high performance theorem prover for full first-order logic with equality.

## Effective results in number theory

For historical reasons and in order to have application to the solution of Diophantine equations, results in number theory have been scrutinised more than in other branches of mathematics to see if their content is effectively computable.

## Ehrenfeucht–Fraïssé game

In the mathematical discipline of model theory, the Ehrenfeucht–Fraïssé game (also called back-and-forth games) is a technique for determining whether two structures are elementarily equivalent.

## Element (mathematics)

In mathematics, an element, or member, of a set is any one of the distinct objects that make up that set.

## Elementary Calculus: An Infinitesimal Approach

Elementary Calculus: An Infinitesimal approach is a textbook by H. Jerome Keisler.

## Elementary class

In model theory, a branch of mathematical logic, an elementary class (or axiomatizable class) is a class consisting of all structures satisfying a fixed first-order theory.

## Elementary equivalence

In model theory, a branch of mathematical logic, two structures M and N of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-sentences.

## Emil Leon Post

Emil Leon Post (February 11, 1897 – April 21, 1954) was an American mathematician and logician.

## Empty set

In mathematics, and more specifically set theory, the empty set or null set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero.

## Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem (German for "decision problem") is a challenge posed by David Hilbert in 1928.

## Epsilon-induction

In mathematics, \in-induction (epsilon-induction) is a variant of transfinite induction that can be used in set theory to prove that all sets satisfy a given property P. If the truth of the property for x follows from its truth for all elements of x, for every set x, then the property is true of all sets.

## Erdős cardinal

In mathematics, an Erdős cardinal, also called a partition cardinal is a certain kind of large cardinal number introduced by.

## Eurisko

Eurisko (Gr., I discover) is a program written by Douglas Lenat in RLL-1, a representation language itself written in the Lisp programming language.

## Existence theorem

In mathematics, an existence theorem is a theorem with a statement beginning 'there exist(s)..', or more generally 'for all,,...

## Existentially closed model

In model theory, a branch of mathematical logic, the notion of an existentially closed model (or existentially complete model) of a theory generalizes the notions of algebraically closed fields (for the theory of fields), real closed fields (for the theory of ordered fields), existentially closed groups (for the class of groups), and dense linear orders without endpoints (for the class of linear orders).

## Exponential field

In mathematics, an exponential field is a field that has an extra operation on its elements which extends the usual idea of exponentiation.

## Exponential hierarchy

In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, which is an exponential time analogue of the polynomial hierarchy.

## Extendible cardinal

In mathematics, extendible cardinals are large cardinals introduced by, who was partly motivated by reflection principles.

## Finite model theory

Finite model theory (FMT) is a subarea of model theory (MT).

## Finitism

Finitism is a philosophy of mathematics that accepts the existence only of finite mathematical objects.

## First-order logic

First-order logic—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.

## Forcing (mathematics)

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results.

## Forking extension

In model theory, a forking extension is an extension that is not whereas a non-forking extension is an extension that is as free as possible.

## Formal language

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it.

## Formal system

A formal system is the name of a logic system usually defined in the mathematical way.

## Foundations of mathematics

Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathematics.

## Function (mathematics)

In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.

## Functional predicate

In formal logic and related branches of mathematics, a functional predicate, or function symbol, is a logical symbol that may be applied to an object term to produce another object term.

## Fuzzy set

In mathematics, fuzzy sets (aka uncertain sets) are somewhat like sets whose elements have degrees of membership.

## Gandalf (theorem prover)

Gandalf is a first-order automated theorem prover applied to several domain-specific tasks such as Semantic web.

## 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.

## Gödel's incompleteness theorems

Gödel's incompleteness theorems are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic.

## General frame

In logic, general frames (or simply frames) are Kripke frames with an additional structure, which are used to model modal and intermediate logics.

## Gentzen's consistency proof

Gentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936.

## Georg Cantor's first set theory article

Georg Cantor's first set theory article was published in 1874 and contains the first theorems of transfinite set theory, which studies infinite sets and their properties.

## Gerhard Gentzen

Gerhard Karl Erich Gentzen (November 24, 1909 – August 4, 1945) was a German mathematician and logician.

## Giuseppe Peano

Giuseppe Peano (27 August 1858 – 20 April 1932) was an Italian mathematician and glottologist.

## Halting problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever.

## Hartogs number

In mathematics, specifically in axiomatic set theory, a Hartogs number is a particular kind of cardinal number.

Haskell Brooks Curry (September 12, 1900 – September 1, 1982) was an American mathematician and logician.

## Herbrand interpretation

In mathematical logic, a Herbrand interpretation is an interpretation in which all constants and function symbols are assigned very simple meanings.

## Herbrand structure

In first-order logic, a Herbrand structure S is a structure over a vocabulary &sigma;, that is defined solely by the syntactical properties of &sigma;.

## Higher-order logic

In mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and, sometimes, stronger semantics.

## Hilbert's program

In mathematics, Hilbert's program, formulated by German mathematician David Hilbert in the early part of the 20th century, was a proposed solution to the foundational crisis of mathematics, when early attempts to clarify the foundations of mathematics were found to suffer from paradoxes and inconsistencies.

## History of topos theory

This page gives some very general background to the mathematical idea of topos.

## HOL (proof assistant)

HOL (Higher Order Logic) denotes a family of interactive theorem proving systems using similar (higher-order) logics and implementation strategies.

## Hrushovski construction

In model theory, a branch of mathematical logic, the Hrushovski construction generalizes the Fraïssé limit by working with a notion of strong substructure \leq rather than \subseteq.

## Huge cardinal

In mathematics, a cardinal number κ is called huge if there exists an elementary embedding j: V → M from V into a transitive inner model M with critical point κ and Here, &alpha;M is the class of all sequences of length α whose elements are in M. Huge cardinals were introduced by.

## Hypercomputation

Hypercomputation or super-Turing computation refers to models of computation that can provide outputs that are not Turing computable.

## Hyperinteger

In non-standard analysis, a hyperinteger n is a hyperreal number that is equal to its own integer part.

## Hyperreal number

The system of hyperreal numbers is a way of treating infinite and infinitesimal quantities.

## Imaginary element

In mathematical model theory, an imaginary element of a structure is roughly a definable equivalence class.

## Impredicativity

Something that is impredicative, in mathematics and logic, is a self-referencing definition.

## Inaccessible cardinal

In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic.

## Indescribable cardinal

In mathematics, a Q-indescribable cardinal is a certain kind of large cardinal number that is hard to describe in some language Q. There are many different types of indescribable cardinals corresponding to different choices of languages Q. They were introduced by.

## Indiscernibles

In mathematical logic, indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula.

## Ineffable cardinal

In the mathematics of transfinite numbers, an ineffable cardinal is a certain kind of large cardinal number, introduced by.

## Infinitary logic

An infinitary logic is a logic that allows infinitely long statements and/or infinitely long proofs.

## Infinite descending chain

Given a set S with a partial order ≤, an infinite descending chain is an infinite, strictly decreasing sequence of elements x1 > x2 >...

## Infinity-Borel set

In set theory, a subset of a Polish space X is ∞-Borel if it can be obtained by starting with the open subsets of X, and transfinitely iterating the operations of complementation and wellordered union.

## Institution (computer science)

The notion of institution has been created by Joseph Goguen and Rod Burstall in the late 1970s.

## Interactive proof system

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties.

## Interior algebra

In abstract algebra, an interior algebra is a certain type of algebraic structure that encodes the idea of the topological interior of a set.

## Internal set theory

Internal set theory (IST) is a mathematical theory of sets developed by Edward Nelson that provides an axiomatic basis for a portion of the non-standard analysis introduced by Abraham Robinson.

## Interpretability

In mathematical logic, interpretability is a relation between formal theories that expresses the possibility of interpreting or translating one into the other.

## Interpretability logic

Interpretability logics comprise a family of modal logics that extend provability logic to describe interpretability or various related metamathematical properties and relations such as weak interpretability, Π1-conservativity, cointerpretability, tolerance, cotolerance, and arithmetic complexities.

## Interpretation (logic)

An interpretation is an assignment of meaning to the symbols of a formal language.

## Interpretation (model theory)

In model theory, interpretation of a structure M in another structure N (typically of a different signature) is a technical notion that approximates the idea of representing M inside N. For example every reduct or definitional expansion of a structure N has an interpretation in N. Many model-theoretic properties are preserved under interpretability.

## Intersection (set theory)

In mathematics, the intersection A ∩ B of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements.

## Intuitionistic logic

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof.

## Intuitionistic type theory

Intuitionistic type theory (also known as constructive type theory, or Martin-Löf type theory) is a type theory and an alternative foundation of mathematics.

## Isabelle (proof assistant)

The Isabelle theorem prover is an interactive theorem prover, a Higher Order Logic (HOL) theorem prover.

## Θ (set theory)

In set theory, Θ (pronounced like the letter theta) is the least nonzero ordinal α such that there is no surjection from the reals onto α. If the axiom of choice (AC) holds (or even if the reals can be wellordered), then Θ is simply (2^)^+, the cardinal successor of the cardinality of the continuum.

## Μ operator

In computability theory, the μ operator, minimization operator, or unbounded search operator searches for the least natural number with a given property.

## Jacques Herbrand

Jacques Herbrand (12 February 1908 – 27 July 1931) was a French mathematician.

## 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.

## Kripke semantics

Kripke semantics (also known as relational semantics or frame semantics, and often confused with possible world semantics) is a formal semantics for non-classical logic systems created in the late 1950s and early 1960s by Saul Kripke and André Joyal.

## Kripke–Platek set theory with urelements

The Kripke–Platek set theory with urelements (KPU) is an axiom system for set theory with urelements, based on the traditional (urelement-free) Kripke–Platek set theory.

## Kurt Gödel

Kurt Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.

## L(R)

In set theory, L(R) (pronounced L of R) is the smallest transitive inner model of ZF containing all the ordinals and all the reals.

## L. E. J. Brouwer

Luitzen Egbertus Jan Brouwer (27 February 1881 – 2 December 1966), usually cited as L. E. J. Brouwer but known to his friends as Bertus, was a Dutch mathematician and philosopher, who worked in topology, set theory, measure theory and complex analysis.

## Lambda calculus

Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.

## Lambda cube

In mathematical logic and type theory, the λ-cube is a framework for exploring the axes of refinement in Thierry Coquand's calculus of constructions, starting from the simply typed lambda calculus (written as λ→ in the cube diagram) as the vertex of a cube placed at the origin, and the calculus of constructions (higher-order dependently typed polymorphic lambda calculus; written as λPω in the diagram) as its diametrically opposite vertex.

## Large cardinal

In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers.

## Löb's theorem

In mathematical logic, Löb's theorem states that in any formal system F with Peano arithmetic (PA), for any formula P, if it is provable in F that "if P is provable in F then P is true", then P is provable in F. More formally, if Bew(#P) means that the formula P with Gödel number #P is provable (from the German "beweisbar"), then or An immediate corollary of Löb's theorem is that, if P is not provable in PA, then "if P is provable in PA, then P is true" is not provable in PA.

## Löwenheim–Skolem theorem

In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ. The result implies that first-order theories are unable to control the cardinality of their infinite models, and that no first-order theory with an infinite model can have a unique model up to isomorphism.

## Lightface analytic game

In descriptive set theory, a lightface analytic game is a game whose payoff set A is a \Sigma^1_1 subset of Baire space; that is, there is a tree T on \omega\times\omega which is a computable subset of (\omega\times\omega)^.

## Limit ordinal

In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal.

## Lindenbaum–Tarski algebra

In mathematical logic, the Lindenbaum–Tarski algebra (or Lindenbaum algebra) of a logical theory T consists of the equivalence classes of sentences of the theory (i.e., the quotient, under the equivalence relation ~ defined such that p ~ q exactly when p and q are provably equivalent in T).

## Lindström quantifier

In mathematical logic, a Lindström quantifier is a generalized polyadic quantifier.

## Linear logic

Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter.

## List of complexity classes

This is a list of complexity classes in computational complexity theory.

## List of computability and complexity topics

This is a list of computability and complexity topics, by Wikipedia page.

## List of first-order theories

In mathematical logic, a first-order theory is given by a set of axioms in some language.

## Logic for Computable Functions

Logic for Computable Functions (LCF) is an interactive automated theorem prover developed at the universities of Edinburgh and Stanford by Robin Milner and others in 1972.

## Logical framework

In logic, a logical framework provides a means to define (or present) a logic as a signature in a higher-order type theory in such a way that provability of a formula in the original logic reduces to a type inhabitation problem in the framework type theory.

## Ludics

In proof theory, ludics is an analysis of the principles governing inference rules of mathematical logic.

## Mahlo cardinal

In mathematics, a Mahlo cardinal is a certain kind of large cardinal number.

## Many-sorted logic

Many-sorted logic can reflect formally our intention not to handle the universe as a homogeneous collection of objects, but to partition it in a way that is similar to types in typeful programming.

## Markov algorithm

In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols.

## Mathematical induction

Mathematical induction is a mathematical proof technique.

## Mathematical proof

In mathematics, a proof is an inferential argument for a mathematical statement.

## Measurable cardinal

In mathematics, a measurable cardinal is a certain kind of large cardinal number.

## Metamathematics

Metamathematics is the study of mathematics itself using mathematical methods.

## Mizar system

The Mizar system consists of a formal language for writing mathematical definitions and proofs, a proof assistant, which is able to mechanically check proofs written in this language, and a library of formalized mathematics, which can be used in the proof of new theorems.

## Model checking

In computer science, model checking or property checking refers to the following problem: Given a model of a system, exhaustively and automatically check whether this model meets a given specification.

## Model complete theory

In model theory, a first-order theory is called model complete if every embedding of models is an elementary embedding.

## Morley rank

In mathematical logic, Morley rank, introduced by, is a means of measuring the size of a subset of a model of a theory, generalizing the notion of dimension in algebraic geometry.

## Morley's categoricity theorem

In model theory, a branch of mathematical logic, a theory is κ-categorical (or categorical in κ) if it has exactly one model of cardinality κ up to isomorphism.

## Morse–Kelley set theory

In the foundations of mathematics, Morse–Kelley set theory (MK), Kelley–Morse set theory (KM), Morse–Tarski set theory (MT), Quine–Morse set theory (QM) or the system of Quine and Morse is a first order axiomatic set theory that is closely related to von Neumann–Bernays–Gödel set theory (NBG).

## Naive set theory

Naïve set theory is any of several theories of sets used in the discussion of the foundations of mathematics.

## Natural proof

In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one.

## New Foundations

In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica.

## Non-standard analysis

The history of calculus is fraught with philosophical debates about the meaning and logical validity of fluxions or infinitesimal numbers.

## Non-standard calculus

In mathematics, non-standard calculus is the modern application of infinitesimals, in the sense of non-standard analysis, to differential and integral calculus.

## Non-standard model

In model theory, a discipline within mathematical logic, a non-standard model is a model of a theory that is not isomorphic to the intended model (or standard model).

## Non-standard model of arithmetic

In mathematical logic, a non-standard model of arithmetic is a model of (first-order) Peano arithmetic that contains non-standard numbers.

## Nonfirstorderizability

In formal logic, nonfirstorderizability is the inability of an expression to be adequately captured in particular theories in first-order logic.

## NP-completeness

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

## O-minimal theory

In mathematical logic, and more specifically in model theory, an infinite structure (M,&lt;,...) which is totally ordered by Knight, Pillay and Steinhorn (1986), Pillay and Steinhorn (1988).

## Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.

## Ordinal number

In set theory, an ordinal number, or ordinal, is one generalization of the concept of a natural number that is used to describe a way to arrange a collection of objects in order, one after another.

## Original proof of Gödel's completeness theorem

The proof of Gödel's completeness theorem given by Kurt Gödel in his doctoral dissertation of 1929 (and a rewritten version of the dissertation, published as an article in 1930) is not easy to read today; it uses concepts and formalism that are no longer used and terminology that is often obscure.

## Outline of logic

Logic is the formal science of using reason and is considered a branch of both philosophy and mathematics.

## Overspill

In non-standard analysis, a branch of mathematics, overspill (referred to as overflow by Goldblatt (1998, p. 129)) is a widely used proof technique.

## P versus NP problem

The P versus NP problem is a major unsolved problem in computer science.

Paradox is an automated theorem proving system developed by Koen Lindström Claessen and Niklas Sörensson at the Chalmers University of Technology.

## Peano axioms

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano.

## Perfect set property

In descriptive set theory, a subset of a Polish space has the perfect set property if it is either countable or has a nonempty perfect subset (Kechris 1995, p. 150).

## Polish space

In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset.

## Polynomial hierarchy

In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

## Positive set theory

In mathematical logic, positive set theory is the name for a class of alternative set theories in which the axiom of comprehension.

## Post correspondence problem

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.

## Post's theorem

In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.

## Potential isomorphism

In mathematical logic and in particular in model theory, a potential isomorphism is a collection of finite partial isomorphisms between two models which satisfies certain closure conditions.

## Power set

In mathematics, the power set (or powerset) of any set is the set of all subsets of, including the empty set and itself, variously denoted as, 𝒫(), ℘() (using the "Weierstrass p"),,, or, identifying the powerset of with the set of all functions from to a given set of two elements,.

## Pregeometry (model theory)

Pregeometry, and in full combinatorial pregeometry, are essentially synonyms for "matroid".

## Presburger arithmetic

Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929.

## Prewellordering

In set theory, a prewellordering is a binary relation \le that is transitive, total, and wellfounded (more precisely, the relation x\le y\land y\nleq x is wellfounded).

## Prime model

In mathematics, and in particular model theory, a prime model is a model which is as simple as possible.

## Primitive recursive function

In computability theory, primitive recursive functions are a class of functions that are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions (µ-recursive functions are also called partial recursive).

## Principia Mathematica

The Principia Mathematica (often abbreviated PM) is a three-volume work on the foundations of mathematics written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913.

## Projective hierarchy

In the mathematical field of descriptive set theory, a subset A of a Polish space X is projective if it is \boldsymbol^1_n for some positive integer n. Here A is.

## Proof by exhaustion

Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction, or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases and each type of case is checked to see if the proposition in question holds.

## Proof net

In proof theory, proof nets are a geometrical method of representing proofs that eliminates two forms of bureaucracy that differentiates proofs: (A) irrelevant syntactical features of regular proof calculi such as the natural deduction calculus and the sequent calculus, and (B) the order of rules applied in a derivation.

## Proof-theoretic semantics

Proof-theoretic semantics is an approach to the semantics of logic that attempts to locate the meaning of propositions and logical connectives not in terms of interpretations, as in Tarskian approaches to semantics, but in the role that the proposition or logical connective plays within the system of inference.

## Property of Baire

A subset A of a topological space X has the property of Baire (Baire property, named after René-Louis Baire), or is called an almost open set, if it differs from an open set by a meager set; that is, if there is an open set U\subseteq X such that A \bigtriangleup U is meager (where \bigtriangleup denotes the symmetric difference).

## Provability logic

Provability logic is a modal logic, in which the box (or "necessity") operator is interpreted as 'it is provable that'.

## Prover9

Prover9 is an automated theorem prover for First-order and equational logic developed by William McCune.

## Pseudoelementary class

In logic, a pseudoelementary class is a class of structures derived from an elementary class (one definable in first-order logic) by omitting some of its sorts and relations.

## QED manifesto

The QED manifesto was a proposal for a computer-based database of all mathematical knowledge, strictly formalized and with all proofs having been checked automatically.

## Quantifier elimination

Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science.

## Ramsey cardinal

In mathematics, a Ramsey cardinal is a certain kind of large cardinal number introduced by and named after Frank P. Ramsey.

## Rank-into-rank

In set theory, a branch of mathematics, a rank-into-rank is a large cardinal property defined by one of the following four axioms given in order of increasing consistency strength.

## Rózsa Péter

Rózsa Péter, born Politzer, (17 February 1905 &ndash; 16 February 1977) was a Hungarian mathematician and logician.

## Recursion

Recursion occurs when a thing is defined in terms of itself or of its type.

## Recursive definition

A recursive definition (or inductive definition) in mathematical logic and computer science is used to define the elements in a set in terms of other elements in the set (Aczel 1978:740ff).

## Recursive language

In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.

## Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.

## Recursively enumerable set

In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if.

## Reduct

In universal algebra and in model theory, a reduct of an algebraic structure is obtained by omitting some of the operations and relations of that structure.

In logic, reductio ad absurdum ("reduction to absurdity"; also argumentum ad absurdum, "argument to absurdity") is a form of argument which attempts either to disprove a statement by showing it inevitably leads to a ridiculous, absurd, or impractical conclusion, or to prove one by showing that if it were not true, the result would be absurd or impossible.

## Relevance logic

Relevance logic, also called relevant logic, is a kind of non-classical logic requiring the antecedent and consequent of implications to be relevantly related.

## Remarkable cardinal

In mathematics, a remarkable cardinal is a certain kind of large cardinal number.

## Resolution (logic)

In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic.

## Reverse mathematics

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics.

## Rice's theorem

In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable.

In the foundations of mathematics, Russell's paradox (also known as Russell's antinomy), discovered by Bertrand Russell in 1901, showed that some attempted formalizations of the naïve set theory created by Georg Cantor led to a contradiction.

## Saharon Shelah

Saharon Shelah (שהרן שלח) is an Israeli mathematician.

## Sahlqvist formula

In modal logic, Sahlqvist formulas are a certain kind of modal formula with remarkable properties.

## Saturated model

In mathematical logic, and particularly in its subfield model theory, a saturated model M is one which realizes as many complete types as may be "reasonably expected" given its size.

## Schröder–Bernstein theorem

In set theory, the Schröder–Bernstein theorem states that, if there exist injective functions and between the sets and, then there exists a bijective function.

## Second-order arithmetic

In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets.

## Second-order logic

In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic.

## Self-verifying theories

Self-verifying theories are consistent first-order systems of arithmetic much weaker than Peano arithmetic that are capable of proving their own consistency.

## Sequent

In mathematical logic, a sequent is a very general kind of conditional assertion.

## Sequent calculus

Sequent calculus is, in essence, a style of formal logical argumentation where every line of a proof is a conditional tautology (called a sequent by Gerhard Gentzen) instead of an unconditional tautology.

## Set (mathematics)

In mathematics, a set is a collection of distinct objects, considered as an object in its own right.

## Set theory

Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects.

## Set theory (music)

Musical set theory provides concepts for categorizing musical objects and describing their relationships.

## Shelah cardinal

In axiomatic set theory, Shelah cardinals are a kind of large cardinals.

## Signature (logic)

In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language.

## Simple theorems in the algebra of sets

The simple theorems in the algebra of sets are some of the elementary properties of the algebra of union (infix &cup), intersection (infix &cap), and set complement (postfix ') of sets.

## Simply typed lambda calculus

The simply typed lambda calculus (\lambda^\to), a form of type theory, is a typed interpretation of the lambda calculus with only one type constructor: \to that builds function types.

## Singleton (mathematics)

In mathematics, a singleton, also known as a unit set, is a set with exactly one element.

## Skolem normal form

In mathematical logic, a formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers.

In mathematical logic and philosophy, Skolem's paradox is a seeming contradiction that arises from the downward Löwenheim–Skolem theorem.

## Soundness

In mathematical logic, a logical system has the soundness property if and only if every formula that can be proved in the system is logically valid with respect to the semantics of the system.

## Space hierarchy theorem

In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions.

## Spectrum of a theory

In model theory, a branch of mathematical logic, the spectrum of a theory is given by the number of isomorphism classes of models in various cardinalities.

## Stability spectrum

In model theory, a branch of mathematical logic, a complete first-order theory T is called stable in λ (an infinite cardinal number), if the Stone space of every model of T of size ≤ λ has itself size ≤ λ. T is called a stable theory if there is no upper bound for the cardinals κ such that T is stable in κ. The stability spectrum of T is the class of all cardinals κ such that T is stable in κ. For countable theories there are only four possible stability spectra.

## Stable group

In model theory, a stable group is a group that is stable in the sense of stability theory.

## Stable theory

In model theory, a complete theory is called stable if it does not have too many types.

## Standard part function

In non-standard analysis, the standard part function is a function from the limited (finite) hyperreal numbers to the real numbers.

## Stephen Cole Kleene

Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician.

## Strength (mathematical logic)

The relative strength of two systems of formal logic can be defined via model theory.

## Strict logic

Strict logic is essentially synonymous with relevant logic, though it can be characterized proof-theoretically as.

## Strong cardinal

In set theory, a strong cardinal is a type of large cardinal.

## Strongly minimal theory

In model theory&mdash;a branch of mathematical logic&mdash;a minimal structure is an infinite one-sorted structure such that every subset of its domain that is definable with parameters is either finite or cofinite.

## Structural induction

Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields.

## Structural proof theory

In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof.

## Structural rule

In proof theory, a structural rule is an inference rule that does not refer to any logical connective, but instead operates on the judgment or sequents directly.

## Structure (mathematical logic)

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

## Subset

In mathematics, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide.

## Substructural logic

In logic, a substructural logic is a logic lacking one of the usual structural rules (e.g. of classical and intuitionistic logic), such as weakening, contraction, exchange or associativity.

## Substructure

In mathematical logic, an (induced) substructure or (induced) subalgebra is a structure whose domain is a subset of that of a bigger structure, and whose functions and relations are the traces of the functions and relations of the bigger structure.

## Subtle cardinal

In mathematics, subtle cardinals and ethereal cardinals are closely related kinds of large cardinal number.

## Successor ordinal

In set theory, the successor of an ordinal number α is the smallest ordinal number greater than α.

## Supercompact cardinal

In set theory, a supercompact cardinal is a type of large cardinal.

## Superstrong cardinal

In mathematics, a cardinal number &kappa; is called superstrong if and only if there exists an elementary embedding j: V &rarr; M from V into a transitive inner model M with critical point &kappa; and V_ &sube; M. Similarly, a cardinal κ is n-superstrong if and only if there exists an elementary embedding j: V &rarr; M from V into a transitive inner model M with critical point &kappa; and V_ &sube; M. Akihiro Kanamori has shown that the consistency strength of an n+1-superstrong cardinal exceeds that of an n-huge cardinal for each n > 0.

## Suslin's problem

In mathematics, Suslin's problem is a question about totally ordered sets posed by and published posthumously.

## System F

System F, also known as the (Girard–Reynolds) polymorphic lambda calculus or the second-order lambda calculus, is a typed lambda calculus that differs from the simply typed lambda calculus by the introduction of a mechanism of universal quantification over types.

## Systems of Logic Based on Ordinals

Systems of Logic Based on Ordinals was the PhD dissertation of the mathematician Alan Turing.

## T-schema

The T-schema or truth schema (not to be confused with 'Convention T') is used to give an inductive definition of truth which lies at the heart of any realisation of Alfred Tarski's semantic theory of truth.

## Tame group

In mathematical group theory, a tame group is a certain kind of group defined in model theory.

## Tarski's exponential function problem

In model theory, Tarski's exponential function problem asks whether the theory of the real numbers together with the exponential function is decidable.

## Tarski's undefinability theorem

Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1936, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics.

## Tautology (logic)

In logic, a tautology (from the Greek word ταυτολογία) is a formula or assertion that is true in every possible interpretation.

## Term algebra

In universal algebra and mathematical logic, a term algebra is a freely generated algebraic structure over a given signature.

## Theory (mathematical logic)

In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language.

## Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

## Time hierarchy theorem

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines.

## Tolerant sequence

In mathematical logic, a tolerant sequence is a sequence of formal theories such that there are consistent extensions of these theories with each S_ interpretable in S_i.

## Trakhtenbrot's theorem

In logic, finite model theory, and computability theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) states that the problem of validity in first-order logic on the class of all finite models is undecidable.

## Transfer principle

In model theory, a transfer principle states that all statements of some language that are true for some structure are true for another structure.

## Transfinite induction

Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers.

## Tree (descriptive set theory)

In descriptive set theory, a tree on a set X is a collection of finite sequences of elements of X such that every prefix of a sequence in the collection also belongs to the collection.

## Tree (set theory)

In set theory, a tree is a partially ordered set (T, \omega + 1.

## Turing degree

In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.

## Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

## Type (model theory)

In model theory and related areas of mathematics, a type is an object that, loosely speaking, describes how a (real or possible) element or elements in a mathematical structure might behave.

## Type theory

In mathematics, logic, and computer science, a type theory is any of a class of formal systems, some of which can serve as alternatives to set theory as a foundation for all mathematics.

## Typed lambda calculus

A typed lambda calculus is a typed formalism that uses the lambda-symbol (\lambda) to denote anonymous function abstraction.

## Ultrafinitism

In the philosophy of mathematics, ultrafinitism, also known as ultraintuitionism, strict-finitism, actualism, and strong-finitism, is a form of finitism.

## Ultraproduct

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic.

## Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.

## Unfoldable cardinal

In mathematics, an unfoldable cardinal is a certain kind of large cardinal number.

## Uniformization (set theory)

In set theory, the axiom of uniformization, a weak form of the axiom of choice, states that if R is a subset of X\times Y, where X and Y are Polish spaces, then there is a subset f of R that is a partial function from X to Y, and whose domain (in the sense of the set of all x such that f(x) exists) equals Such a function is called a uniformizing function for R, or a uniformization of R. To see the relationship with the axiom of choice, observe that R can be thought of as associating, to each element of X, a subset of Y. A uniformization of R then picks exactly one element from each such subset, whenever the subset is nonempty.

## Union (set theory)

In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.

## Universally measurable set

In mathematics, a subset A of a Polish space X is universally measurable if it is measurable with respect to every complete probability measure on X that measures all Borel subsets of X. In particular, a universally measurable set of reals is necessarily Lebesgue measurable (see #Finiteness condition below).

## Universe (mathematics)

In mathematics, and particularly in set theory, category theory, type theory, and the foundations of mathematics, a universe is a collection that contains all the entities one wishes to consider in a given situation.

## Urelement

In set theory, a branch of mathematics, an urelement or ur-element (from the German prefix ur-, 'primordial') is an object (concrete or abstract) that is not a set, but that may be an element of a set.

## Vampire (theorem prover)

Vampire is an automatic theorem prover for first-order classical logic developed in the School of Computer Science at the University of Manchester by Andrei Voronkov together with Kryštof Hoder and previously with Alexandre Riazanov.

## Vaught conjecture

The Vaught conjecture is a conjecture in the mathematical field of model theory originally proposed by Robert Lawson Vaught in 1961.

## Von Neumann universe

In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted V, is the class of hereditary well-founded sets.

## Weak interpretability

In mathematical logic, weak interpretability is a notion of translation of logical theories, introduced together with interpretability by Alfred Tarski in 1953.

## Weakly compact cardinal

In mathematics, a weakly compact cardinal is a certain kind of cardinal number introduced by; weakly compact cardinals are large cardinals, meaning that their existence cannot be proven from the standard axioms of set theory.

## Weakly o-minimal structure

In model theory, a weakly o-minimal structure is a model theoretic structure whose definable sets in the domain are just finite unions of convex sets.

## Well-founded relation

In mathematics, a binary relation, R, is called well-founded (or wellfounded) on a class X if every non-empty subset S ⊆ X has a minimal element with respect to R, that is an element m not related by sRm (for instance, "s is not smaller than m") for any s ∈ S. In other words, a relation is well founded if Some authors include an extra condition that R is set-like, i.e., that the elements less than any given element form a set.

## Well-order

In mathematics, a well-order (or well-ordering or well-order relation) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering.

## 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.

## Woodin cardinal

In set theory, a Woodin cardinal (named for W. Hugh Woodin) is a cardinal number λ such that for all functions there exists a cardinal κ j(f)(κ) &sube; M. An equivalent definition is this: λ is Woodin if and only if λ is strongly inaccessible and for all A \subseteq V_\lambda there exists a \lambda_A -A-strong.

## Word problem for groups

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element.

## Zariski geometry

In mathematics, a Zariski geometry consists of an abstract structure introduced by Ehud Hrushovski and Boris Zilber, in order to give a characterisation of the Zariski topology on an algebraic curve, and all its powers.

## Zermelo set theory

Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory.

## Zermelo–Fraenkel set theory

In mathematics, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox.

## Zero sharp

In the mathematical discipline of set theory, 0# (zero sharp, also 0#) is the set of true formulae about indiscernibles and order-indiscernibles in the Gödel constructible universe.

## Zorn's lemma

Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max Zorn and Kazimierz Kuratowski, is a proposition of set theory that states that a partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily contains at least one maximal element.

## References

Hey! We are on Facebook now! »