534 articles
2-satisfiability
2-satisfiability (2-SAT) is the problem of deciding whether a Boolean formula whose clauses each contain exactly two literals has a satisfying truth assignment, solvable in linear time.
3-satisfiability
3-satisfiability, or 3-SAT, is the NP-complete problem of deciding whether a Boolean formula whose clauses each contain three literals has a truth assignment satisfying every clause.
Abductive reasoning
Abductive reasoning, or inference to the best explanation, is a form of inference that reasons from an observation to the hypothesis that best explains it.
Abraham Fraenkel (אברהם הלוי פרנקל)
Abraham Fraenkel, born Adolf Abraham Halevi Fraenkel (1891–1965), was a German-born Israeli mathematician whose axiom of replacement produced the standard Zermelo–Fraenkel axioms of set theory.
Absoluteness (mathematical logic)
In mathematical logic, absoluteness is the property of a formula whose truth value stays the same when evaluated in different models or inner structures, such as forcing extensions.
Ackermann function
The Ackermann function, also called the Ackermann-Peter function, is a computable function that grows faster than every primitive recursive function, defined by Wilhelm Ackermann in 1928.
Actual and potential infinity
Actual and potential infinity are two conceptions of the infinite: an unending process that stays finite, versus a completed totality, a distinction Aristotle drew and Cantor made mathematical.
Adaptive logic
An adaptive logic is a formal logical system that adapts its consequence relation to a premise set, treating formulas as abnormal unless the premises force otherwise; it was created by Diderik Batens.
Adaptive neuro fuzzy inference system
The adaptive neuro fuzzy inference system (ANFIS), introduced by Jyh-Shing Jang in 1993, is a Sugeno fuzzy inference system whose rules and membership functions are tuned from data by neural learning.
Admissible set
An admissible set is a transitive set whose membership relation models Kripke–Platek set theory, a weak ZF fragment; the hereditarily finite sets are the smallest example.
AIXI
AIXI, also written AIξ, is a theoretical mathematical model of an optimal reinforcement learning agent, constructed by Marcus Hutter by combining Solomonoff induction with sequential decision theory.
Algebraic closure (model theory)
In model theory, the algebraic closure of a set is the collection of elements lying in some finite set definable from it, and in algebraically closed fields it matches the usual field-theoretic algebraic closure.
Algebraic data type
An algebraic data type (ADT), also called an algebraic type, is a composite type built by combining simpler types with sum and product operations, a core feature of Haskell.
Algorithmic probability
Algorithmic probability, also called Solomonoff or universal probability, is a mathematical prior introduced by Ray Solomonoff in 1960 that assigns shorter strings higher probability and underlies Solomonoff induction.
Alpha recursion theory
Alpha recursion theory (Α-recursion theory), also called admissible recursion theory, is a branch of mathematical logic generalizing computability theory from the natural numbers to admissible ordinals.
Alternating-time temporal logic
Alternating-time temporal logic (ATL) is a modal temporal logic stating what groups of agents can enforce by strategy, introduced by Alur, Henzinger, and Kupferman and published in full in 2002.
Amorphous set
An amorphous set is an infinite set that cannot be partitioned into two disjoint infinite subsets; such sets can exist only in Zermelo–Fraenkel set theory without the axiom of choice.
Analytic proof
An analytic proof is a proof in which only subformulas of the statement being proved appear, obtained via Gentzen's 1935 cut-elimination theorem, central to proof theory.
Analytic set
An analytic set is a subset of a Polish space that is the continuous image of a Polish space, or equivalently the projection of a Borel set.
Analytical hierarchy
The analytical hierarchy is a classification of relations on natural numbers by the function quantifiers needed to define them, the second-order counterpart of the arithmetical hierarchy, developed by Stephen Cole Kleene in 1955.
Approximate message passing
Approximate message passing (AMP) is a class of iterative algorithms for high-dimensional statistical estimation, introduced for compressed sensing in 2009, whose error is exactly predicted by state evolution.
Argument from ignorance
Argument from ignorance (Latin argumentum ad ignorantiam), or appeal to ignorance, is an informal fallacy inferring that a claim is true or false because it has not been proven otherwise.
Argumentum ad populum
Argumentum ad populum, also called the bandwagon fallacy, is an informal logical fallacy in which a claim is treated as true simply because many people believe it.
Arity
Arity, also called adicity, is the number of arguments that a function or predicate takes, chiefly in mathematical logic and programming; standard names include unary, binary, ternary, and n-ary.
Association for Symbolic Logic
The Association for Symbolic Logic (ASL) is an international organization founded in 1936 that supports research in logic and publishes three journals with Cambridge University Press.
Atomic model (model theory)
In model theory, an atomic model is a model of a first-order theory whose every realized type is isolated by a single formula, making it a small model.
Axiom
An axiom is a proposition accepted without proof from which the theorems of a theory are derived, a method beginning with Euclid's Elements and formalized by Hilbert in 1899.
Axiom of choice
The axiom of choice is the principle of set theory that every collection of nonempty sets has a function selecting one element from each set, formulated by Zermelo in 1904.
Axiom of countable choice
The axiom of countable choice, usually denoted ACω, states that every countable family of nonempty sets has a choice function and is weaker than the full axiom of choice.
Axiom of dependent choice
The axiom of dependent choice (DC), also called the principle of dependent choices, is a weak form of the axiom of choice formulated by Paul Bernays in 1942.