|
This is a list of mathematical logic topics, by Wikipedia page.
For traditional syllogistic logic, see the list of topics in logic. See also the list of computability and complexity topics for more theory of algorithms. This is a list of topics in logic. ...
This is a list of computability and complexity topics, by Wikipedia page. ...
Flowcharts are often used to represent algorithms. ...
Clicking on related changes shows a list of most-recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes.
Working foundations In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). ...
Giuseppe Peano Giuseppe Peano (August 27, 1858 – April 20, 1932) was an Italian mathematician and philosopher best known for his contributions to set theory. ...
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers, or otherwise is true of all members of an infinite sequence. ...
Proofs that a subset of { 1, 2, 3, ... } is in fact the whole set { 1, 2, 3, ... } by mathematical induction usually have one of the following three forms. ...
Structural induction is a proof method that is used in mathematical logic (e. ...
A recursive definition is a one which defines a word in terms of itself, albeit in a useful way. ...
Naive set theory1 is distinguished from axiomatic set theory by the fact that the former regards sets as collections of objects, called the elements or members of the set, whereas the latter regards sets only as that which satisfies certain axioms. ...
In mathematics, an element (also called a member) is an object contained in a set (or more generally a class). ...
Definition In set theory a ur-element is something which is not a set, but may itself be an element of a set. ...
In mathematics, a singleton is a set with exactly one element. ...
Elementary mathematics courses sometimes leave students under an erroneous impression that the subject matter of set theory is the algebra of union, intersection, and complementation of sets. ...
The algebra of sets develops and describes the basic properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality (mathematics) and set inclusion. ...
In mathematics, a set S, the power set of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ...
In mathematics, the empty set is the set with no elements. ...
In set theory, a set is called non-empty (or nonempty) if it contains at least one element, and is therefore not the empty set. ...
In the case where the domain of the function is the empty set {}, there is only one function with that domain (given any codomain), the empty function, and any formula can be used to define the empty function, since the formula wont apply to anything and will therefore never...
In mathematics, and particularly in applications to set theory and the foundations of mathematics, a universe or universal class (or if a set, universal set) is, roughly speaking, a class that is large enough to contain (in some sense) all of the sets that one may wish to use. ...
In mathematics, axiomatization is the process of defining the basic axiomatic systems from which mathematical theories can be derived. ...
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 symbolic logic, it is sometimes inconvenient or impossible to express an axiomatic system in a finite number of axioms. ...
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 mathematics, a proof is a demonstration that, given certain axioms, some statement of interest is necessarily true. ...
In mathematics, a direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually existing lemmas and theorems, without making any further assumptions. ...
Reductio ad absurdum (Latin for reduction to the absurd, traceable back to the Greek ἡ εις το αδυνατον απαγωγη, reduction to the impossible, often used by Aristotle) is a type of logical argument where we assume a claim for the sake of argument, arrive at an absurd result, and then conclude the original assumption must...
Proof by exhaustion, also known as the brute force method or case analysis, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases, and each case is proved separately. ...
In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object. ...
In mathematics, a nonconstructive proof, is a mathematical proof that purports to demonstrate the existence of something, but which does not say how to construct it. ...
In logic, a tautology is a statement which is true by its own definition. ...
Consistency has three technical meanings: In mathematics and logic, as well as in theoretical physics, it refers to the proposition that a formal theory or a physical theory contains no contradictions. ...
The arithmetization of analysis was a research program in the foundations of mathematics carried out in the second half of the 19th century. ...
The term foundations of mathematics is sometimes used for certain fields of mathematics itself, namely for mathematical logic, axiomatic set theory, proof theory, model theory, and recursion theory. ...
In the mathematics of the nineteenth century, the interest in the foundations of mathematics led to what could be called a professional view of the arithmetization of analysis; and a further question about generating arithmetic from more primitive concepts. ...
In mathematics, logic and computer science, a formal language is a set of finite-length words (i. ...
For Isaac Newtons 1687 book containing basic laws of physics, see Philosophiae Naturalis Principia Mathematica The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Bertrand Russell and Alfred North Whitehead and published in 1910-1913. ...
Hilberts Program was to formalize all existing theories to finite real complete set of axioms, and provide a proof that these axioms were consistent. ...
In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the models which underlie mathematical systems. ...
In mathematical logic, especially set theory and model theory, Cantors back-and-forth method, named after Georg Cantor, is a method for showing isomorphism between countably infinite structures satisfying specified conditions. ...
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, a monadic logic is one that employs only unary relations. ...
First-order predicate calculus or first-order logic (FOL) permits the formulation of quantified statements such as there exists an x such that. ...
In predicate calculus, a formula is in prenex normal form if it can be written as a string of quantifiers, followed by a quantifier-free part, referred to as the matrix. ...
A formula of first-order logic is in Skolem normal form if its prenex normal form has only universal quantifiers. ...
In mathematical logic, the Lindenbaum-Tarski algebra A of a logical theory T consists of the equivalence classes of sentences p of the theory, under the equivalence relation ~ defined by p ~ q when p and q are logically equivalent in T. That is, in T q can be deduced from...
The T-schema is the inductive definition that lies at the heart of any realisation of Alfred Tarskis semantic theory of truth, expressing the commutation of truth over logical operators. ...
A maximal consistent set is a set of formulae belonging to some formal language that satisfy certain constraints: The set is consistent, that is, no formula is both provable and refutable. ...
The compactness theorem is a basic fact in symbolic logic and model theory and asserts that a set (possibly infinite) of first-order sentences is satisfiable, i. ...
In mathematical logic, the classic Löwenheim-Skolem theorem states that any infinite model M has a countably infinite submodel N that satisfies exactly the same set of first-order sentences that M satisfies. ...
Soundness theorems are among the most fundamental results in mathematical logic. ...
Gödels completeness theorem is a fundamental theorem in mathematical logic proved by Kurt Gödel in 1929. ...
The proof of Gödels 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 outdated and terminology that is...
In mathematical logic, the deduction theorem states that if a conclusion can be inferred (by means of some inference rule) from a premise, then it is possible to assert that the premise implies the conclusion. ...
In mathematical logic, given models and in the same language , a function is called an elementary embedding if is an elementary substructure of . ...
In model theory, given two structures and in the same language , we say that is an elementary substructure of (notated sometimes ) if 1. ...
In mathematical logic, Löbs theorem states that in a theory with Peano arithmetic, for any formula P, if it is provable that if P is provable then P, then P is provable. ...
In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proved by Kurt Gödel in 1931. ...
An ultraproduct is a mathematical construction, which is used in abstract algebra to construct new fields from given ones, and in model theory, a branch of mathematical logic. ...
In mathematical logic, and in particular model theory, a model is -saturated if and only if it realizes all elements , for with . ...
In the most restricted sense, non-standard analysis is that branch of mathematics that formulates analysis using a rigorous notion of infinitesimal, where an element of an ordered field F is infinitesimal if and only if its absolute value is smaller than any element of F of the form 1...
In mathematics, particularly in non-standard analysis and mathematical logic, hyperreal numbers or nonstandard reals (usually denoted as *R) denote an ordered field which is a proper extension of the ordered field of real numbers R and which satisfies the transfer principle. ...
In mathematics non-standard calculus is the application of non-standard analysis techniques to differential and integral calculus. ...
In mathematics particularly in non-standard analysis, the transfer principle is a rule which transforms assertions about standard sets, mappings etc. ...
In mathematics, particularly in non-standard analysis, overspill is a widely used proof technique. ...
In mathematical logic, a tolerant sequence is a sequence ,..., of formal theories such that there are consistent extensions ,..., of these theories with each interpretable in . ...
In mathematical logic, a cotolerant sequence is a sequence of formal theories such that there are consistent extensions of these theories with each is cointerpretable in . ...
The concept of interpretability is one in mathematical logic. ...
Assume T and S are formal theories. ...
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...
In mathematical logic, second-order logic is an extension of either propositional logic or first-order logic which contains variables in predicate positions (rather than only in term positions, as in first-order logic), and quantifiers binding them. ...
In group theory, the Whitehead problem is the following question: Is every abelian group A with Ext1(A, Z) = 0 a free abelian group? The condition Ext1(A, Z) = 0 can be equivalently formulated as follows: whenever B is an abelian group and f : B → A is a surjective group...
Th see Thompson group (finite). ...
Kurt Gödel Kurt Gödel [kurt gøËdl], (April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher of mathematics. ...
Alfred Tarski, original name Alfred Teitelbaum (January 14, 1901 in Warsaw–October 26, 1983 in Berkeley, USA) was a Polish logician considered to be one of the greatest logicians of all time in a manner after Aristotle, Gottlob Frege, and Kurt Gödel. ...
Saharon Shelah (שהרן שלח, born July 3, 1945 in Jerusalem) is an Israeli mathematician. ...
Set theory is the mathematical theory of sets, which represent collections of abstract objects. ...
Set theory is a branch of mathematics created principally by the German mathematician Georg Cantor at the end of the 19th century. ...
In mathematics, a well-founded relation is an order relation R on a set X where every non-empty subset of X has an R-minimal element; that is, where for every non-empty subset S of X, there is an element m of S such that for every element...
Transfinite numbers, also known as infinite numbers, are numbers that are not finite. ...
Hilberts paradox of the Grand Hotel - Wikipedia /**/ @import /skins/monobook/IE50Fixes. ...
Commonly, ordinal numbers, or ordinals for short, are numbers used to denote the position in an ordered sequence: first, second, third, fourth, etc. ...
When defining the ordinal numbers, an absolutely fundamental operation that we can perform on them is a successor operation S to get the next higher one. ...
In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that naïvely constructing the set of all ordinal numbers leads to a contradiction and therefore shows an antinomy in a system that allows its construction. ...
A limit ordinal is an ordinal number which is not a successor ordinal. ...
Two sets A and B are said to be equinumerous if they have the same cardinality, i. ...
In linguistics, cardinal numbers is the name given to number words that are used for quantity (one, two, three), as opposed to ordinal numbers, words that are used for order (first, second, third). ...
In the theory of cardinal numbers, we can define a successor operation similar to that in the ordinal numbers. ...
In mathematics the term countable set is used to describe the size of a set, e. ...
In mathematics, an uncountable set is a set which is not countable. ...
Contrary to what most mathematicians believe, Georg Cantors first proof that the set of all real numbers is uncountable was not his famous diagonal argument, and did not mention decimal expansions or any other numeral system. ...
Cantors diagonal argument is a proof devised by Georg Cantor to demonstrate that the real numbers are not countably infinite. ...
Note: in order to fully understand this article you may want to refer to the set theory portion of the table of mathematical symbols. ...
There is also a proposition in graph theory called Königs lemma. ...
In the branch of mathematics known as set theory, aleph usually refers to a series of numbers used to represent the cardinality (or size) of infinite sets. ...
In mathematics, the Hebrew letter (aleph) with various subscripts represents various infinite cardinal numbers (see aleph number). ...
In axiomatic set theory, the gimel function is the following function mapping cardinal numbers to cardinal numbers: where cf denotes the cofinality function; the gimel function is used for studying the continuum function and the cardinal exponentiation function. ...
In set theory and other branches of mathematics, ב2 (pronounced beth two), or 2c (pronounced two to the power of c), is a certain cardinal number. ...
An infinite cardinal number κ is called regular if cf(κ) = κ, where cf is the cofinality operation. ...
In mathematics, limit cardinals are a type of cardinal number. ...
In mathematical set theory, 0# (zero sharp, also: 0#) is defined to be a particular real number satisfying certain conditions. ...
In set theory, the concept of cardinality is significantly developable without recourse to actually defining cardinal numbers as objects in theory itself (this is in fact a viewpoint taken by Frege; Frege cardinals are basically equivalence classes on the entire universe of sets which are equinumerous). ...
The von Neumann cardinal assignment is a cardinal assignment which uses ordinal numbers. ...
In set theory, the Cantor-Bernstein-Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions f : A → B and g : B → A between the sets A and B, then there exists a bijective function h : A → B. In terms of the...
The Zermelo-Fraenkel axioms of set theory (ZF) are the standard axioms of axiomatic set theory on which, together with the axiom of choice, all of ordinary mathematics is based in modern formulations. ...
The axiom of regularity (also known as the axiom of foundation) is one of the axioms of Zermelo-Fraenkel set theory. ...
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of extensionality, or axiom of extension, is one of the axioms of Zermelo-Fraenkel set theory. ...
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of pairing is one of the axioms of Zermelo_Fraenkel set theory. ...
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of empty set is one of the axioms of Zermelo_Fraenkel set theory. ...
In mathematics, the axiom of power set is one of the Zermelo-Fraenkel axioms of axiomatic set theory. ...
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of union is one of the axioms of Zermelo_Fraenkel set theory, stating that, for any two sets, there is a set that contains exactly the elements of both. ...
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom of infinity is one of the axioms of Zermelo-Fraenkel set theory. ...
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of specification, or axiom schema of separation, or axiom schema of restricted comprehension, is a schema of axioms in Zermelo-Fraenkel set theory. ...
In axiomatic set theory and the branches of logic, mathematics, and computer science that use it, the axiom schema of replacement is a schema of axioms in Zermelo-Fraenkel set theory. ...
In mathematics, the axiom of choice is an axiom of set theory. ...
Zorns lemma, also known as the Kuratowski-Zorn lemma, is a theorem of set theory that states: Every partially ordered set in which every chain (i. ...
The well-ordering theorem (not to be confused with the well-ordering axiom) states that every set can be well-ordered. ...
Sometimes the phrase well-ordering principle (or the axiom of choice) is taken to be synonymous with well-ordering theorem. On other occasions the phrase is taken to mean the proposition that the set of natural numbers {1, 2, 3, ....} is well-ordered, i. ...
Transfinite induction is the proof technique of mathematical induction when applied to (large) well-ordered sets, for instance to sets of ordinals or cardinals, or even to the class of all ordinals. ...
The Hausdorff maximality theorem, formulated and proved by Felix Hausdorff in 1914, is an alternate formulation of Zorns lemma and therefore also equivalent to the axiom of choice. ...
In mathematics, the axiom of dependent choice is a weak form of the axiom of choice which is still sufficient to develop most of real analysis. ...
The axiom of countable choice or axiom of denumerable choice is an axiom of set theory similar to the axiom of choice. ...
In mathematics, a number of prime ideal theorems for guaranteeing the existence of certain subsets of an abstract algebra can be stated. ...
In mathematics, the Ultrafilter Lemma states that every filter is a subset of some ultrafilter, i. ...
The following is a list of mathematical statements that are undecidable in ZFC (the Zermelo-Fraenkel axioms plus the axiom of choice), assuming that ZFC is consistent. ...
Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. ...
In foundations of mathematics, Von Neumann-Bernays-Gödel set theory (NBG) is an axiom system for set theory designed to yield the same results as Zermelo-Fraenkel set theory, together with the axiom of choice (ZFC), but with only a finite number of axioms, that is without axiom schemas. ...
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 mathematics, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. ...
In axiomatic set theory, forcing is a technique, invented by Paul Cohen, for proving consistency and independence results with respect to the Zermelo-Fraenkel axioms. ...
Freilings axiom of symmetry (AX) is a set-theoretic axiom proposed by Chris Freiling. ...
In mathematical logic, Goodsteins theorem is a statement about the natural numbers that is undecidable in Peano arithmetic but can be proven to be true using the stronger axiom system of set theory, in particular using the axiom of infinity. ...
Internal set theory (IST) is a mathematical theory of sets developed by Edward Nelson which provides an axiomatic basis for a portion of the non-standard analysis introduced by Abraham Robinson. ...
In mathematics, the constructible universe (or Gödels constructible universe), denoted , is a particular class of sets which can be described entirely in terms of simpler sets. ...
The axiom of constructibility is a possible axiom for set theory in mathematics. ...
In axiomatic set theory and related branches of mathematics, the Von Neumann universe, or Von Neumann hierarchy of sets is the class of all sets, divided into a transfinite hierarchy of individual sets. ...
In mathematics, hereditarily finite sets are defined recursively as finite sets containing hereditarily finite sets (with the empty set as a base case). ...
In axiomatic set theory, a function f : Ord → Ord is called normal (or a normal function) iff it is continuous (with respect to the order topology) and strictly mononotically increasing. ...
The fixed-point lemma for normal functions is a basic result in axiomatic set theory; it states that any normal function has arbitrarily large fixed points and can often be used to construct ordinal numbers with interesting properties. ...
In mathematics, under various anti-large cardinal assumptions, one can prove the existence of the canonical inner model, called the Core Model, that is, in a sense, maximal and approximates the structure of V. A covering lemma asserts that under the particular anti-large cardinal assumption, the Core Model exists...
In mathematical logic, stratification is any consistent assignment of numbers to predicate symbols guaranteeing that a unique formal interpretation of a logical theory exists. ...
Suslins problem in mathematics is a question about orders posed by M. Suslin in the early 1920s. ...
In mathematics, and particularly in axiomatic set theory, ♣S (clubsuit) is a combinatorial principle that is a weaker version of ◊S and that was introduced in 1975 by A. Ostaszewski. ...
In mathematics, and particularly in axiomatic set theory, ◊S (diamondsuit or diamond) is a certain family of combinatorial principles. ...
Ernst Friedrich Ferdinand Zermelo (July 27, 1871 – May 21, 1953) was a German mathematician and philosopher. ...
Paul Joseph Cohen (born April 2, 1934) is an American mathematician. ...
In mathematical logic, the New Foundations (NF) of W. V. O. Quine is a candidate set theory, obtained from a streamlined version of the theory of types of Bertrand Russell. ...
In mathematical logic, especially set theory and model theory, Cantors back-and-forth method, named after Georg Cantor, is a method for showing isomorphism between countably infinite structures satisfying specified conditions. ...
In mathematics, descriptive set theory is the study of certain classes of well-behaved sets of real numbers, e. ...
In mathematical logic and descriptive set theory, the analytical hierarchy is a second-order analogue of the arithmetical hierarchy. ...
In mathematics, a cardinal is called a large cardinal if it belongs to a class of cardinals, the existence of which provably cannot be proved within the standard axiomatic set theory ZFC, if one assumes ZFC itself is consistent. ...
In mathematics, an almost Ramsey cardinal is a certain kind of large cardinal number. ...
In mathematics, an Erdős cardinal (named after Paul Erdős) is a certain kind of large cardinal number. ...
In mathematics, a cardinal number κ is η-extendible iff for some λ there is a nontrivial elementary embedding of Vκ+η into Vλ. ...
In mathematics, a cardinal number κ is called huge iff there exists an elementary embedding j : V → M from V into a transitive inner model M with critical point κ and j(κ)M ⊆ M. Categories: Math stubs ...
In axiomatic set theory, hyper-Woodin cardinals are a kind of large cardinals. ...
In mathematics, a cardinal number k > (aleph-null) is called weakly inaccessible, or just inaccessible, if the following two conditions hold. ...
In mathematics, an ineffable cardinal is a certain kind of large cardinal number. ...
In mathematics, a Mahlo cardinal is a certain kind of large cardinal number. ...
Bold textcopper mellon pressure washer. ...
In mathematics, a cardinal number κ is called n-huge iff there exists an elementary embedding j : V → M from V into a transitive inner model M that has critical point κ and is closed under sequences of length jn(κ). ...
In mathematics, a Mahlo cardinal is a certain kind of large cardinal number. ...
In mathematics, a Ramsey cardinal is a certain kind of large cardinal number. ...
In set theory, a rank-into-rank is a large cardinal λ satisfying one of the following four axioms (commonly known as rank-into-rank embeddings, given in order of increasing consistency strength): There is a nontrivial elementary embedding of Vλ into itself. ...
In mathematics, a remarkable cardinal is a certain kind of large cardinal number. ...
In axiomatic set theory, Shelah cardinals are a kind of large cardinals. ...
In mathematics, a strong cardinal is a cardinal number κ such that for all ordinal numbers λ there exists an elementary embedding j : V → M from V into a transitive inner model M with critical point κ and Vλ ⊆ M. A λ-strong cardinal is a cardinal number κ such...
In mathematics, a strongly inaccessible cardinal is an uncountable cardinal number κ that is regular and a strong limit cardinal. ...
In mathematics, a subtle cardinal is a certain kind of large cardinal number. ...
In mathematics, a cardinal number κ is called supercompact iff for all ordinal numbers α there exists an elementary embedding j : V → M from V into a transitive inner model M with critical point κ and αM ⊆ M. Categories: Math stubs ...
In mathematics, a cardinal number κ is called superstrong iff there exists an elementary embedding j : V → M from V into a transitive inner model M with critical point κ and Vj(κ) ⊆ M. Categories: Math stubs ...
In mathematics, a totally indescribable cardinal is a certain kind of large cardinal number. ...
In mathematics, a weakly compact cardinal is a certain kind of cardinal number; weakly compact cardinals are large cardinals, meaning that their existence can neither be proven nor disproven from the standard axioms of set theory. ...
In axiomatic set theory, weakly hyper-Woodin cardinals are a kind of large cardinals. ...
In mathematics, a cardinal number k > (aleph-null) is called weakly inaccessible, or just inaccessible, if the following two conditions hold. ...
In mathematical logic, a Woodin cardinal is a cardinal number κ such that for all f : κ → κ there exists α < κ with f[α] ⊆ α and an elementary embedding j : V → M from V into a transitive inner model M with critical point α and Vj(f)(α) ⊆ M...
In mathematics, an unfoldable cardinal is a certain kind of large cardinal number. ...
Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. ...
The Entscheidungsproblem (German: decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. ...
In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ...
A logical system is decidable iff there exists an algorithm such that for every well-formed formula in that system there exists a maximum finite number N of steps such that the algorithm is capable of deciding in less than or equal to N algorithmic steps whether the formula is...
In computability theory the Church-Turing thesis, Churchs thesis, Churchs conjecture or Turings thesis, named after Alonzo Church and Alan Turing, is a hypothesis about the nature of mechanical calculation devices, such as electronic computers. ...
In mathematical logic and computer science, the recursive functions are a class of functions from natural numbers to natural numbers which are computable in some intuitive sense. ...
Flowcharts are often used to represent algorithms. ...
In mathematics and computer science, recursion is a particular way of specifying (or constructing) a class of objects (or an object from a certain class) with the help of a reference to other objects of the class: a recursive definition defines objects in terms of the already defined objects of...
In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. ...
In computability theory, the μ-operator is the operator which when applied to a given computable function f is a computable function returning the first value for which f is zero. ...
In the theory of computation, the Ackermann function or Ackermann-Peter function is a simple example of a recursive function that is not primitive recursive. ...
Artists conception of a universal Turing machine. ...
In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of an algorithm and its initial input, determine whether the algorithm, when executed on this input, ever halts (completes). ...
Computability theory is that part of the theory of computation dealing with which problems are solvable by algorithms (equivalently, by Turing machines), with various restrictions and extensions. ...
Computation can be defined as finding a solution to a problem from given inputs by means of an algorithm. ...
In mathematical logic, for any formal language with a set of symbols (constants and functional symbols), the Herbrand universe recursively defines the set of all terms that can be composed by applying functional composition from the basic symbols. ...
A Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. ...
The lambda calculus is a formal system designed to investigate function definition, function application, and recursion. ...
In mathematical logic, the Church-Rosser theorem states that, in the lambda calculus, a term has at most one normal form. ...
The calculus of constructions (CoC) is a higher-order typed lambda calculus where types are first-class values. ...
Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. ...
The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post. ...
Kleenes recursion theorem is a result in computability theory first proved by Stephen Kleene; it allows to construct programs, Turing machines and recursive functions that refer back to their own description. ...
In computability theory, often less suggestively called recursion theory, a countable set S is called recursively enumerable, computably enumerable, semi-decidable or provable if There is an algorithm that, when given an input — typically an integer or a tuple of integers or a sequence of characters — eventually halts if it...
A recursively enumerable language in mathematics, logic and computer science, is a type of formal language which is also called recursively enumerable, partially decidable or Turing-recognizable. ...
In computer science a formal language is called recursive or decidable if there exists an algorithm to decide for any given string w over the alphabet of the language, if w belongs to the language or not. ...
In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ...
Rices theorem (also known as The Rice-Myhill-Shapiro theorem) is an important result in the theory of recursive functions. ...
In computability theory Posts theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees. ...
In computability theory, the Turing degree of a subset of the natural numbers, , is the equivalence class of all subsets of equivalent to under Turing reducibility. ...
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 mathematics, a set S of j-tuples of integers is Diophantine precisely if there is some polynomial with integer coefficients f(n1, ..., nj, x1, ..., xk) such that a tuple (n1, ..., nj) of integers is in S if and only if there exist some integers x1, ..., xk with f(n1...
Matiyasevichs theorem, proven in 1970 by Yuri Matiyasevich, implies that Hilberts tenth problem is unsolvable. ...
In abstract algebra, the word problem for groups is the problem of deciding whether two given words of a presentation of a group represent the same element. ...
In mathematical logic, the arithmetical hierarchy (also known as the arithmetic hierarchy) classifies the set of all formulas (or functions) according to their degree of solvability. ...
Presburger arithmetic is the first-order theory of the natural numbers with addition. ...
Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ...
In complexity theory, exponential time is the computation time of a problem where the time, m(n), is bounded by an exponential function of the problem size, n. ...
In computational complexity theory, a complexity class is a set of problems of related complexity. ...
Diagram of complexity classes provided that P ≠NP. If P = NP, then all three classes are equal. ...
In computational complexity theory, Cooks theorem, proved by Stephen Cook in his 1971 paper The Complexity of Theorem Proving Procedures, states that the Boolean satisfiability problem is NP-complete. ...
This is a list of complexity classes in computational complexity theory. ...
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. ...
In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, starting with EXP: and continuing with and so on. ...
In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
In computational complexity theory, the time hierarchy theorems are important statements that ensure the existence of certain hard problems which cannot be solved in a given amount of time. ...
In computational complexity theory, the space hierarchy theorems are the exact analogues of the time hierarchy theorems for space. ...
In computational complexity theory, natural proof is a notion introduced by Alexander Razborov and Steven Rudich, to classify the set of proofs that will fail to prove separations between complexity classes. ...
Hypercomputation refers to methods for the computation of non-computable functions. ...
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ...
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who was responsible for some of the foundations of theoretical computer science. ...
Emil Leon Post (February 11, 1897 - April 21, 1954) was a Polish-American mathematician and logician. ...
Alan Turing is often considered the father of modern computer science. ...
Jacques Herbrand (February 12, 1908 - July 27, 1932) was a French mathematician who was born in Paris, France and died in La Bérarde, Isère, France. ...
Haskell Brooks Curry (September 12, 1900 - September 1, 1982) was an American mathematician and logician. ...
Stephen Cole Kleene (January 5, 1909 - January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ...
Proof theory, studied as a branch of mathematical logic, represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. ...
Metamathematics is mathematics used to study mathematics. ...
The Cut-elimination theorem is the central result establishing the significance of the sequent calculus. ...
In mathematical logic, Tarskis Indefinability Theorem is a theorem due to Alfred Tarski concerning the foundations of mathematics. ...
In mathematical logic, Gödels diagonal lemma is a precise way of constructing self-referential statements. ...
Provability logic, or the logic of provability, is a modal logic where the necessity operator is interpreted as provability in a reasonably rich formal theory such as Peano arithmetic. ...
Interpretability logics comprise a family of modal logics that extend provability logic to describe interpretability and/or various related metamathematical properties and relations such as weak interpretability, Π1-conservativity, cointerpretability, tolerance, cotolerance, arithmetic complexities. ...
In proof theory, a sequent is a formalized statement of provability that is frequently used when specifying calculi for deduction. ...
In proof theory and mathematical logic, the sequent calculus is a widely known deduction system for first-order logic (and propositional logic as a special case of it). ...
In structural proof theory, an analytical proof is a proof whose structure is simple in a special way. ...
In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof. ...
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, in particular in connection with proof theory, a number of substructural logics have been introduced, as systems of propositional calculus that are weaker than the conventional one. ...
In proof theory, a structural rule is an inference rule that does not refer to any logical connective, but instead operates on the judgements or sequents directly. ...
A structural rule or structural principle of mathematical logic that states that the hypotheses of any derived fact may be freely extended with additional assumptions. ...
The word contraction when used alone, has several possible meanings in the English language. ...
In mathematical logic, linear logic is a type of substructural logic that denies the structural rules of weakening and contraction. ...
A variant of linear logic that allows a single, or no more than one, conclusion. ...
In proof theory, proof nets are a geometrical method of representing proofs that eliminates irrelevant syntactical features of regular proof calculi such as the natural deduction calculus and the sequent calculus; by this means the formal properties of proof identity correspond more closely to the intuitively desirable properties. ...
A substructural logic that denies the structural rule of contraction. ...
Essentially synonymous with relevant logic, though it can be characterized proof-theoretically as ordinary logic without weakening, or linear logic with contraction See also Relevant logic Linear logic Substructural logic Proof theory ...
Relevance logic, also called relevant logic, is any of a family of non-classical substructural logics that impose certain restrictions on implication. ...
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. ...
In proof theory, ludics is an analysis of the principles governing inference rules of mathematical logic. ...
System F is a typed lambda calculus. ...
Gerhard Gentzen (November 24, 1909 – August 4, 1945) was a German mathematician and logician. ...
Reverse mathematics is the branch of mathematics concerned with what are the minimal axioms needed to prove the particular theorem. ...
In formal logic, nonfirstorderizability is the inability of an expression to be adequately captured in standard first-order logic. ...
In the philosophy of mathematics, constructivism asserts that it is necessary to find (or construct) a mathematical object to prove that it exists. ...
In mathematics, a nonconstructive proof, is a mathematical proof that purports to demonstrate the existence of something, but which does not say how to construct it. ...
In mathematics, an existence theorem is a theorem with a statement beginning there exist(s) .., or more generally for all x, y, ... there exist(s) .... That is, in more formal terms of symbolic logic, it is a theorem with a statement involving the existential quantifier. ...
Intuitionistic logic, or constructivist logic, is the logic used in mathematical intuitionism and other forms of mathematical constructivism. ...
At the broadest level, type theory is the branch of mathematics and logic that concerns itself with classifying entities into sets called types. ...
This page gives some very general background to the mathematical idea of topos. ...
In type theory, the LF logical framework was one of the first logical frameworks, that is a formal calculus for the description of formal systems and reasoning about them. ...
In mathematical logic and type theory, the λ-cube is a framework for exploring the axes of refinement in Coquands Calculus of Constructions, starting from the simply typed lambda calculus as the vertex of a (3-D) cube placed at the origin, and the calculus of constructions (= higher order...
In mathematics, constructive analysis is mathematical analysis done according to the principles of constructivist mathematics. ...
Computability logic is a formal theory of computability, introduced by Giorgi Japaridze in 2003. ...
A version of measure theory which deals with computable numbers, as opposed to real numbers which are used in standard measure theory. ...
In the philosophy of mathematics, finitism is an extreme form of constructivism, according to which a mathematical object does not exist unless it can be constructed from natural numbers in a finite number of steps. ...
In the philosophy of mathematics, ultrafinitism, or ultraintuitionism, is an extreme version of finitism. ...
Luitzen Egbertus Jan Brouwer (February 27, 1881 - December 2, 1966), usually cited as L. E. J. Brouwer, was a Dutch mathematician, a graduate of the University of Amsterdam, who worked in topology, set theory, measure theory and complex analysis. ...
Modal logic, or (less commonly) intensional logic is the branch of logic that deals with sentences that are qualified by modalities such as can, could, might, may, must, possibly, and necessarily, and others. ...
Kripke semantics (also known as possible world semantics, relational semantics, or frame semantics) is a formal semantics for modal logic systems, created in late 1950s and early 1960s by Saul Kripke. ...
In modal logic, Sahlqvist formulas are a certain kind of modal formula with remarkable properties. ...
In abstract algebra, an interior algebra is an algebraic structure of the signature <A, ·, +, , 0, 1, I> where <A, ·, +, , 0, 1> is a Boolean algebra and I is a unary operator, the interior operator, satisfying the identities: xI ≤ x xII = xI (xy)I = xIyI 1I = 1 xI is called the...
Automated theorem proving (currently the most important subfield of automated reasoning) is the proving of mathematical theorems by a computer program. ...
In mathematical logic and automated theorem proving, first-order resolution is a theorem-proving technique. ...
Automated theorem proving (currently the most important subfield of automated reasoning) is the proving of mathematical theorems by a computer program. ...
ACL2 is a software system consisting of a programming language, an extensible theory in a first-order logic, and a mechanical theorem prover. ...
E is a modern, high performance theorem prover for first-order logic with equality. ...
The Gandalf theorem prover is the first-order theorem prover applied to several domain-specific tasks such as Semantic web. ...
The various HOL (which stands for Higher Order Logic) systems are a family of interactive theorem proving systems sharing similar logics and implementation strategies. ...
The Isabelle theorem prover an interactive theorem proving framework, a successor of the HOL theorem prover. ...
An interactive theorem prover developed at the universities of Edinburgh and Stanford by Robin Milner and others. ...
Paradox is an automated theorem proving system. ...
Vampire is an automatic theorem prover for first-order classical logic developed in the Computer Science Department of the University of Manchester. ...
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. ...
The Mizar system consists of a language for writing strictly formalized mathematical definitions and proofs, a computer program which is able to check proofs written in this language, and a library of definitions and proved theorems which can be referred to and used in new articles. ...
The QED project was a proposal for a computer-based encyclopedia and database of all mathematical knowledge, strictly formalized and with all proofs having been checked automatically. ...
In automated theorem proving, Coq is a proof assistant which handles mathematical assertions, checks mechanically proofs of these assertions, helps to find formal proofs, and extracts a certified program from the constructive proof of its formal specification. ...
A discovery system is an artificial intelligence system which attempts to discover new scientific concepts or laws. ...
Autoclass is a Bayesian clustering tool developed at the NASA Ames Research Center by the Bayes group. ...
The Automated Mathematician is one of the earliest successful discovery systems developed. ...
Eurisko (Gr. ...
Historical |
Feeds |
Contact