534 articles
Q.E.D.
Q.E.D., short for the Latin quod erat demonstrandum ("which was to be demonstrated"), is written at the end of a mathematical proof to signal completion.
Quantified modal logic
Quantified modal logic (QML) combines a propositional modal logic with first-order quantifiers; the Barcan Formula is valid under constant domains but fails under the varying domains Kripke introduced in 1963.
Quantifier (logic)
A quantifier, also called a logical quantifier, is an operator in predicate logic, such as "for all" or "there exists", expressing how many objects satisfy a formula.
Quantifier elimination
Quantifier elimination is a property of first-order theories in model theory: every formula is equivalent, over the theory, to one with no quantifiers, which can yield decidability.
Quotient set
A quotient set is the set of all equivalence classes of a set under an equivalence relation, so equivalence becomes equality, as in the integers modulo n.
Random degree
A random degree is an equivalence class of infinite binary sequences compared by relative randomness, most commonly the K-degrees induced by prefix-free Kolmogorov complexity of initial segments.
Random forcing
Random forcing, also called Solovay forcing, is a set-theoretic forcing method, introduced by Robert Solovay in the 1960s, that adjoins a real avoiding all null sets.
Random graph
A random graph, or random network, is a graph whose edges are placed by random rules, a field founded by Paul Erdős and Alfréd Rényi in the late 1950s.
Rank-into-rank cardinal
A rank-into-rank cardinal is the critical point of a nontrivial elementary embedding from some rank into itself, a hypothesis at the top of the large cardinal hierarchy in set theory.
Real closed field
A real closed field is an ordered field where every non-negative element is a square and every odd-degree polynomial has a root, introduced by Artin and Schreier in the 1920s.
Realizability
Realizability is a family of semantic techniques in mathematical logic, introduced by Stephen Cole Kleene in 1945, where a number or program counts as evidence for a statement.
Recursion theorem fixed point
In computability theory, a recursion theorem fixed point is a program index n with the same partial function as its transform, φn = φf(n), guaranteed by Kleene's second recursion theorem.
RecycleUnits
RecycleUnits, also written Recycle-Units, is a linear-time algorithm that shrinks SAT solvers' resolution proofs and their unsatisfiable cores, introduced by IBM Haifa and Technion researchers in 2008.
Reflection principle
A reflection principle in set theory states that any first-order statement true of the universe of sets V is already true in some smaller set-sized Vα.
Reflection principles
A reflection principle is a formal schema asserting that a theory is sound, meaning every sentence it proves is true; it extends theories beyond what they can prove about themselves.
Reflexive relation
A reflexive relation, also called the reflexive property, is a binary relation on a set in which every element is related to itself, as with the identity relation.
Regress argument (epistemology)
The regress argument, or epistemic regress, is a problem in epistemology holding that every chain of justifying reasons must end in basic beliefs, circle, or continue forever.
Relative consistency
Relative consistency is a property of formal theories: a theory S is consistent relative to T when Con(T) implies Con(S), since strong theories like ZF cannot prove their own consistency.
Relevance logic
Relevance logic, also known as relevant logic, is a family of non-classical logics developed to avoid the paradoxes of material and strict implication by requiring content connection.
Relevant type theory
Relevant type theory is the substructural type system with exchange and contraction but no weakening, so every variable is used at least once; it corresponds to relevant logic and the λI-calculus.
Rete algorithm
The Rete algorithm, also called the Rete network, is an efficient pattern-matching algorithm for production rule systems, developed by Charles Forgy at Carnegie Mellon University from 1974.
Reverse mathematics
Reverse mathematics, also known as reverse math, is a program in mathematical logic founded by Harvey Friedman in 1974 that determines which axioms are necessary to prove theorems of ordinary mathematics.
Rice–Shapiro theorem
The Rice–Shapiro theorem characterizes the semi-decidable index sets of partial computable functions: a property is semi-decidable exactly when it is upward closed and witnessed by finite subfunctions.
Richard M. Friedberg
Richard M. Friedberg is an American theoretical physicist and logician at Columbia University known for solving Post's problem in 1957 and for an early 1958 paper on machine learning.
Rigid designator
A rigid designator is an expression, such as a proper name, that names the same object in every possible world, a concept introduced by Saul Kripke.
Rigour
Rigour, or rigor, in mathematics is the virtue of a proof that establishes its conclusion through acceptable deductive steps, with no reliance on intuition or unchecked assumptions.
Robinson arithmetic
Robinson arithmetic, usually denoted Q, is a finitely axiomatized first-order theory of the natural numbers introduced by Raphael Robinson in 1950 that drops Peano arithmetic's induction schema.
Rule of inference
A rule of inference, also called an inference rule, is a syntactic schema in logic that licenses a proof step from premises to a conclusion.
Russell's paradox
Russell's paradox is a contradiction in naive set theory, found by Bertrand Russell around 1901, concerning the set of all sets that are not members of themselves.
S5 (modal logic)
S5 is a system of modal logic, introduced by Lewis and Langford in 1932 and commonly used as the logic of necessity and of knowledge.