Predicate (logic)

Symbol representing a property or relation in logic

For other uses, see Predicate (disambiguation) § Logic.

In logic, a predicate is a symbol that represents a property or a relation. For instance, in the first-order formula P ( a ) {\displaystyle P(a)} , the symbol  P {\displaystyle P} is a predicate that applies to the individual constant a {\displaystyle a} . Similarly, in the formula  R ( a , b ) {\displaystyle R(a,b)} , the symbol  R {\displaystyle R} is a predicate that applies to the individual constants  a {\displaystyle a} and  b {\displaystyle b} .

According to Gottlob Frege, the meaning of a predicate is exactly a function from the domain of objects to the truth values "true" and "false".

In the semantics of logic, predicates are interpreted as relations. For instance, in a standard semantics for first-order logic, the formula  R ( a , b ) {\displaystyle R(a,b)} would be true on an interpretation if the entities denoted by  a {\displaystyle a} and  b {\displaystyle b} stand in the relation denoted by  R {\displaystyle R} . Since predicates are non-logical symbols, they can denote different relations depending on the interpretation given to them. While first-order logic only includes predicates that apply to individual objects, other logics may allow predicates that apply to collections of objects defined by other predicates.

## Predicates in different systems

[edit]

A predicate is a statement or mathematical assertion that contains variables, sometimes referred to as predicate variables, and may be true or false depending on those variables’ value or values.

* In propositional logic, atomic formulas are sometimes regarded as zero-place predicates.[1] In a sense, these are nullary (i.e. 0-arity) predicates.
* In first-order logic, a predicate forms an atomic formula when applied to an appropriate number of terms.
* In set theory with the law of excluded middle, predicates are understood to be characteristic functions or set indicator functions (i.e., functions from a set element to a truth value). Set-builder notation makes use of predicates to define sets.
* In autoepistemic logic, which rejects the law of excluded middle, predicates may be true, false, or simply unknown. In particular, a given collection of facts may be insufficient to determine the truth or falsehood of a predicate.
* In fuzzy logic, the strict true/false valuation of the predicate is replaced by a quantity interpreted as the degree of truth.

## See also

[edit]

* Classifying topos
* Free variables and bound variables
* Multigrade predicate
* Opaque predicate
* Predicate functor logic
* Predicate variable
* Truthbearer
* Truth value
* Well-formed formula

## References

[edit]

1. ^ Lavrov, Igor Andreevich; Maksimova, Larisa (2003). Problems in Set Theory, Mathematical Logic, and the Theory of Algorithms. New York: Springer. p. 52\. ISBN 0306477122.

## External links

[edit]

* Introduction to predicates

* v
* t
* e

Mathematical logic

General|

* Axiom
* list
* Cardinality
* First-order logic
* Formal proof
* Formal semantics
* Foundations of mathematics
* Information theory
* Lemma
* Logical consequence
* Model
* Theorem
* Theory
* Type theory

Theorems (list)
and paradoxes|

* Gödel's completeness and incompleteness theorems
* Tarski's undefinability
* Banach–Tarski paradox
* Cantor's theorem, paradox and diagonal argument
* Compactness
* Halting problem
* Lindström's
* Löwenheim–Skolem
* Russell's paradox

Logics|

| Traditional|

* Classical logic
* Logical truth
* Tautology
* Proposition
* Inference
* Logical equivalence
* Consistency
* Equiconsistency
* Argument
* Soundness
* Validity
* Syllogism
* Square of opposition
* Venn diagram

|

Propositional|

* Boolean algebra
* Boolean functions
* Logical connectives
* Propositional calculus
* Propositional formula
* Truth tables
* Many-valued logic
* 3
* finite
* ∞

Predicate|

* First-order
* list
* Second-order
* Monadic
* Higher-order
* Fixed-point
* Free
* Quantifiers
* Predicate
* Monadic predicate calculus

Set theory|

* Set
* hereditary
* Class
* (Ur-)Element
* Ordinal number
* Extensionality
* Forcing
* Relation
* equivalence
* partition
* Set operations:
* intersection
* union
* complement
* Cartesian product
* power set
* identities

Types of sets|

* Countable
* Uncountable
* Empty
* Inhabited
* Singleton
* Finite
* Infinite
* Transitive
* Ultrafilter
* Recursive
* Fuzzy
* Universal
* Universe
* constructible
* Grothendieck
* Von Neumann

Maps and cardinality|

* Function/Map
* domain
* codomain
* image
* In/Sur/Bi-jection
* Schröder–Bernstein theorem
* Isomorphism
* Gödel numbering
* Enumeration
* Large cardinal
* inaccessible
* Aleph number
* Operation
* binary

Set theories|

* Zermelo–Fraenkel
* axiom of choice
* continuum hypothesis
* General
* Kripke–Platek
* Morse–Kelley
* Naive
* New Foundations
* Tarski–Grothendieck
* Von Neumann–Bernays–Gödel
* Ackermann
* Constructive

Formal systems (list),
language and syntax|

* Alphabet
* Arity
* Automata
* Axiom schema
* Expression
* ground
* Extension
* by definition
* conservative
* Relation
* Formation rule
* Grammar
* Formula
* atomic
* closed
* ground
* open
* Free/bound variable
* Language
* Metalanguage
* Logical connective
* ¬
* ∨
* ∧
* →
* ↔
* =
* Predicate
* functional
* variable
* propositional variable
* Proof
* Quantifier
* ∃
* !
* ∀
* rank
* Sentence
* atomic
* spectrum
* Signature
* String
* Substitution
* Symbol
* function
* logical/constant
* non-logical
* variable
* Term
* Theory
* list

Example axiomatic
systems (list)|

* of arithmetic:
* Peano
* second-order
* elementary function
* primitive recursive
* Robinson
* Skolem
* of the real numbers
* Tarski's axiomatization
* of Boolean algebras
* canonical
* minimal axioms
* of geometry:
* Euclidean:
* Elements
* Hilbert's
* Tarski's
* non-Euclidean

* Principia Mathematica

Proof theory|

* Formal proof
* Natural deduction
* Logical consequence
* Rule of inference
* Sequent calculus
* Theorem
* Systems
* axiomatic
* deductive
* Hilbert
* list
* Complete theory
* Independence (from ZFC)
* Proof of impossibility
* Ordinal analysis
* Reverse mathematics
* Self-verifying theories

Model theory|

* Interpretation
* function
* of models
* Model
* equivalence
* finite
* saturated
* spectrum
* submodel
* Non-standard model
* of arithmetic
* Diagram
* elementary
* Categorical theory
* Model complete theory
* Satisfiability
* Semantics of logic
* Strength
* Theories of truth
* semantic
* Tarski's
* Kripke's
* T-schema
* Transfer principle
* Truth predicate
* Truth value
* Type
* Ultraproduct
* Validity

Computability theory|

* Church encoding
* Church–Turing thesis
* Computably enumerable
* Computable function
* Computable set
* Decision problem
* decidable
* undecidable
* P
* NP
* P versus NP problem
* Kolmogorov complexity
* Lambda calculus
* Primitive recursive function
* Recursion
* Recursive set
* Turing machine
* Type theory

Related|

* Abstract logic
* Algebraic logic
* Automated theorem proving
* Category theory
* Concrete/Abstract category
* Category of sets
* History of logic
* History of mathematical logic
* timeline
* Logicism
* Mathematical object
* Philosophy of mathematics
* Supertask

Mathematics portal

Authority control databases

National|

* Germany
* United States
* Latvia
* Israel

Other|

* Yale LUX

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template