Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So let us say that for whatever reasons, we are not allowed to use function symbols in first-order logic. Then can we define and use a function only by relations?

share|improve this question
    
I'm sure you can define them as relations. But from what I've gathered the reason to differentiate between the two is to introduce functions as terms and relations as formulas which help us incredibly in the formulation of our structures/theories. So in First Order Logic I don't think so. But in general many teachers use Relations to define what a function actually is. –  Ishfaaq Aug 8 at 3:32

4 Answers 4

Yes, you just have to add an axiom stating that the relation is a function: $$\forall x\forall y\forall z(R(x,y)\land R(x,z)\rightarrow y=z)$$

And you may want to require that the domain is the entire universe.

share|improve this answer

Great Question. Yes! In fact, all functions are relations: the set of all functions is a subset of the set of all relations.

Think about it: take two sets $A = \{a,b,c\},B = \{1,2,3\}$. Create a function between them. Remember the formal definition of a function: a function is just a set of ordered pairs $(x,y)$, for which we like to say that $x \in X$ is mapped to $y \in Y$. So our function between the two sets $A$ and $B$ will be a subset of the Cartesian product $A \times B$, for example: $f = \{(a,2),(c,1)\}$.

Does that sound familiar to you? That's right. A relation between two sets $A,B$ is always just a subset of the Cartesian product $A \times B$. (Note that here, a relation is not the same as an equivalence relation, which are much more strict, and you have probably just heard about.)

So far it sounds as if they're the same. So what's the big difference? Well, remember that a function maps each input to just one output. You cannot have $f(x) = 5$ and $f(x) = 3$, because then $5=3$. You know this. So for your set that represents a function --- take our example from earlier, $f = \{(a,2),(c,1)\}$ --- we have that for every element of $f$ (an ordered pair $(x,y)$), the first coordinate in the tuple (in this example, that's $x$) is unique. That means you cannot have a function like $g = \{(a,2),(c,1),(a,3)\}$ because $a$ appears twice as the first coordinate of a tuple --- it would mean that $g(a) = 2$ and $g(a)=3$, and we can't have that.

And that's the condition that makes the functions a subset of the relations. In a relation, the first coordinate of the tuple does not have to be unique. The relation $R = \{(a,2),(c,1),(a,3)\}$ is perfectly valid. But that set is not a valid function. So even though every function is a relation, not every relation is a function.

share|improve this answer

Yes, a function from $A$ to $B$ is a relation on A and B such that any element x of the domain cannot be related to two different element $y$ and $z$ of $B$ . Also every element of the domain $A$ should be related to some element of the target $B$.

In one sentence,every element of the domain should be related exactly one element of the target.

share|improve this answer

Usually functions are defined in the language of set theory. Here is a possible definition using only FOL:

Let $D$ and $C$ be unary predicates. Let $F$ by a binary predicate.

$F$ is said to be a functional relation with domain predicate $D$ and codomain predicate $C$ if and only if:

  1. $\forall x,y:[F(x,y)\implies D(x)\land C(y)]$

  2. $\forall x:[D(x)\implies \exists y:[F(x,y)]$

  3. $\forall x,y_1,y_2:[F(x,y_1)\land F(x,y_2)\implies y_1=y_2]$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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