Math Notes – Theory of Relations – Part 1

 

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 first 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.

 

A binary cross-product (A´B) of two sets A and B contains all ordered pairs such that the first element of each ordered pair is in set A, and the second element of each ordered pair is in set B.  Thus:

 

      A´B = {a,b | a Î A Ù b Î B : <a,b>}.

 

A binary cross-product (A´A) over set A contains all ordered pairs such that each element of each ordered pair is in set A.  Thus:

 

      A´A = {a,b | a Î A Ù b Î A : <a,b>}.

 

A relation r (rho) over a cross-product A´B is a subset of A´B.  Thus:

 

      rÍ A´B.

 

The less-than relation < is the set of all ordered pairs <a,b> such that a is less than b.  Let the universe of discourse be the set of integers. The following two statements are equivalent.

 

      <2,3> Î < and 2 < 3.

 

Many investigations of relations explain how two elements are related to each other.  This analysis goes in another direction, and is more concerned with the nature and properties of the relation itself.  Relations are denoted by Greek letters, Sets are denoted by upper case letters, and elements are denoted by lower-case letters. 

 

The domain of a relation contains all the first-elements that make up the relation.  The range of a relation contains all the second-elements that make up the relation.

 

Definition 1. ran.r = {b:B |($a:A |:a r b):b}

Definition 2. dom.r = {a:A |($b:B |:a r b):a}

 

Suppose that the set Q is the subset of the range of a relation.  There is a set P in the domain of the range such that there is an element in Q that is related to each element in P.  Some texts might call P the image of Q. The concept of image is an old one; image theorems are usually related to functions rather than relations.  The theorems in this text are stated in the context of relations and use equational logic as a metaphor.  Otherwise, these are essentially old ideas. 

 

This text defines an image set P as an extension of Definition 1.  Definition 3 defines the image of domain subset P, and definition 4 defines the reverse image of range subset Q.

 

Definition 3.ran.r.P = {b:B |($a:A |:a r b Ù a Î P):b}

Definition 4.dom.r.Q = {a:A |($b:B |:a r b Ù b Î Q):a}

 

The theorems below implicitly assume that there is a relation r that is a subset of the cross-product A´B.  Thus,

 

      rÍ A´B

 

is an implicit assumption in all theorems.

 

The first theorem asserts that the domain of the null set is the null set.  Thus, a requirement for a nonempty domain is a nonempty range.

 

 

Theorem 1: dom.r.Æ = Æ

 

A real-world example of a relation is the sales tax calculation

 

      t = .05×s

 

where t is the tax and s represents the total sales amount.  The set of ordered pairs

 

      r = <s,.05×s>

 

forms a relation between the tax (t = .05×s) and the sale amount (s).  Suppose one wants sales to be large enough so that tax

 

      t > 10.00.

 

One could substitute the equal value for t and solve for s

 

      .05×s > 10.00

      s > 10.00 / .05 = 200.00

 

      s > 200 Þ t > 10

 

‘t > 10.00’ denotes an expression that represents a set of all tax values greater than 10.00.  ‘t > 10.00’ also denotes a subset of ran.r, where r is the sales tax relation defined above.  The expression ‘s > 200.00’ denotes a subset of dom.r.  That is,

 

      ‘s > 200’ = dom.r.’t > 10.00’

 

The following expression is obviously true.

 

      t > 10 Þ t > 5.

 

Similarly

 

      s > 200 Þ s > 100.

 

But

 

s > 100 = dom.r.’t > 5.00’

      s > 200 = dom.r.’t > 10.00’

 

so

dom.r.’t > 10.00’ Þ dom.r.’t > 5.00’

 

The second theorem generalizes the sales tax example, and shows that subset relationships in the range imply the same relationships between the corresponding domain images.

 

Theorem 2: R Í Q Þ dom.r.R Í dom.r.Q

 

Application of set contrapositives produces the following theorem.  The complement of the domain of the complement is an interesting set. 

 

Theorem 3: R Í Q Þ ~dom.r.~R Í ~dom.r.~Q

 

The domain of unions is the union of the domains.

 

Theorem 4: dom.r.(P È Q) = dom.r.P È dom.r.Q

 

The domain of intersections is in the intersection of the domains.

 

Theorem 5: dom.r.(P Ç Q) Í (dom.r.P Ç dom.r.Q)

 

The domain of a set is the same as the domain of the set and the range.

 

Theorem 6: r Í A´B Þ dom.r.R = dom.r.(R Ç B)

 

The domain of a relation is the domain of the range.

 

Theorem 7: r Í A´B Þ dom.r.B = dom.r

 

The domain of any set that contains the range of the relation is the domain of the relation.  Similarly, the domain of the union of a set with its complement is the domain of the relation.

 

Theorem 8: r Í A´B Ù B Í R Þ dom.r.R = dom.r

 

Corollary: dom.r.(R È ~R) = dom.r

 

The domain of a set is in the domain of the relation.

 

Theorem 9: dom.r.R Í dom.r

 

If an ordered pair is a member of a relation, then the first element of the ordered pair is in the domain of the relation. 

 

Theorem 10:  <x,y> ÎrÞ x Î dom.r

 

The following four theorems prove properties of the difference between the domain of result R and the domain of the result’s complement.  Theorem 11 shows that the difference between the domain and the domain of the result’s complement is a subset of the domain of R.

 

Theorem 11: (dom.r - dom.r.~R) Í dom.r.R

 

The domain minus the domain of the result’s complement is also a subset of the domain of the result minus the domain of the result’s complement.

 

Theorem 12: (dom.r - dom.r.~R) Í (dom.r.R – dom.r.~R)

 

The subset relation in the other direction is also true.  The domain of the result minus the domain of the result’s complement is a subset of the domain minus the domain of the result’s complement.

 

Theorem 13: (dom.r.R - dom.r.~R) Í (dom.r – dom.r.~R)

 

Theorem 12 and theorem 13 lead directly to theorem 14.  The two domain differences are equal.

 

Theorem 14: (dom.r.R - dom.r.~R) = (dom.r – dom.r.~R)

 

An apparently obvious relationship between domains occurs when the domain of a result is disjoint from the domain of the complement.  When the domains are disjoint, then the domain minus the domain of the complement equals the domain.

 

Theorem 15: (dom.r.R Ç dom.r.~R = Æ) º

(dom.r.R = dom.r.R – dom.r.~R)

 

 

Problems

 

Let ‘1/x’ be the multiplicative inverse relation.  If a ‘1/x’ b then b = 1/a.

 

Specify following sets.

ran.‘1/x’

dom.‘1/x’

ran.‘1/x’.{0}

dom.’1/x’.(ran.‘1/x’.{0})

 

The domain of image intersections is in the intersection of the domains, but is not necessarily equal to the intersection of the domains.  The following set of ordered pairs forms a simple relation.

 

      r = {<2,1>,<2,3>}

 

Show that the relation r represents a counter-example to the proposal that the sets in Theorem 5 are necessarily equal.

 

 

 

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.