4

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?

tim_xyz
  • 243
  • 1
    You should look up the exactly definition of a function first. You may find it in several books, such as How to Prove It – Eric Sep 08 '16 at 05:27
  • How to Prove It is a nice book. Enjoy it. – Rafael Sep 08 '16 at 05:32
  • Note that your argument would also mean that "give a relation $xRy$, we can compute a set of $(x,y)$ ..." – Hagen von Eitzen Sep 08 '16 at 05:32
  • 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. – fleablood Sep 08 '16 at 05:57

4 Answers4

4

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.

Pratyush Rathore
  • 341
  • 1
  • 5
2

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.

Alexis Olson
  • 5,414
0

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.

celtschk
  • 43,384
-1

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$.

ninjaaa
  • 440