Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I read that all binary relations are associative. i.e (p.q).r = p.(q.r). However, I was curious that does this hold if p,q, and r are ternary relationships. I tried several examples, such as the one below, but could not prove that ternary relationaships are NOT associate. So, are they associative or not

p = {(a,b,c) , (f,o,x)}
q = { (f,d,e), (x,o,c) }
r = { (e,t,o), (c,t,s)}

The output for (p.q).r and p.(q.r) in both cases is {(f,o,o,t,s)}

share|cite|improve this question
What do you mean by "binary relation"? – wj32 Nov 2 '12 at 12:24
I assume you're talking of composition of relations. I'm familiar with the binary case. How exactly are you defining the composition of ternary relations? – Hurkyl Nov 2 '12 at 12:24
It is far not true that "all binary relations are associative". Probably it was meant: "in the following, we assume that all binary operations that will occur, is associative." – Berci Nov 2 '12 at 12:25
I know this is irrelevant to your question, but what do you mean that all binary relations are associative? Do you mean the composition of relations like $p.q= \left\{\left(x,y\right)|\exists z, \left(x, z\right) \in p , \left(z,y \right) \in q \right\}$? If yes, I don't know of any obvious analogue for composing ternary relations. – Hooman Nov 2 '12 at 12:26
Yes, how do yoe mean the composition of ternary relations? – Berci Nov 2 '12 at 12:26

If you want to talk about associativity, then probably what you are interested in is binary operators rather than binary relations.

Recall that a binary operator is something that takes in two inputs, and gives out a single output. Note that this must all be done with a particular set in mind.

For example, if your set is the natural numbers $\mathbb{N} = \{0, 1, 2, 3, \ldots\}$, then addition, $+$, is a binary operator: given two natural numbers, $m$ and $n$, their sum, $m+n$, is also a natural number.

It is not true, however, that all binary operators are associative. For example, subtraction is a binary operator on the integers, but it is not associative: $10-(9-8) \neq (10-9)-8$, since the left hand side is $9$ and the right hand side is $-7$ (and clearly $9 \neq -7$).

Similarly, one can define a ternary operator that takes in three inputs, and gives out a single output. As with binary operators, there is no guarantee that a ternary operator will be associative.

If the above does not answer your question and, in fact, you have other restrictions in mind when you refer to "ternary relationships," please make them explicit.

share|cite|improve this answer

For ternary relations, you can either use indexed or named perspective. Indexed perspective is the standard math where attributes are indexed with consecutive integer numbers. Unfortunately, it is not obvious what is the analog of composition operation (aka relative multiplication). However, one logic application -- namely, database theory -- has developed alternative, quite compelling perspective. There each attribute is equipped with name. Relational join projected to the set of distinct relation attributes is generalization from binary case. The associativity counterexample is the following:

z = [p  r  s]
     0  0  s
     0  1  s
     0  2  s
     1  2  l
     2  0  s
     2  2  s
     3  2  l

y = [p  q  s]
     0  c  s
     1  c  l
     2  b  s
     3  a  l

x = [p  q  r]
     0  a  0
     0  a  1
     1  c  0
     1  c  1
     2  a  0

Intermediate evaluations:

x;y=[r  s]
     0  l
     1  l


y;z=[q  r]
     a  2
     b  0
     b  2
     c  0
     c  1
     c  2


Yes, composition of ternary relations in database theory is not closed (it doesn't produce a ternary relation). Relational algebra is algebra of relations with mixed dimensions.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.