When we talk about relations in context of mathematical logic, they are predicates that are contained in the signature of a certain language. For example the signature of ordered fields is:

$$\sigma=\{+,\times,0,1, > \}$$

Where $+,\times,0,1,$ are functions of arity 2,2,0,0 and $>$ is a relations symbol of arity 2. Here the symbol "$>$" is also called a predicate and $>(xy)$ is interpreted as "$x$ is greater then $y$" So this is just a sentence that is either true or false, therefore can be thought of as a boolean valued function as also explained on Predicate vs function.

Now what causes confusion to me is the definition of a relation as the cartesian product of two sets: "everything that is a subset of $A\times B$ is a relation." Furthermore, functions are defined just as certain subset of this cartesian product. So accoring to this definition functions are just a subset of a wider concept - relations.

But how the first and the second usage of relation go together? In the first usage there is a clear disticntion between relations and functions, relations take certain elements from doamin of discourse and make a statement out of them, which can take only two values, true or false, functions associate certain elements with others. In the second usage, on the other hand, functions and relations are very similar consepts, functions are just a certain type of relations. So do these two usages represent different consepts, or am I missing something?

  • $\begingroup$ see a recent similar post. $\endgroup$ – Mauro ALLEGRANZA Feb 3 '15 at 21:22
  • $\begingroup$ @MauroALLEGRANZA nice, but it doesn't anwer my question though $\endgroup$ – steakexchange Feb 3 '15 at 21:24
  • 1
    $\begingroup$ Note that in FOL we can, in principle, dispense with functions; we can e.g. replace the function $f(y_1,y_2)$ with the predicate $P_f(x_1,x_2,x_3)$ such that $P_f(x,y,z)$ holds iff $f(x,y)=z$. $\endgroup$ – Mauro ALLEGRANZA Feb 3 '15 at 21:25
  • 2
    $\begingroup$ But from the "philosophical" point of view, the difference is that is "set language" relations and functions are (mathematical) objects, while in logic language predicates and functions are linguistic entities; of course, their denotations are set in the domain $D$ of interpretation: a $n$-ary predicate $P$ denotes a $n$-ary relation in $D^n$ (i.e. $P^D \subseteq D^n$) while a $ n$-ary function symbol $f$ denotes a $n$-ary function $f^D : D^n \to D$, i.e. a $(n+1)$-ary relation on $D$. $\endgroup$ – Mauro ALLEGRANZA Feb 3 '15 at 21:29
  • $\begingroup$ so set language relations and mathematical logic relations are two different conepts happened to have same name? $\endgroup$ – steakexchange Feb 3 '15 at 21:36

If you are using the set theoretic definition of functions, then functions are relations.

When you are given a signature, you are only given functions symbols, relation symbols and constant symbols together with the "arities" of these symbols. By themselves, these symbols do not mean anything. They are just symbols together with certain numbers attached to them.

When you are given a structure for a certain signature, this structure comes with a domain and an interpretation for each symbol in your signature.

For each n-ary relation symbol, you associate that symbol an n-ary relation on the domain of your structure, which is by definition a subset of the n-fold cartesian product of your domain.

For each constant symbol, you associate that symbol an element of the domain.

For each n-ary function symbol, you associate an n-ary function on the domain of your structure, which by definition is an n+1-ary relation satisfying certain properties. (This actually depends on whether you define an n-ary function to be a subset of the cartesian product of a cartesian product of n-sets and the codomain, or as a subset of a cartesian product of n+1 sets.)

  • $\begingroup$ thank you for the answer, it is a nice summary of key concepts, but my question actually is what is the difference between relations in context of sets and relations in context of FOL? are they the same concept or different? relations in sets don't seem to be same as relations in mathematical logic $\endgroup$ – steakexchange Feb 3 '15 at 21:45
  • 1
    $\begingroup$ The point of this answer is that there is no difference because "relations in context of FOL" simply does not mean anything without the actual set theoretic definition of relation. Whenever you are given a relation symbol, like $<$, whether or not the formula $< (x,y)$ is true is determined by whether or not the 2-tuple $(x,y)$ belongs to the interpretation of the relation symbol $<$, which is a subset of 2-fold cartesian product of your domain. $\endgroup$ – Burak Feb 3 '15 at 21:50
  • 1
    $\begingroup$ her ne kadar yorumlarda tesekkur etmek kurallara aykiri da olsa tesekkur ederim, aydinlandim. $\endgroup$ – steakexchange Feb 3 '15 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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