In
formal logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premise ...
and related branches of
mathematics, a functional predicate, or function symbol, is a logical symbol that may be applied to an object term to produce another object term.
Functional predicates are also sometimes called mappings, but that term has
additional meanings in mathematics.
In a
model, a function symbol will be modelled by a
function.
Specifically, the symbol ''F'' in a
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of s ...
is a functional symbol if,
given any symbol ''X'' representing an object in the language, ''F''(''X'') is again a symbol representing an object in that language.
In
typed logic
In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a foundat ...
, ''F'' is a functional symbol with ''domain'' type T and ''codomain'' type U if, given any symbol ''X'' representing an object of type T, ''F''(''X'') is a symbol representing an object of type U.
One can similarly define function symbols of more than one variable, analogous to functions of more than one variable; a function symbol in
zero
0 (zero) is a number representing an empty quantity. In place-value notation such as the Hindu–Arabic numeral system, 0 also serves as a placeholder numerical digit, which works by multiplying digits to the left of 0 by the radix, usu ...
variables is simply a
constant symbol.
Now consider a model of the formal language, with the types T and U modelled by
sets ''Tand
''Uand each symbol ''X'' of type T modelled by an element
'X''in
''T
Then ''F'' can be modelled by the set
:
which is simply a
function with domain
''Tand codomain
''U
It is a requirement of a consistent model that
'F''(''X'')=
'F''(''Y'')whenever
'X''=
'Y''
Introducing new function symbols
In a treatment of
predicate logic
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...
that allows one to introduce new predicate symbols, one will also want to be able to introduce new function symbols. Given the function symbols ''F'' and ''G'', one can introduce a new function symbol ''F'' ∘ ''G'', the ''
composition'' of ''F'' and ''G'', satisfying (''F'' ∘ ''G'')(''X'') = ''F''(''G''(''X'')),
for all ''X''.
Of course, the right side of this equation doesn't make sense in typed logic unless the domain type of ''F'' matches the codomain type of ''G'', so this is required for the composition to be defined.
One also gets certain function symbols automatically.
In untyped logic, there is an ''identity predicate'' id that satisfies id(''X'') = ''X'' for all ''X''.
In typed logic, given any type T, there is an identity predicate id
T with domain and codomain type T; it satisfies id
T(''X'') = ''X'' for all ''X'' of type T.
Similarly, if T is a
subtype
Subtype may refer to:
* Viral subtypes, such as Subtypes of HIV
* Subtyping
In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which a subtype is a datatype that is ...
of U, then there is an inclusion predicate of domain type T and codomain type U that satisfies the same equation; there are additional function symbols associated with other ways of constructing new types out of old ones.
Additionally, one can define functional predicates after proving an appropriate
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of ...
.
(If you're working in a
formal system
A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system.
A for ...
that doesn't allow you to introduce new symbols after proving theorems, then you will have to use relation symbols to get around this, as in the next section.)
Specifically, if you can prove that for every ''X'' (or every ''X'' of a certain type),
there exists a
unique ''Y'' satisfying some condition ''P'', then you can introduce a function symbol ''F'' to indicate this.
Note that ''P'' will itself be a relational
predicate involving both ''X'' and ''Y''.
So if there is such a predicate ''P'' and a theorem:
: For all ''X'' of type T, for some unique ''Y'' of type U, ''P''(''X'',''Y''),
then you can introduce a function symbol ''F'' of domain type T and codomain type U that satisfies:
: For all ''X'' of type T, for all ''Y'' of type U, ''P''(''X'',''Y'')
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bi ...
''Y'' = ''F''(''X'').
Doing without functional predicates
Many treatments of predicate logic don't allow functional predicates, only relational
predicates.
This is useful, for example, in the context of proving
metalogical theorems (such as
Gödel's incompleteness theorems), where one doesn't want to allow the introduction of new functional symbols (nor any other new symbols, for that matter).
But there is a method of replacing functional symbols with relational symbols wherever the former may occur; furthermore, this is algorithmic and thus suitable for applying most metalogical theorems to the result.
Specifically, if ''F'' has domain type T and
codomain
In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either ...
type U, then it can be replaced with a predicate ''P'' of type (T,U).
Intuitively, ''P''(''X'',''Y'') means ''F''(''X'') = ''Y''.
Then whenever ''F''(''X'') would appear in a statement, you can replace it with a new symbol ''Y'' of type U and include another statement ''P''(''X'',''Y'').
To be able to make the same deductions, you need an additional proposition:
:
For all ''X'' of type T, for some
unique ''Y'' of type U, ''P''(''X'',''Y'').
(Of course, this is the same proposition that had to be proven as a theorem before introducing a new function symbol in the previous section.)
Because the elimination of functional predicates is both convenient for some purposes and possible, many treatments of formal logic do not deal explicitly with function symbols but instead use only relation symbols; another way to think of this is that a functional predicate is a ''special kind of'' predicate, specifically one that satisfies the proposition above.
This may seem to be a problem if you wish to specify a proposition
schema
The word schema comes from the Greek word ('), which means ''shape'', or more generally, ''plan''. The plural is ('). In English, both ''schemas'' and ''schemata'' are used as plural forms.
Schema may refer to:
Science and technology
* SCHEMA ...
that applies only to functional predicates ''F''; how do you know ahead of time whether it satisfies that condition?
To get an equivalent formulation of the schema, first replace anything of the form ''F''(''X'') with a new variable ''Y''.
Then
universally quantify over each ''Y'' immediately after the corresponding ''X'' is introduced (that is, after ''X'' is quantified over, or at the beginning of the statement if ''X'' is free), and guard the quantification with ''P''(''X'',''Y'').
Finally, make the entire statement a
material consequence of the uniqueness condition for a functional predicate above.
Let us take as an example the
axiom schema of replacement
In set theory, the axiom schema of replacement is a schema of axioms in Zermelo–Fraenkel set theory (ZF) that asserts that the image of any set under any definable mapping is also a set. It is necessary for the construction of certain infi ...
in
Zermelo–Fraenkel set theory.
(This example uses
mathematical symbols.)
This schema states (in one form), for any functional predicate ''F'' in one variable:
:
First, we must replace ''F''(''C'') with some other variable ''D'':
:
Of course, this statement isn't correct; ''D'' must be quantified over just after ''C'':
:
We still must introduce ''P'' to guard this quantification:
:
This is almost correct, but it applies to too many predicates; what we actually want is:
:
This version of the axiom schema of replacement is now suitable for use in a formal language that doesn't allow the introduction of new function symbols. Alternatively, one may interpret the original statement as a statement in such a formal language; it was merely an abbreviation for the statement produced at the end.
See also
*
Function symbol (logic) In mathematical logic, an uninterpreted function or function symbol is one that has no other property than its name and ''n-ary'' form. Function symbols are used, together with constants and variables, to form terms.
The theory of uninterpreted fu ...
*
Logical connective
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...
*
Logical constant
{{DEFAULTSORT:Functional Predicate
Model theory