354 relations: Ackermann function, ACL2, AD+, Affine logic, Age (model theory), Alan Turing, Aleph number, Alfred Tarski, Algebra of sets, Algebraic logic, Algorithm, Alonzo Church, Alternative set theory, Amalgamation property, Analytic proof, Analytic set, Analytical hierarchy, Arithmetical hierarchy, Arithmetical set, Arithmetization of analysis, Atomic model (mathematical logic), Automated Mathematician, Automated theorem proving, Ax–Grothendieck theorem, Ax–Kochen theorem, Axiom of choice, Axiom of countable choice, Axiom of dependent choice, Axiom of determinacy, Axiom of projective determinacy, Axiom of real determinacy, Axiom schema, Axiomatic system, Łoś–Vaught test, Back-and-forth method, Barwise compactness theorem, Begriffsschrift, Beth number, Boolean algebra, Boolean algebra (structure), Boolean-valued model, Borel equivalence relation, Burali-Forti paradox, C-minimal theory, Calculus of constructions, Cantor's diagonal argument, Cantor's theorem, Cardinal number, Cardinality, Cartesian product, ..., Categorical logic, Church–Rosser theorem, Church–Turing thesis, Cirquent calculus, Class (set theory), Cointerpretability, Combinatory logic, Compactness theorem, Complement (set theory), Complete Boolean algebra, Complete theory, Complexity class, Computability logic, Computability theory, Computable function, Computable measure theory, Computable model theory, Computation, Computational complexity theory, Conservative extension, Consistency, Constructible universe, Constructive analysis, Constructive proof, Continuum (set theory), Continuum hypothesis, Cook–Levin theorem, Coq, Countable set, Criticism of non-standard analysis, Curry–Howard correspondence, Cut-elimination theorem, Decidability (logic), Decision problem, Deduction theorem, Definable real number, Definable set, Descriptive complexity theory, Descriptive set theory, Determinacy, Diagonal lemma, Dialectica space, Differentially closed field, Diophantine set, Direct proof, E theorem prover, Effective results in number theory, Ehrenfeucht–Fraïssé game, Element (mathematics), Elementary Calculus: An Infinitesimal Approach, Elementary class, Elementary equivalence, Emil Leon Post, Empty set, Entscheidungsproblem, Epsilon-induction, Erdős cardinal, Eurisko, Existence theorem, Existentially closed model, Exponential field, Exponential hierarchy, Extendible cardinal, Finite model theory, Finitism, First-order logic, Forcing (mathematics), Forking extension, Formal language, Formal system, Foundations of mathematics, Function (mathematics), Functional predicate, Fuzzy set, Gandalf (theorem prover), Gödel's completeness theorem, Gödel's incompleteness theorems, General frame, Gentzen's consistency proof, Georg Cantor's first set theory article, Gerhard Gentzen, Giuseppe Peano, Halting problem, Hartogs number, Haskell Curry, Herbrand interpretation, Herbrand structure, Higher-order logic, Hilbert's program, History of topos theory, HOL (proof assistant), Hrushovski construction, Huge cardinal, Hypercomputation, Hyperinteger, Hyperreal number, Imaginary element, Impredicativity, Inaccessible cardinal, Indescribable cardinal, Indiscernibles, Ineffable cardinal, Infinitary logic, Infinite descending chain, Infinity-Borel set, Institution (computer science), Institutional model theory, Interactive proof system, Interior algebra, Internal set theory, Interpretability, Interpretability logic, Interpretation (logic), Interpretation (model theory), Intersection (set theory), Intuitionistic logic, Intuitionistic type theory, Isabelle (proof assistant), Θ (set theory), Μ operator, Jacques Herbrand, Kleene's recursion theorem, Kripke semantics, Kripke–Platek set theory with urelements, Kurt Gödel, L(R), L. E. J. Brouwer, Lambda calculus, Lambda cube, Large cardinal, Löb's theorem, Löwenheim–Skolem theorem, Lightface analytic game, Limit ordinal, Lindenbaum–Tarski algebra, Lindström quantifier, Linear logic, List of complexity classes, List of computability and complexity topics, List of first-order theories, Logic for Computable Functions, Logical framework, Ludics, Mahlo cardinal, Many-sorted logic, Markov algorithm, Mathematical induction, Mathematical proof, Measurable cardinal, Metamathematics, Mizar system, Model checking, Model complete theory, Morley rank, Morley's categoricity theorem, Morse–Kelley set theory, Naive set theory, Natural proof, New Foundations, Non-standard analysis, Non-standard calculus, Non-standard model, Non-standard model of arithmetic, Nonfirstorderizability, NP-completeness, O-minimal theory, Oracle machine, Ordinal number, Original proof of Gödel's completeness theorem, Outline of logic, Overspill, P versus NP problem, Paradox (theorem prover), Peano axioms, Perfect set property, Polish space, Polynomial hierarchy, Positive set theory, Post correspondence problem, Post's theorem, Potential isomorphism, Power set, Pregeometry (model theory), Presburger arithmetic, Prewellordering, Prime model, Primitive recursive function, Principia Mathematica, Projective hierarchy, Proof by exhaustion, Proof net, Proof-theoretic semantics, Property of Baire, Provability logic, Prover9, Pseudoelementary class, QED manifesto, Quantifier elimination, Ramsey cardinal, Rank-into-rank, Rózsa Péter, Recursion, Recursive definition, Recursive language, Recursively enumerable language, Recursively enumerable set, Reduct, Reductio ad absurdum, Relevance logic, Remarkable cardinal, Resolution (logic), Reverse mathematics, Rice's theorem, Russell's paradox, Saharon Shelah, Sahlqvist formula, Saturated model, Schröder–Bernstein theorem, Second-order arithmetic, Second-order logic, Self-verifying theories, Sequent, Sequent calculus, Set (mathematics), Set theory, Set theory (music), Shelah cardinal, Signature (logic), Simple theorems in the algebra of sets, Simply typed lambda calculus, Singleton (mathematics), Skolem normal form, Skolem's paradox, Soundness, Space hierarchy theorem, Spectrum of a theory, Stability spectrum, Stable group, Stable theory, Standard part function, Stephen Cole Kleene, Strength (mathematical logic), Strict logic, Strong cardinal, Strongly minimal theory, Structural induction, Structural proof theory, Structural rule, Structure (mathematical logic), Subset, Substructural logic, Substructure, Subtle cardinal, Successor ordinal, Supercompact cardinal, Superstrong cardinal, Suslin's problem, System F, Systems of Logic Based on Ordinals, T-schema, Tame group, Tarski's exponential function problem, Tarski's undefinability theorem, Tautology (logic), Term algebra, Theory (mathematical logic), Time complexity, Time hierarchy theorem, Tolerant sequence, Trakhtenbrot's theorem, Transfer principle, Transfinite induction, Tree (descriptive set theory), Tree (set theory), Turing degree, Turing machine, Type (model theory), Type theory, Typed lambda calculus, Ultrafinitism, Ultraproduct, Undecidable problem, Unfoldable cardinal, Uniformization (set theory), Union (set theory), Universally measurable set, Universe (mathematics), Urelement, Vampire (theorem prover), Vaught conjecture, Von Neumann universe, Weak interpretability, Weakly compact cardinal, Weakly o-minimal structure, Well-founded relation, Well-order, Wilkie's theorem, Woodin cardinal, Word problem for groups, Zariski geometry, Zermelo set theory, Zermelo–Fraenkel set theory, Zero sharp, Zorn's lemma. Expand index (304 more) » « Shrink index
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 (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 is a substructural logic whose proof theory rejects the structural rule of contraction.
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 Mathison Turing (23 June 1912 – 7 June 1954) was an English computer scientist, mathematician, logician, cryptanalyst, philosopher, and theoretical biologist.
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 (January 14, 1901 – October 26, 1983), born Alfred Teitelbaum,School of Mathematics and Statistics, University of St Andrews,, School of Mathematics and Statistics, University of St Andrews.
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.
In mathematical logic, algebraic logic is the reasoning obtained by manipulating equations with free variables.
In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.
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.
Generically, an alternative set theory is an alternative mathematical approach to the concept of set.
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.
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.
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.
In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the 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.
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.
The arithmetization of analysis was a research program in the foundations of mathematics carried out in the second half of the 19th century.
In model theory, an atomic model is a model such that the complete type of every tuple is axiomatized by a single formula.
The Automated Mathematician (AM) is one of the earliest successful discovery systems.
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.
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.
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.
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.
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.
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.
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.
In mathematical logic, projective determinacy is the special case of the axiom of determinacy applying only to projective sets.
In mathematics, the axiom of real determinacy (abbreviated as ADR) is an axiom in set theory.
In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom.
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.
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.
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.
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 (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.
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).
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.
In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice.
In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory.
In mathematics, a Borel equivalence relation on a Polish space X is an equivalence relation on X that is a Borel subset of X × 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.
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.
In mathematical logic and computer science, the calculus of constructions (CoC) is a type theory created by Thierry Coquand.
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.
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.
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets.
In mathematics, the cardinality of a set is a measure of the "number of elements of the set".
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 is the branch of mathematics in which tools and concepts from category theory are applied to the study of mathematical logic.
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.
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 is a proof calculus which manipulates graph-style constructs termed cirquents, as opposed to the traditional tree-style objects such as formulas or sequents.
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.
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 is a notation to eliminate the need for quantified variables in mathematical logic.
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.
In set theory, the complement of a set refers to elements not in.
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound).
In mathematical logic, a theory is complete if, for every formula in the theory's language, that formula or its negation is demonstrable.
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
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, 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 functions are the basic objects of study in computability theory.
In mathematics, computable measure theory is the part of computable analysis that deals with effective versions of measure theory.
Computable model theory is a branch of model theory which deals with questions of computability as they apply to model-theoretical structures.
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 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.
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.
In classical deductive logic, a consistent theory is one that does not contain a contradiction.
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.
In mathematics, constructive analysis is mathematical analysis done according to some principles of constructive mathematics.
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.
In the mathematical field of set theory, the continuum means the real numbers, or the corresponding (infinite) cardinal number, \mathfrak.
In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets.
In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete.
In computer science, Coq is an interactive theorem prover.
In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.
Non-standard analysis and its offshoot, non-standard calculus, have been criticized by several authors, notably Errett Bishop, Paul Halmos, and Alain Connes.
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.
The cut-elimination theorem (or Gentzen's Hauptsatz) is the central result establishing the significance of the sequent calculus.
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).
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.
In mathematical logic, the deduction theorem is a metatheorem of propositional and first-order logic.
Informally, a definable real number is a real number that can be uniquely specified by its description.
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 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.
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 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.
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 spaces are a categorical way of constructing models of linear logic.
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.
In mathematics, a Diophantine equation is an equation of the form P(x1,..., xj, y1,..., yk).
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 is a high performance theorem prover for full first-order logic with equality.
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.
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.
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 is a textbook by H. Jerome Keisler.
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.
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 (February 11, 1897 – April 21, 1954) was an American mathematician and logician.
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.
In mathematics and computer science, the Entscheidungsproblem (German for "decision problem") is a challenge posed by David Hilbert in 1928.
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.
In mathematics, an Erdős cardinal, also called a partition cardinal is a certain kind of large cardinal number introduced by.
Eurisko (Gr., I discover) is a program written by Douglas Lenat in RLL-1, a representation language itself written in the Lisp programming language.
In mathematics, an existence theorem is a theorem with a statement beginning 'there exist(s)..', or more generally 'for all,,...
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).
In mathematics, an exponential field is a field that has an extra operation on its elements which extends the usual idea of exponentiation.
In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, which is an exponential time analogue of the polynomial hierarchy.
In mathematics, extendible cardinals are large cardinals introduced by, who was partly motivated by reflection principles.
Finite model theory (FMT) is a subarea of model theory (MT).
Finitism is a philosophy of mathematics that accepts the existence only of finite mathematical objects.
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.
In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results.
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.
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.
A formal system is the name of a logic system usually defined in the mathematical way.
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.
In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.
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.
In mathematics, fuzzy sets (aka uncertain sets) are somewhat like sets whose elements have degrees of membership.
Gandalf is a first-order automated theorem prover applied to several domain-specific tasks such as Semantic web.
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 are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic.
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 is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936.
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 Karl Erich Gentzen (November 24, 1909 – August 4, 1945) was a German mathematician and logician.
Giuseppe Peano (27 August 1858 – 20 April 1932) was an Italian mathematician and glottologist.
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.
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.
In mathematical logic, a Herbrand interpretation is an interpretation in which all constants and function symbols are assigned very simple meanings.
In first-order logic, a Herbrand structure S is a structure over a vocabulary σ, that is defined solely by the syntactical properties of σ.
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.
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.
This page gives some very general background to the mathematical idea of topos.
HOL (Higher Order Logic) denotes a family of interactive theorem proving systems using similar (higher-order) logics and implementation strategies.
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.
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, αM is the class of all sequences of length α whose elements are in M. Huge cardinals were introduced by.
Hypercomputation or super-Turing computation refers to models of computation that can provide outputs that are not Turing computable.
In non-standard analysis, a hyperinteger n is a hyperreal number that is equal to its own integer part.
The system of hyperreal numbers is a way of treating infinite and infinitesimal quantities.
In mathematical model theory, an imaginary element of a structure is roughly a definable equivalence class.
Something that is impredicative, in mathematics and logic, is a self-referencing definition.
In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic.
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.
In mathematical logic, indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula.
In the mathematics of transfinite numbers, an ineffable cardinal is a certain kind of large cardinal number, introduced by.
An infinitary logic is a logic that allows infinitely long statements and/or infinitely long proofs.
Given a set S with a partial order ≤, an infinite descending chain is an infinite, strictly decreasing sequence of elements x1 > x2 >...
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.
The notion of institution has been created by Joseph Goguen and Rod Burstall in the late 1970s.
This page is about the concept in mathematical logic.
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties.
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 (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.
In mathematical logic, interpretability is a relation between formal theories that expresses the possibility of interpreting or translating one into the other.
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.
An interpretation is an assignment of meaning to the symbols of a formal language.
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.
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, 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 (also known as constructive type theory, or Martin-Löf type theory) is a type theory and an alternative foundation of mathematics.
The Isabelle theorem prover is an interactive theorem prover, a Higher Order Logic (HOL) theorem prover.
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.
In computability theory, the μ operator, minimization operator, or unbounded search operator searches for the least natural number with a given property.
Jacques Herbrand (12 February 1908 – 27 July 1931) was a French mathematician.
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 (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.
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 Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.
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.
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 (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.
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.
In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers.
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.
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.
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)^.
In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal.
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).
In mathematical logic, a Lindström quantifier is a generalized polyadic quantifier.
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.
This is a list of complexity classes in computational complexity theory.
This is a list of computability and complexity topics, by Wikipedia page.
In mathematical logic, a first-order theory is given by a set of axioms in some language.
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.
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.
In proof theory, ludics is an analysis of the principles governing inference rules of mathematical logic.
In mathematics, a Mahlo cardinal is a certain kind of large cardinal number.
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.
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 is a mathematical proof technique.
In mathematics, a proof is an inferential argument for a mathematical statement.
In mathematics, a measurable cardinal is a certain kind of large cardinal number.
Metamathematics is the study of mathematics itself using mathematical methods.
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.
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.
In model theory, a first-order theory is called model complete if every embedding of models is an elementary embedding.
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.
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.
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).
Naïve set theory is any of several theories of sets used in the discussion of the foundations of mathematics.
In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one.
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.
The history of calculus is fraught with philosophical debates about the meaning and logical validity of fluxions or infinitesimal numbers.
In mathematics, non-standard calculus is the modern application of infinitesimals, in the sense of non-standard analysis, to differential and integral calculus.
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).
In mathematical logic, a non-standard model of arithmetic is a model of (first-order) Peano arithmetic that contains non-standard numbers.
In formal logic, nonfirstorderizability is the inability of an expression to be adequately captured in particular theories in first-order logic.
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
In mathematical logic, and more specifically in model theory, an infinite structure (M,<,...) which is totally ordered by Knight, Pillay and Steinhorn (1986), Pillay and Steinhorn (1988).
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.
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.
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.
Logic is the formal science of using reason and is considered a branch of both philosophy and mathematics.
In non-standard analysis, a branch of mathematics, overspill (referred to as overflow by Goldblatt (1998, p. 129)) is a widely used proof technique.
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.
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.
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).
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.
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.
In mathematical logic, positive set theory is the name for a class of alternative set theories in which the axiom of comprehension.
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.
In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.
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.
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, and in full combinatorial pregeometry, are essentially synonyms for "matroid".
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.
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).
In mathematics, and in particular model theory, a prime model is a model which is as simple as possible.
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).
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.
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, 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.
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 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.
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 is a modal logic, in which the box (or "necessity") operator is interpreted as 'it is provable that'.
Prover9 is an automated theorem prover for First-order and equational logic developed by William McCune.
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.
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 is a concept of simplification used in mathematical logic, model theory, and theoretical computer science.
In mathematics, a Ramsey cardinal is a certain kind of large cardinal number introduced by and named after Frank P. Ramsey.
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, born Politzer, (17 February 1905 – 16 February 1977) was a Hungarian mathematician and logician.
Recursion occurs when a thing is defined in terms of itself or of its type.
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).
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.
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.
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.
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, also called relevant logic, is a kind of non-classical logic requiring the antecedent and consequent of implications to be relevantly related.
In mathematics, a remarkable cardinal is a certain kind of large cardinal number.
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 is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics.
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 (שהרן שלח) is an Israeli mathematician.
In modal logic, Sahlqvist formulas are a certain kind of modal formula with remarkable properties.
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.
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.
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets.
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 are consistent first-order systems of arithmetic much weaker than Peano arithmetic that are capable of proving their own consistency.
In mathematical logic, a sequent is a very general kind of conditional assertion.
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.
In mathematics, a set is a collection of distinct objects, considered as an object in its own right.
Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects.
Musical set theory provides concepts for categorizing musical objects and describing their relationships.
In axiomatic set theory, Shelah cardinals are a kind of large cardinals.
In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language.
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.
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.
In mathematics, a singleton, also known as a unit set, is a set with exactly one element.
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.
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.
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.
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.
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.
In model theory, a stable group is a group that is stable in the sense of stability theory.
In model theory, a complete theory is called stable if it does not have too many types.
In non-standard analysis, the standard part function is a function from the limited (finite) hyperreal numbers to the real numbers.
Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician.
The relative strength of two systems of formal logic can be defined via model theory.
Strict logic is essentially synonymous with relevant logic, though it can be characterized proof-theoretically as.
In set theory, a strong cardinal is a type of large cardinal.
In model theory—a branch of mathematical logic—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 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.
In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof.
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.
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.
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.
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.
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.
In mathematics, subtle cardinals and ethereal cardinals are closely related kinds of large cardinal number.
In set theory, the successor of an ordinal number α is the smallest ordinal number greater than α.
In set theory, a supercompact cardinal is a type of large cardinal.
In mathematics, a cardinal number κ is called superstrong if and only if there exists an elementary embedding j: V → M from V into a transitive inner model M with critical point κ and V_ ⊆ M. Similarly, a cardinal κ is n-superstrong if and only if there exists an elementary embedding j: V → M from V into a transitive inner model M with critical point κ and V_ ⊆ 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.
In mathematics, Suslin's problem is a question about totally ordered sets posed by and published posthumously.
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 was the PhD dissertation of the mathematician Alan Turing.
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.
In mathematical group theory, a tame group is a certain kind of group defined in model theory.
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, stated and proved by Alfred Tarski in 1936, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics.
In logic, a tautology (from the Greek word ταυτολογία) is a formula or assertion that is true in every possible interpretation.
In universal algebra and mathematical logic, a term algebra is a freely generated algebraic structure over a given signature.
In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language.
In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.
In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines.
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.
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.
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 is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers.
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.
In set theory, a tree is a partially ordered set (T, \omega + 1.
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.
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.
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.
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.
A typed lambda calculus is a typed formalism that uses the lambda-symbol (\lambda) to denote anonymous function abstraction.
In the philosophy of mathematics, ultrafinitism, also known as ultraintuitionism, strict-finitism, actualism, and strong-finitism, is a form of finitism.
The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic.
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.
In mathematics, an unfoldable cardinal is a certain kind of large cardinal number.
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.
In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.
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).
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.
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 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.
The Vaught conjecture is a conjecture in the mathematical field of model theory originally proposed by Robert Lawson Vaught in 1961.
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.
In mathematical logic, weak interpretability is a notion of translation of logical theories, introduced together with interpretability by Alfred Tarski in 1953.
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.
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.
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.
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.
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.
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)(κ) ⊆ 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.
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.
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, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern 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.
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, 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.