534 articles
Sacks splitting theorem
The Sacks splitting theorem is a 1963 result in computability theory: every noncomputable c.e. set splits into two disjoint c.e. sets, each of low degree.
Satisfaction relation
The satisfaction relation in logic holds between a structure, a formula, and an assignment of objects to variables, written M, s models φ, and was introduced by Alfred Tarski in 1933.
Satisfiability
Satisfiability is the property of a logical formula being true under at least one interpretation, or model. Its decision problem spans NP-complete Boolean SAT and undecidable first-order logic.
Satisfiability modulo theories
Satisfiability modulo theories (SMT) is the decision problem of whether a formula is satisfiable under a background theory, extending Boolean SAT to first-order logic for verification.
Saturated model
A saturated model, also called a saturated structure, is a model of a first-order theory realizing every type over smaller parameter sets, a key concept from Morley and Vaught's 1962 paper.
Saul Kripke
Saul Kripke, or Saul Aaron Kripke, was an American philosopher and logician, 1940 to 2022, whose Naming and Necessity and possible worlds semantics reshaped analytic philosophy.
Scale (descriptive set theory)
In descriptive set theory, a scale, or scale property, is a structured family of norms on a pointset that selects canonical elements and uniformizes relations, first isolated by Yiannis Moschovakis.
Second-order logic
Second-order logic is a formal logical system whose quantifiers range over properties, relations, and functions, not just individuals; unlike first-order logic, it can uniquely characterize structures like the natural numbers.
Self-reference
Self-reference, also called self-reflexivity, is the relation an object bears when it refers to itself, the source of the liar paradox and Gödel's incompleteness theorems.
Semantic theory of truth
The semantic theory of truth, also called Tarski's definition of truth, is a definition of truth for formalized languages developed by Alfred Tarski in the 1930s.
Semantics (logic)
Semantics, also called the semantics of logic, is the part of logic assigning truth conditions to formal-language sentences, chiefly through the model-theoretic semantics introduced by Alfred Tarski.
Semi-structured data
Semi-structured data is data with some structure beyond plain text, such as tags or nested fields, but no fixed schema; XML and JSON are the most widespread formats.
Separation logic
Separation logic is an extension of Hoare logic for verifying programs that manipulate heap-allocated pointer structures, using a separating conjunction for disjoint memory; it won the 2016 Gödel Prize.
Sequent
A sequent is an expression Γ ⇒ Δ in a formal logic, read as yielding the right side from the left, introduced by Gerhard Gentzen in his 1934/35 dissertation.
Sequent calculus
The sequent calculus, or Gentzen calculus, is a formal proof system for logic introduced by Gerhard Gentzen in 1934, a central tool of structural proof theory.
Set (mathematics)
A set is a well-determined collection of distinct objects, called its members or elements, treated as a single mathematical object; set theory is the standard foundation of mathematics.
Set theory
Set theory is the branch of mathematics that studies collections of objects called sets, founded by Georg Cantor in the 1870s and now the standard foundation of modern mathematics.
Set-builder notation
Set-builder notation, also called set comprehension, is the mathematical notation for specifying a set by a property its members satisfy, as in {x ∈ A : P(x)}.
Set-theoretic definition of natural numbers
The set-theoretic definition of natural numbers identifies 0, 1, 2, and so on with sets, most often the von Neumann ordinals, letting arithmetic develop inside set theories like ZFC.
Set-theoretic multiverse
The set-theoretic multiverse is a view in the philosophy of set theory, introduced by Joel David Hamkins, holding that there are many concepts of set rather than one absolute universe of sets.
Sheffer stroke
The Sheffer stroke, or NAND, is a binary logical connective false only when both inputs are true, named for Henry M. Sheffer, who published it in 1913.
Sierpiński set
A Sierpiński set is an uncountable set of real numbers meeting every Lebesgue measure zero set in only countably many points, first shown to exist under CH in 1924.
Signal temporal logic
Signal temporal logic (STL) is a temporal logic for specifying and monitoring properties of real-valued, dense-time signals in cyber-physical systems, analog circuits, and systems biology.
Signature (logic)
In mathematical logic, a signature, also called a vocabulary or language, is the collection of constant, function, and relation symbols, with their arities, for building first-order formulas.
Simple set (computability theory)
A simple set, introduced by Emil Post in 1944, is a recursively enumerable set of natural numbers whose complement is infinite but contains no infinite recursively enumerable subset.
Simple theory (model theory)
In model theory, a simple theory is a complete first-order theory in which no formula has the tree property. Introduced by Shelah, the class properly contains the stable theories.
Simply typed lambda calculus
The simply typed lambda calculus is a typed form of lambda calculus formulated by Alonzo Church in 1940, where every term has a type and all programs terminate.
Skolem normal form
Skolem normal form, also known as Skolem standard form, is a form of a first-order logic formula with only universal quantifiers, introduced by Thoralf Skolem in 1920.
Skolemization
Skolemization is a transformation in first-order logic that removes existential quantifiers by replacing their variables with newly introduced Skolem functions, producing a formula satisfiable if and only if the original.
Solomonoff's theory of inductive inference
Solomonoff's theory of inductive inference, also called Solomonoff induction, is a mathematical framework for sequence prediction presented by Ray J. Solomonoff in 1964 that initiated algorithmic information theory.