I had a recent conversation with a professional mathematician about the status of relations, functions and predicates. I was arguing that it seems intuitive (to me at least) to classify them in this hierarchy (as to which is more primitive):

  1. All predicates are functions.
  2. All functions are relations.

The obvious problem here is that it seems intuitive that unary or even nullary <predicates/relations/functions> are more primitive than their n-ary variants. Is there a way to compose functions as at least unary relations or vice versa (relations as unary functions)? If not, is it possible to order them in such a hierarchy given the binary restriction.

Finally, if there is something more primitive that has a formal definition, then that would do as well. A resource or explanation pointing to how at least functions, relations and predicates are composed using this notion would be helpful.

  • $\begingroup$ Relevant: Noah Schweber's answer to Is set theory the most fundamental aspect of mathematics? AND Foundation of Formal Logic. $\endgroup$ May 30 at 21:43
  • $\begingroup$ You have it a bit backwards. All relations are predicates, but unless a 1-ary or 0-ary predicate is a relation, not all predicates are relations. Functions are a special kind of predicate, but they behave as objects as opposed to propositions. For example, $F(a)$ means “$a$ has property $F$”, while $f(a)$ is just whatever object to which $f$ maps $a$. With this in mind, an n-ary function can be interpreted as an n+1-ary predicate. E.g., $f(x)=y$ can be understood as $F(x,y)$. Credit to math.stackexchange.com/questions/315936/predicate-vs-function as I used some of their answer. $\endgroup$
    – PW_246
    May 30 at 21:58
  • $\begingroup$ @RW_123 f(a) is an object, but f without an argument to it is definitely not a predicate since the obvious issue is predicates can only return boolean values (T or F) as opposed to functions which can return pretty much anything that is an object. This object could even be a predicate, function or a relation. Now that I think about it, predicates could actually be special case of relations where predicates are relations that only accept terms (functions or objects). $\endgroup$ May 30 at 22:09
  • $\begingroup$ Theoretical computer science can be of some help. I advise you in particular to see "lambda-calculus" which has been "implemented" (with some nuances) as LISP language. $\endgroup$
    – Jean Marie
    May 30 at 22:14
  • $\begingroup$ @JeanMarie I assume you mean simply typed lambda calculus. If so, I find the concept of types interesting, but I'm versed in it. Is it possible to reduce everything to types? $\endgroup$ May 30 at 22:20


You must log in to answer this question.

Browse other questions tagged .