Predicate (logic)
Encyclopedia
In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a predicate is commonly understood to be a boolean-valued function
Boolean-valued function
A boolean-valued function, in some usages is a predicate or a proposition, is a function of the type f : X → B, where X is an arbitrary set and where B is a boolean domain....

 P: X→ {true, false}, called the predicate on X. However, predicates have many different uses and interpretations in mathematics and logic, and their precise definition, meaning and use will vary from theory to theory. So, for example, when a theory defines the concept of a relation
Relation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...

, then a predicate is simply the characteristic function or the indicator function of a relation. However, not all theories have relations, or are founded on set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

, and so one must be careful with the proper definition and semantic interpretation of a predicate.

Simplified overview

Informally, a predicate is a statement that may be true or false depending on the values of its variables. It can be thought of as an operator or function that returns a value that is either true or false. For example, predicates are sometimes used to indicate set membership: when talking about sets, it is sometimes inconvenient or impossible to describe a set by listing all of its elements. Thus, a predicate P(x) will be true or false, depending on whether x belongs to a set.

Predicates are also commonly used to talk about the properties
Property
Property is any physical or intangible entity that is owned by a person or jointly by a group of people or a legal entity like a corporation...

 of objects, by defining the set of all objects that have some property in common. So, for example, when P is a predicate on X, one might sometimes say P is a property
Property
Property is any physical or intangible entity that is owned by a person or jointly by a group of people or a legal entity like a corporation...

 of X. Similarly, the notation P(x) is used to denote a sentence or statement P concerning the variable object x. The set defined by P(x) is written as {x | P(x)}, and is just a collection of all the objects for which P is true.

For instance, {x | x is a positive integer less than 4} is the set {1,2,3}.

If t is an element of the set {x | P(x)}, then the statement P(t) is true.

Here, P(x) is referred to as the predicate, and x the subject of the proposition
Proposition
In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...

. Sometimes, P(x) is also called a propositional function
Propositional function
A propositional function in logic, is a statement expressed in a way that would assume the value of true or false, except that within the statement is a variable that is not defined or specified, which leaves the statement undetermined...

, as each choice of x produces a proposition.

Formal definition

The precise semantic interpretation of an atomic formula and an atomic sentence will vary from theory to theory.
  • In propositional logic, atomic formulae are called propositional variable
    Propositional variable
    In mathematical logic, a propositional variable is a variable which can either be true or false...

    s.

  • In first-order logic
    First-order logic
    First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

    , an atomic formula consists of a predicate symbol applied to an appropriate number of terms.

  • In set theory
    Set theory
    Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...

    , predicates are understood to be characteristic functions or set indicator functions, i.e. functions
    Function (mathematics)
    In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

     from a set element to a truth value. Set-builder notation
    Set-builder notation
    In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by stating the properties that its members must satisfy...

     makes use of predicates to define sets.

  • In autoepistemic logic
    Autoepistemic logic
    The autoepistemic logic is a formal logic for the representation and reasoning of knowledge about knowledge. While propositional logic can only express facts, autoepistemic logic can express knowledge and lack of knowledge about facts....

    , which rejects the law of excluded middle
    Law of excluded middle
    In logic, the law of excluded middle is the third of the so-called three classic laws of thought. It states that for any proposition, either that proposition is true, or its negation is....

    , predicates may be true, false, or simply unknown; i.e. a given collection of facts may be insufficient to determine the truth or falsehood of a predicate.

  • In fuzzy logic
    Fuzzy logic
    Fuzzy logic is a form of many-valued logic; it deals with reasoning that is approximate rather than fixed and exact. In contrast with traditional logic theory, where binary sets have two-valued logic: true or false, fuzzy logic variables may have a truth value that ranges in degree between 0 and 1...

    , predicates are the characteristic functions
    Characteristic function (probability theory)
    In probability theory and statistics, the characteristic function of any random variable completely defines its probability distribution. Thus it provides the basis of an alternative route to analytical results compared with working directly with probability density functions or cumulative...

     of a probability distribution
    Probability distribution
    In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....

    . That is, the strict true/false valuation of the predicate is replaced by a quantity interpreted as the degree of truth.

  • In formal semantics, a predicate is an expression of a semantic set type
    Type theory
    In mathematics, logic and computer science, type theory is any of several formal systems that can serve as alternatives to naive set theory, or the study of such formalisms in general...

    . Equivalently, they can be thought of as set indicator functions. i.e. functions
    Function (mathematics)
    In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

     from an entity
    Entity
    An entity is something that has a distinct, separate existence, although it need not be a material existence. In particular, abstractions and legal fictions are usually regarded as entities. In general, there is also no presumption that an entity is animate.An entity could be viewed as a set...

     to a truth value.

See also

  • Free variables and bound variables
    Free variables and bound variables
    In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place...

  • Predicate functor logic
    Predicate functor logic
    In mathematical logic, predicate functor logic is one of several ways to express first-order logic by purely algebraic means, i.e., without quantified variables. PFL employs a small number of algebraic devices called predicate functors that operate on terms to yield terms...

  • Truthbearer
    Truthbearer
    Truth-bearer is a term used to designate entities that are either true or false and nothing else. The thesis that some things are true while others are false raises the question of the nature of these things. Since there is divergence of opinion on the matter, the term truthbearer is used to be...


External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK