Extension (predicate logic)

The extension of a predicatea truth-valued function

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...

is the set of tuple

Tuple

In mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...

s of values that, used as arguments, satisfy the predicate. Such a set of tuples is 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...

.

For example the statement "d2 is the weekday following d1"
can be seen as a truth function associating to each tuple (d2, d1)
the value true or false. The extension of this truth function
is, by convention, the set of all such tuples associated with the
value true, i.e.

{(Monday, Sunday),
(Tuesday, Monday),
(Wednesday, Tuesday),
(Thursday, Wednesday),
(Friday, Thursday),
(Saturday, Friday),
(Sunday, Saturday)}

By examining this extension we can conclude that "Tuesday is the weekday following Saturday" (for example) is false.

Using 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...

, the extension of the n-ary predicate can be written as

Relationship with characteristic function

If the values 0 and 1 in the range of a characteristic function

Characteristic function

In mathematics, characteristic function can refer to any of several distinct concepts:* The most common and universal usage is as a synonym for indicator function, that is the function* In probability theory, the characteristic function of any probability distribution on the real line is given by...

are identified with the values false and true, respectivelymaking the characteristic function a predicate, then for all relations R and predicates the following two statements are equivalent:

• is the characteristic function of R;
• R is the extension of .