4
$\begingroup$

Is a function a "special kind of relation", or, does it "describe a specific relation"?

My text on discrete mathematics explains:

A relation is a subset of a Cartesian product and a function is a special kind of relation.

But it would make more sense to me if a function described a relation as a subset of the Cartesian product.

My thoughts being:
Given a function, f(x) = y, we can compute a set of (x,y) coordinates within the Cartesian plain. And this set of coordinates would be the relation that is the subset of the Cartesian product.

Am I confused? Could anyone help explain how a function IS a relation?

$\endgroup$
  • 1
    $\begingroup$ You should look up the exactly definition of a function first. You may find it in several books, such as How to Prove It $\endgroup$ – Eric Sep 8 '16 at 5:27
  • $\begingroup$ How to Prove It is a nice book. Enjoy it. $\endgroup$ – Rafael Holanda Sep 8 '16 at 5:32
  • $\begingroup$ Note that your argument would also mean that "give a relation $xRy$, we can compute a set of $(x,y)$ ..." $\endgroup$ – Hagen von Eitzen Sep 8 '16 at 5:32
  • $\begingroup$ But there are "more" relations than there are functions. Take the relation "have a prime factor in common". Than 6R2, 6R4, 6R8 etc. This can not be a function as ^R? has many values, not just one. take the function f(x) = 2x. then we can create a relation 2R4, 3R6, 4R8, etc. So a function is a special kind of relation but not all relations are functions. $\endgroup$ – fleablood Sep 8 '16 at 5:57
2
$\begingroup$

A function is a specific kind of relation.

The best way to understand this is with the help of an example. So, let us take a couple of sets - set $A$ = {1, 2, 3} and set $B$ = {$a$, $b$, $c$}. Thus the set $A \times B$ will have 9 elements.

We can choose $2^9 = 512$ different subsets of $A \times B$. Each of this subset is a relation between $A$ and $B$. So, $\phi$ is a relation, {$(1, a), (1, c), (2, b)$} is also a relation. $A$ is called the domain and $B$ is called the co-domain.

A function is also a subset of $A \times B$ (hence a relation), but it has constraints. For every element in set $A$, there should be exactly one element in set $B$. More concretely, for every element $x$ in set A, there is exactly one $(x, y)$ in $f$ for some $y \epsilon B$

For example, {$(1, a), (2, b), (3, b)$} is a function, but {$(1, a), (2, b)$} is not because there is no entry of the form (3, *). Also, {$(1, a), (1, b), (3, b), (2, b)$} is also not a function because 1 has two values it is mapping to.

$\endgroup$
1
$\begingroup$

A function is a binary relation where the first value of the pair is unique.

If $A$ and $B$ are sets, then a binary relation $R$ is just a collection of pairs $(a,b) \in A \times B$. A function is a special kind of relation where given any $a \in A$ there is only one $b \in B$ such that $(a,b)$ is $R$. That is, both $(a,b_1)$ and $(a,b_2)$ cannot be in $R$ unless $b_1 = b_2$.

For a function $f : A \to B$, we can express $f$ as the collection of elements $(a,b) \in A \times B$ where $b = f(a)$. In set builder notation,

$$f = \{(a,f(a)) : a \in A,\ f(a) \in B\}.$$

Since any subset of $A \times B$ is a relation from $A$ to $B$, a function is certainly a relation.

$\endgroup$
0
$\begingroup$

Think of the relation "is less than" in $\{1,2,3\}^2$. That relation is $\mathrm{Less}=\{(1,2),(1,3),(2,3)\}$, however you normally will not write $(x,y)\in\mathrm{Less}$, but you will write $x<y$. You certainly have no problem with saying "$x<y$ is a relation". And of course that is true not only for $x<y$, but also for other relations like $x\le y$, $x<y^2$, $x=y$, or, for that matter, $f(x)=y$.

So we see, $f(x)=y$ is a relation. But as you correctly said, $f(x)=y$ is a function. So a function quite obviously is a relation.

It is, however, a very special relation; which is why the notation $f(x)$ makes sense: For any $x\in A$ there's exactly one $y\in B$ so that $(x,y)\in f$. That is, you can read "$f(x)$ as meaning "The unique $y$ such that $(x,y)\in f$", just as you can read $xRy$ as "$(x,y)\in R$". Note that this also means that in principle, $xfy$ would also be a meaningful way to write $f(x)=y$, although that notation is, well, extremely unusual.

$\endgroup$
-1
$\begingroup$

A function (from set $A$ to set $B$) is a relaction of special kind in which $(x,y_1)=(x,y_2) \Rightarrow y_1=y_2$ for every $x \in A, y_1,y_2 \in B$.

$\endgroup$
  • $\begingroup$ That notation isn't correct. If (x,y) is a pair that is true for all relations. $\endgroup$ – Q the Platypus Sep 8 '16 at 5:36

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.