Math Notes – Theory of Relations – Part 2
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 at the second set of relation theorems. The method of proofs is based on a style developed in A Logical Approach to Discrete Math, though the approach used here is quite different from the set theorems in Gries’ text. I would appreciate any comments, suggestions, and feedback as related to the proofs.
This page is a continuation of part 1. The theorems on this page are sequenced starting with 1. Any reference to a part-1 theorem will be so noted.
Every relation has a corresponding inverse relation. If <a,b> is a member of a relation, then <b,a> is a member of the inverse relation. The inverse relation is denoted by a superscript –1. If r is a relation, then r-1 is the inverse of r.
Definition 1: (inverse) <a,b> Î r º <b,a> Î r-1
The inverse relation is important in showing the relationship between the range and the domain, as shown in the following theorems.
The range of a relation is the domain of the inverse. Theorem 1 may be used to derive range theorems from domain theorems, and the properties of a range are similar to the properties of a domain.
Theorem 1: ran.r.P = dom.(r-1).P
Similarly, the domain of a relation is the range of the inverse.
Theorem 2: ran.(r-1).P = dom.(r).P
The inverse of the inverse of the domain of a relation is also the domain of the relation.
Theorem 3: dom.((r-1)-1).P = dom.r.P
Similarly, the inverse of the inverse of the range of a relation is also the range of the relation.
Theorem 4: ran.((r-1)-1).P = ran.r.P
The following theorems apply to ranges and are similar to corresponding domain theorems.
The range of the null set is the null set. Thus, a requirement for a nonempty range is a nonempty domain.
Theorem 5: ran.r.Æ = Æ
Subset relationships in the domain imply the same relationships between the corresponding range images.
Theorem 6: P Í Q Þ ran.r.P Í ran.r.Q
Application of set contrapositives produces the following theorem. The complement of the range of the complement is an interesting set.
Theorem 7: P Í Q Þ ~ran.r.~P Í ~ran.r.~Q
The range of unions is the union of the ranges.
Theorem 8: ran.r.(P È Q) = ran.r.P È ran.r.Q
The range of intersections is in the intersection of the ranges.
Theorem 9: ran.r.(P Ç Q) Í (ran.r.P Ç ran.r.Q)
The range of a set is the same as the range of the set and the domain.
Theorem 10: r Í A´B Þ ran.r.R = ran.r.(R Ç A)
The range of a relation is the range of the domain.
Theorem 11: r Í A´B Þ ran.r.A = ran.r
Corollary: r Í A´B Þ ran.r = dom.r-1
The range of any set that contains the domain of the relation is the range of the relation. Similarly, the range of the union of a set with its complement is the range of the relation.
Theorem 12: r Í A´B Ù A Í P Þ ran.r.P = ran.r
Corollary: r Í A´B Þ ran.r.(R È ~R) = ran.r
The relationship between the elements of the ordered pair <x,y> can be expressed as an expression involving the range. The ordered pair <x,y> is equivalent to having the element y in the range of the set {x}.
Theorem 13: y Î ran.r.{x} º x r y
If P is a subset of the domain’s complement, then the range of P is empty.
Theorem 14: P Í ~dom.rÞ ran.r.P = Æ
If P is a subset of the domain, then P is also a subset of the domain of its range.
Theorem 15: P Í dom.r Þ P Í dom.r.(ran.r.P)
Similarly, if P is a subset of the range, then P is also a subset of the range of its domain.
Theorem 16: P Í ran.r Þ P Í ran.r.(dom.r.P)
Problems:
Let A = {1,2,3}, and let > be a relation where a > b means a is greater than b.
Derive all the members of the set >.
Derive the set dom.>.{3}.
Derive the set cond.>.{3}.
Derive the set ran.>.(cond.>.{3}.
Theorem 15 requires that P be a subset of the domain. Suppose that the relation is the operation: y/x.
Describe the set representing dom.(y/x).(ran.(y/x).{0}. Where {0} is the singleton set containing the number zero.
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.