1

I'm a bit stuck proving questions such as "$S\circ R$ is a function if $R$ and $S$ are both functions." Is this a case of stating the definition of a composite function?

Thanks.

Would the following proof be correct?

$$ \forall x \in X. \exists y \in Y. (x,y)\in R $$

$$ \forall y \in Y. \exists z\in Z. (y,z)\in S $$

$$ \therefore \forall x \in X. \exists z \in Z. (x,z) \in S\circ R $$

user2979879
  • 55

2 Answers2

1

A binary relation $R\subset X\times Y$ can be classified as a function if it suffices:

$\forall x\in X\;\exists!y\in Y\;\left(x,y\right)\in R$

(in words: for every $x\in X$ there is exactly one $y\in Y$ such that $\left(x,y\right)\in R$).

This unique $y$ is denoted as $R(y)$. Now let $S\subset Y\times Z$ be a binary relation and define $S\circ R$ by:

$\left(x,z\right)\in S\circ R$ iff $\left(x,y\right)\in R\wedge\left(y,z\right)\in S$ for some $y\in Y$.

It can be proved that $S\circ R$ is a function if $S$ and $R$ are functions. Starting with $x\in X$ there is a unique $y\in Y$ with $\left(x,y\right)\in R$ (this because $R$ is a function). For this unique $y$ there is a unique $z\in Z$ with $\left(y,z\right)\in S$ (this because $S$ is a function). Then $\left(x,z\right)\in S\circ R$ and $z\in Z$ is unique. Here $S\circ R$ is the composite function and $z=S\circ R(x)=S(R(x))=S(y)$.

Warning1: Sometimes $S\circ R$ is denoted as $R\circ S$

Warning2: Actually functions are often defined as triples $f=\left(X,G,Y\right)$ where $G\subset X\times Y$ is a binary relation having the mentioned property. Here $X$ is the domain, $Y$ is the codomain and $G$ is the graph of $f$.

drhab
  • 151,093
  • Would this proof be correct?

    $$ \forall x \in X. \exists y \in Y. (x,y)\in R
    $$

    $$ \forall y \in Y. \exists z\in Z. (y,z)\in S $$

    $$ \therefore \forall x \in X. \exists z \in Z. (x,z) \in S\circ R

    $$

     – user2979879 Jan 15 '14 at 14:20
  • That is correct reasoning. But what exactly are you trying to prove here? You are not proving that $S\circ R$ is a function here, because the fact that $z$ is unique is not proved. $\exists$ should be changed into $\exists!$ for that. – drhab Jan 15 '14 at 15:12
  • I am trying to prove S∘R is a function. How would I prove that z is unique? – user2979879 Jan 15 '14 at 15:16
  • As I said: $\exists$ should be changed into $\exists!$ In words: for every $x\in X$ there is a unique $y\in Y$ s.t..... and for every $y\in Y$ there is a unique $z\in Z$ s.t.... so for every $x\in X$ there is a unique $z\in Z$ s.t.... – drhab Jan 15 '14 at 15:20
  • I see, I wasn't aware of the there exists uniquely notation. It makes more sense now. Thank you very much for your help – user2979879 Jan 15 '14 at 15:25
0

I assume that here $R$ and $S$ are binary relations (why else would anyone use uppercase variable names for functions? ;) ). So you would have to look up the definition of a binary relation, $S\circ R$ for binary relations $R$ and $S$, and the definition of a function as a special kind of binary relation.

Of course, I only guessed the context, it may be different.

Carsten S
  • 8,726