2
$\begingroup$

In Elementary Set Theory, a profound understanding of compositums and how they are constructed is essential for further algebraic analisys (for rings, grupoids, groups etc.). In my textbook, the definition of the compositum of certain relations $T$ and $R$ is written as such:

$$T \circ R := \{ (x,y); \; (\exists u)(xRu \wedge uTy) \}.$$

This seems counter-intuitive to me. If anythingl I always (apparently wrongly) considered

$$T \circ R = \{ (x,y); \; (\exists u)(xTu \wedge uRy) \}$$

to be the right way to go about it. It is apparent that I am missing an essential idea behind the "switched order" of $T$ and $R$ in the definition of a compositum. To me, the example I gave would suffice on the surface, as all we need for a compositum is a "bridge" $u$ between elements $x$ and $y$. However, my presumption is clearly false, as compositum isn't a commutative relation. Write

$$T \circ R = \{ (x,y); \; (\exists u)(xRu \wedge uTy) \}$$

$$R \circ T = \{ (x,y); \; (\exists u)(xTu \wedge uRy) \}$$

therefore

$$T \circ R \neq R \circ T.$$

The author reaffirms this definition with an example:

$$R = \{ (1,3), (2,3) \} \quad \text{and} \quad T = \{ (3,1) \}.$$

By definition, we get

$$T \circ R = \{ (1,1), (2,1) \} \quad \text{and} \quad R \circ T = \{ (3,3) \}.$$

I would really appreciate if someone gave me an introspect into the underlying logic behind this definition.

$\endgroup$
  • 1
    $\begingroup$ This (somewhat) makes sense only when you consider functions instead of relations. Then we have (or agree to want) that the function $f\circ g$ is given by mapping $x\mapsto f(g(x))$, in other words we apply $f$ after $g$, not first $f$ then $g$. And of course we also want to have the convention that the pairs making up the graph of our function look like $(x,f(x))$, not $(f(x),x)$. $\endgroup$ – Hagen von Eitzen Oct 16 '17 at 16:16
  • $\begingroup$ +HagenVonEitzen The author of my textbook used a pedagogic method when all of the definitions are built from the ground up (so first are the ZFC axioms, then algebraic structures etc.). The term "function" hasn't even been defined yet. The chapter of the textbook is titled 'Relations' and explores the concepts of writing all relations as sets. I as somewhat confused. $\endgroup$ – Gregor Perčič Oct 16 '17 at 16:19
  • 1
    $\begingroup$ Some authors use the left-to-right order for composition of relations (i.e., consistent with what you expected). Some authors (e.g. the author of your text) choose the right-to-left order, so as to be consistent with the standard order for composition of functions. The choice is arbitrary, and has no theoretical impact. As long as you are aware of the choice made in the context of a given course, it shouldn't be an issue. $\endgroup$ – quasi Oct 16 '17 at 16:32
  • $\begingroup$ +quasi Thank you so much for a comprehensive yet short answer! Sadly I can't give you an upvote and a tick since you've answered in a comment (conside writing a full answer). $\endgroup$ – Gregor Perčič Oct 16 '17 at 16:55
1
$\begingroup$

You want the composition of functions to be a special case of the composition of relations. Functions are usually written with the input on the left and the output on the right, so for example, the function $f(x) = 2x$ would be written:

$$\left\{\begin{array} {c} (1, 2) \\ (2, 4) \\ (3, 6) \\ \vdots \end{array}\right\}$$

And function composition is defined as $(F \circ G)(x) = F(G(x))$. So combining those 2 conventions, if you have $(x, y)$ such that $y = (F \circ G)(x) = F(G(x))$, then it must follow that $\exists u~.~ y = F(u) \land u = G(x)$, or written as a relation, $\exists u~.~ uFy \land xGu$.

$\endgroup$
1
$\begingroup$

Some authors use the left-to-right order for composition of relations (i.e., consistent with what you expected).

Some authors (e.g., the author of your text) choose the right-to-left order, so as to be consistent with the standard order for composition of functions.

The choice is arbitrary, and has no theoretical impact. As long as you are aware of the choice made in the context of a given course, it shouldn't be an issue.

$\endgroup$

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.