0

We denote the composite of relation R and relation S by $S \circ R$.

Since the order matters, meaning composite of R and S is not composite of S and R. I am trying to understand why the denotation of composite of R and S puts S before R, which is unintuitive for me.

Can anyone help me understand this? Thanks

peizhao
  • 103

1 Answers1

4

It's in order to maintain consistency with function composition and application. For functions $g=S, f=R$, the notation for composition of relations $S, R$ should be the same as that of composition of $g,f$: $(g\circ f)(x) = g(f(x))$.

If composition were defined so that the first function $f$ applied (or relation $R$) appears "leftmost", then we would want to (and have to) write function application on the right if we wanted the order to look the same in both composition and application. Otherwise, the orders are different: suppose $|$ denotes this 'reversed' composition, first $R$ then $S$: $R|S = \{(x,z)\mid \exists y (xRy, ySz)\}$. Then, somewhat unintuitively, $(R|S)(x) = S(R(x))$.

Note that historically, relation composition has also been defined as in the above paragraph, with that very symbol $|$, and function application has been (and in some subjects is currently) written on the right. These conventions are in use within particular areas of mathematics (group actions, for example; other areas of algebra; some presentations of category are a few that come to mind). Function application on the right looks better (imho) and is probably more common without parentheses, or with parentheses around both function and argument(s) rather than around just the argument(s): compare $x\sigma, x\sigma\tau$, or $(x\sigma), (x\sigma)\tau, (x\sigma\tau)$, and so on, with $(x)\sigma, ((x)\sigma)\tau$.

In mainstream presentations of, say, set theory, such as you'd find in a "Chapter 0", these forms are less (and less) common. Example: Quine's book Set Theory and Its Logic gets very worked up on the subject of the proper order for writing composition: he favors the $R|S$ order, referring to it as "my way, Schroeder's way" (Schroeder being the inventor of 'relational algebra', and as of Schroeder-Bernstein Theorem fame).

BrianO
  • 16,579
  • I thought there were still many algebraists out there who write functions on the right. Using ";" for what you call "reversed" relational composition works out very nicely in many computer science contexts. – Rob Arthan Feb 03 '16 at 00:37
  • @RobArthan True. I replaced my last sentence with a few more which hopefully are more specific. Originally I was thinking more about what you're likely to find in a "Chapter 0", or examples such as Quine's, as cited in the answer. – BrianO Feb 03 '16 at 01:28
  • @BrianO Your explanation is quite intelligible to me. I understand that relations are a generalizations of functions; and composite of functions is denoted that way; for consistency, composite of relation should be that way, too. – peizhao Feb 03 '16 at 13:59
  • The theory of modules over a non-commutative ring is an obvious example where it is vital to be able to work with both conventions. if the non-commutative ring is a ring of matrices, then we are just talking about whether to represent vectors as row vectors or column vectors. If "mainstream presentations" are encouraging a bias towards functions on the left, then those presentations are encouraging a decrease in mathematical maturity: a competent mathematician should be able to work with either convention (or both). – Rob Arthan Feb 04 '16 at 23:19