534 articles
Pointclass
A pointclass is a collection of pointsets, subsets of Polish spaces, organizing definable sets of reals into hierarchies, chiefly the Borel and projective pointclasses of descriptive set theory.
Polish notation
Polish notation, also called prefix notation or Łukasiewicz notation, is a mathematical notation, invented by Jan Łukasiewicz in 1924, in which operators precede their operands.
Polish space
A Polish space, or Polish metric space, is a separable, completely metrizable topological space; examples include ℝⁿ, and the concept is central to descriptive set theory.
Possible world
A possible world, also called a possible universe, is a complete way things could have been, used in modal logic to define possibility and necessity.
Power set
The power set of a set A, written P(A) or 2^A, is the set of all subsets of A, always including the empty set and A itself.
Pregeometry (model theory)
In model theory, a pregeometry, known in combinatorics as a matroid, is a set with a finitary closure operator satisfying the Steinitz exchange property, abstracting linear span and algebraic closure.
Prenex normal form
Prenex normal form (PNF), also called prenex form, is a standard form for first-order logic formulas in which all quantifiers are gathered at the front, before a quantifier-free matrix.
Presburger arithmetic
Presburger arithmetic is the first-order theory of the integers with addition and order, omitting multiplication; Mojżesz Presburger proved it decidable in 1929, while adding multiplication yields undecidability.
Prime model
A prime model in model theory is a model that can be elementarily embedded into every other model of its complete theory, a notion Robert Vaught introduced in 1961.
Primitive recursive arithmetic
Primitive recursive arithmetic (PRA) is a quantifier-free formal theory of the natural numbers that serves in proof theory as the standard formalization of Hilbert's finitist reasoning about numbers.
Principia Mathematica
Principia Mathematica is a three-volume work of formal logic by Alfred North Whitehead and Bertrand Russell, published by Cambridge University Press in 1910, 1912, and 1913, defending logicism.
Principle of compositionality
The principle of compositionality, also called Frege's principle, is the thesis that an expression's meaning is determined by its structure and the meanings of its constituents.
Principle of explosion
The principle of explosion, also known as ex falso quodlibet or ex contradictione quodlibet, is the rule of inference that anything at all follows from a contradiction.
Priority method
The priority method is a technique in computability theory for constructing computably enumerable sets by satisfying ranked requirements, invented independently by Friedberg and Muchnik in the 1950s.
Probabilistic logic
Probabilistic logic is a family of formal frameworks combining logical representation with probability theory, so inference returns the probability of a query instead of a plain true-or-false verdict.
Problem of evil
The problem of evil is the philosophical problem of how evil and suffering can coexist with, or count against, an omnipotent, omniscient, and perfectly good God.
Problem of universals
The problem of universals, also called the problem of one and many, asks whether properties, kinds, and relations exist independently of particulars, and how they relate to the things that have them.
Projective hierarchy
The projective hierarchy is a classification of sets of real numbers, built from the analytic sets by complementation and projection, introduced by Lusin and Sierpiński in 1925.
Proof calculus
A proof calculus is a formal system of axioms and inference rules whose derivations establish the theorems of a logic; main forms include Hilbert systems, natural deduction, and sequent calculus.
Proof net
A proof net is a graph-based representation of a proof in linear logic, introduced by Jean-Yves Girard in 1987 to eliminate trivial rule permutations of sequent calculus derivations.
Proof-theoretic semantics
Proof-theoretic semantics is an alternative to model-theoretic semantics that explains the meaning of logical constants in terms of the inference rules governing their behavior in proofs.
Proper forcing
Proper forcing is a property of forcing notions in set theory, introduced by Saharon Shelah in 1980, that preserves ω₁ and is preserved under countable-support iterations.
Proper forcing axiom
The Proper Forcing Axiom (PFA) is a strengthening of Martin's Axiom in set theory, formulated by James Baumgartner in the early 1980s using Shelah's notion of properness.
Propositional calculus
A propositional calculus is a formal proof system for propositional logic, given by axioms and inference rules such as modus ponens; first axiomatized by Frege in 1879, it is sound and complete.
Propositional dynamic logic
Propositional dynamic logic (PDL) is a modal logic for reasoning about programs, in which [α]A means A holds after every execution of program α. Fischer and Ladner defined it in 1979.
Propositional logic
Propositional logic, also known as sentential logic or sentential calculus, studies reasoning with whole propositions that are true or false, joined by connectives like and, or, and if-then.
Propositional proof system
A propositional proof system is any polynomial-time computable function whose range is exactly the propositional tautologies, the abstract definition by Cook and Reckhow in 1979 that founded proof complexity.
Protein–protein interaction prediction
Protein–protein interaction prediction is the use of computational methods, from genomic context and co-evolution to deep learning, to infer whether two proteins bind or otherwise associate.
Provability logic
Provability logic is a modal logic, centered on the system GL, that studies what arithmetical theories like Peano Arithmetic can prove about their own provability.
Pullback (category theory)
A pullback, also called the fibered product, is the limit in category theory of two morphisms with a common codomain; in sets it is the set of pairs (a, b) with f(a) = g(b).