17
$\begingroup$

This question already has an answer here:

In logic, what is the difference between a predicate and a function?

To be specific, I am just interested in First Order Logic.

Thanks!

$\endgroup$

marked as duplicate by José Carlos Santos, ancientmathematician, Gibbs, Adrian Keister, Arnaud D. Feb 6 at 21:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Do you know what either "predicate" or "function" means? They really aren't very similar. $\endgroup$ – Chris Eagle Feb 27 '13 at 15:14
8
$\begingroup$

In addition to the link above What is the difference between a predicate and a function, you might want to read the distinctions provided by Wikipedia. See, e.g.

In short, a predicate is a (strictly Boolean-valued) function, but a function is not necessarily, and usually not, a predicate.

A predicate takes one or more argument(s) and evaluates to a Boolean value: true, or false. For $x, y \in \mathbb{Z}$, $\;x \leq y,\;$ is a predicate: its "output" is true, or false. $\;\leq(x, y) \mapsto \{\text{true or false}\}$.

Functions takes of one or more "arguments" (elements) in a set (from the domain of the function) and assign a unique element of another set (which is the range of the function). Note, sometimes the domain is the same set as the range. Arguments of the domain and elements of the range are in the "domain of discourse."

Note: Both predicates and functions have an associated "arity," meaning the number of arguments in in the domain that are mapped onto each value, or respectively, element, of range.

So, e.g., the "arity" of the predicate "x is a parrot": $P(x)$ is one; the arity of the predicate "y sits between x and z": $B(x, y, z)$ is three. In each case the output is true or false.

Addition of integers, on the other hand, is a function of arity two, which takes two numbers as arguments, say $x, y \in \mathbb{Z}$ and returns a number $z = x + y\;\in \mathbb{Z}$

$\endgroup$
  • 1
    $\begingroup$ It is more appropriate to say predicate is proposition-valued function, for example in induction you need to express P(n) => P(n+1), you do not think P(n) as a boolean. $\endgroup$ – golopot Dec 21 '17 at 7:42
13
$\begingroup$

Syntactically predicates are used to form formulas; function symbols are used to form terms.

Terms later translate to objects in the structure, whereas formulas are evaluated to be true or false in a particular structure and assignment.

From the semantic point of view there is little difference from how we usually treat functions and relations. In the sense that an $n$-ary function is just an $(n+1)$-ary predicate. In fact if $F$ is a binary function symbol then $\{(x,y,z)\mid F(x,y)=z\}$ is a definable ternary relation in every structure.

In the other direction if we have a predicate $R(x,y)$ and we know that in a certain structure for the language, $M$, every $u$ has exactly one $v$ such that $M\models R(u,v)$ then in fact $R$ defines a function $f_R(u)$, by saying that "$f_R(u)$ is the unique object $v$ such that $R(u,v)$ holds" we essentially write $f_R(u)=v$, and while we cannot use this to create syntactical terms, we can always write a formula and require that a variable satisfies this condition - so effectively we do write $f_R(u)$.

This is why when we deal with theories rather than structures we can always assume the symbols are relations, because we can add axioms specifying that these relations are really functions (or constants which are constant functions of course, or relations which exactly one object satisfies).

$\endgroup$
  • $\begingroup$ Great answer by providing both syntactic and semantic point of view. For "and while we cannot use this to create syntactical terms, we can always write a formula and require that a variable satisfies this condition", I would appreciate if you could elaborate a bit more. What does the first "this" stand for? Why can we not use it to create syntactic terms? How to write such a formula and require what variable to satisfy the uniqueness condition? It would be clearer if we consider the function symbols zero and succ for Peano numbers. Could you illustrate your point for them? Thanks. $\endgroup$ – day Jun 30 '13 at 20:50
  • $\begingroup$ @plmday: "this" means the condition of being the 'image' of $u$, i.e. the unique $v$ such that $R(u,v)$ holds. As for the second part, terms are defined as variables, constants, or using function symbols with previously defined terms. If there are no function symbols then we cannot write terms which are not constant or variables. If we say "Okay, take $F$ to be a binary relation instead of an unary function symbol (and add an axiom stating that the relation is a function, of course)" then we don't have $F$ as a function symbol anymore, so writing $F(x)$ as a term is not allowed anymore. $\endgroup$ – Asaf Karagila Jun 30 '13 at 21:31
  • $\begingroup$ Thanks for the answer. So the role of function symbols cannot be unified into predicate symbols, we do need them, even though their functionality can be simulated by a predicate (together with the uniqueness condition). But it seems not all their functionality can be simulated. In particular, I do not know how to simulate those function symbols that act as constructors, for example, succ, and zero (a so-called constant, which is typically regarded as a function symbol of zero arity). Do you have any idea? $\endgroup$ – day Jul 1 '13 at 9:16
2
$\begingroup$

I would say that : predicate give you true or false based on your input(s). While, a function gives you an output per your input(s). So a predicate is a special function gives you only "true" or "false".

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.