Math Notes – Theory of Relation Compositions
The notes on this page derive specific properties of mathematical relations; the notes are not intended as a full description of relation theory. Any of the text references below should provide good background for the concepts on this page.
The purpose of these notes is descriptive, so the proofs are omitted. My version of the proofs may be found in the companion to this page. The method of proofs is based on a style developed in A Logical Approach to Discrete Math, though the approach used here varies from the set theorems in Gries’ text. I would appreciate any comments, suggestions, and feedback as related to the proofs.
This page builds on the other pages related to relations and the concept of condition. The theorems on this page are sequenced starting with 1. Any reference to a theorem developed on another page is noted with a reference to the other page.
Suppose that r and s are two relations in A´B. If the intesection of ran.r and dom.s is nonempty then the composition of r and s forms a new relation r·s. The definition of r·s is
Definition 1: r·s = {r,s | ($y|:<r,y> ÎrÙ <y,s> Îs):<r,s>}
The composition definition describes a set operator. The composition operator transforms two relations into a third relation that contains the composed ordered pairs. The composition operator is represented by a large dot ‘·’. The composition of two relations r and s form a third relation. the third relation may be denoted by the expression ‘r·s’.
The composition of two relatiions is a relation, so quantifying expressions involve two quantifying variables. Theorems involving domains and ranges often use single-variable quantifying statements. The first theorem makes the application of the composition definition easier by denoting an expression equivalent to a specific ordered pair in the composition set.
Theorem 1: a r·s b º ($y|:a r y Ù y s b)
The domain of composed relations may be described by the domains of each relation. The domain of a composition is the domain of the domain.
Theorem 2: dom.(r · s).R = dom.r.(dom.s.R)
Theorem 3: dom.(r · s) = dom.r.(dom.s)
The condition may be expressed as an expression of domains, so the condition of composed relations may be expressed as an expression of domains. The resulting expression follows directly from the second and third theorems.
Theorem 4: cond.(r · s).R = dom.r.(dom.s.R) - dom.r.(dom.s.~R)
The substitution of equivalent domain expressions in a condition expression leads to the relationship between the condition of a condition versus the condition of a composition.
Theorem 5: cond.r.(cond.s.R) Í cond.(r · s).R
If the sequence of two relations has the characteristic that the domain intersected with the complement is empty, then the condition of the composition is a subset of the condition of the condition.
Theorem 6: (dom.s.R Ç dom.s.~R = Æ Ù
dom.r.(dom.s.R) Ç dom.r.(~dom.s.R) = Æ) Þ
cond.(r · s).R Í cond.r.(cond.s.R)
If the sequence of two relations has the characteristic that the domain intersected with the complement is empty, then the condition of the composition equals the condition of the condition.
Corollary to Theorem 6: (dom.s.R Ç dom.s.~R = Æ Ù
dom.r.(dom.s.R) Ç dom.r.(~dom.s.R) = Æ) Þ
cond.(r · s).R = cond.r.(cond.s.R)
Theorem 7: r is a function Ù s is a function Þ
cond.r.(cond.s.R) = cond.(r · s).R
When two relations are functions, then the condition of the condition equals the composition of the two relations.
Problems:
Suppose that the set of universal discourse is
U = {a, b, c, d, e, f, g, h, i, j, k}
The following relations are used in this problem:
r = {x,y | x ‘is married to’ y :<x,y>}
s = {x,y | x ‘has a sister named’ y :<x,y>}
t = {x,y | x ‘has a brother named’ y :<x,y>}
The following facts are known:
1. the married couples are: a and c; f and h; and d and k.
2. a has two sisters: b and d.
3. c has two sisters: f and i.
4. k has one sister, e.
5. a has one brother, g.
6. h has two brothers: j and k.
7. a is a male.
The relation r = {<a,c>,<c,a>,<f,h>,<h,f>,<d,k>,<k,d>}
1. Write all the members of the relation s.
2. Write all the members of the relation t.
3. Write the members of the composite r·s.
4. Write the members of the composite r·t.
5. Write the members of the set dom.(r·s).{i}.
6. Write the members of the set cond.(r·s).{e}.
7. Write the members of the set cond.(r·s).{i}.
8. Write the members of the set cond.(r·s).{g}.
References:
Fejer, Peter and Simovici, Dan A., 1991, Mathematical Foundations of Computer Science, New York, NY: Springer-Verlag
Ganong, Rick 1999, Course notes and comments from M1090 and M2090 math and logic courses, http://www.math.yorku.ca/Who/Faculty/Ganong
Gries, David and Schneider, Fred B., 1993, A Logical Approach to Discrete Math, New York, NY: Springer-Verlag
Hu Sze-Tsen, 1963, Elements of Modern Algebra, San Francisco: Holden-Day, Inc.