Math Notes – Theory of Relation Conditions

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 third 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 previous parts.  The theorems on this page are sequenced starting with 1.  Any reference to a theorem in a prior part will be so noted.

The domain of set R with respect to relation r contains all members that map into set R with respect to the relation r.  The condition of set R with respect to relation r contains all members that only map into set R.  The condition is defined as

Definition 1: cond.r.R = dom.r.R – dom.r.~R

The condition of the null set is the null set.

Theorem 1: cond.r.Æ = Æ

The condition of a set equals the domain less the domain of the complement.

Theorem 2: cond.r.R = dom.r - dom.r.~R

The condition of a subset is a subset of the condition.

Theorem 3: R Í Q Þ cond.r.R Í cond.r.Q

The intersection of conditions equals the condition of the intersection.

Theorem 4: cond.r.R Ç cond.r.Q = cond.r.(R Ç Q)

The union of conditions is a subset of the condition of the union.

Theorem 5: cond.r.R È cond.r.Q Í cond.r.(R È Q)

If a relation is also a function, then the union of conditions equals the condition of the union.

Theorem 6: r is a function Þ cond.r.R È cond.r.Q = cond.r.(P È Q)

When the relation r is a function, the domain equals the condition.

Theorem 7: r is a function Þ dom.r.R = cond.r.R

If the domain is disjoint from the domain of the complement, then the domain equals the condition.

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

The identity relation is a function, and the condition is the same as the result.

Theorem 9: Identity, cond.I.R = R

The range of the condition is a subset of the result.

Theorem 10: ran.r.(cond.r.R) Í R

Problems:

Theorem 5 states that the union of conditions is a subset of the condition of the union.  Suppose that the Universal set of discourse is the set of integers and that set

B = {x|1 < x < 6}

Let the relation over B´B  r = {<b,c>|b Î B Ù c Î B Ù c is a factor of b}.

List the members of the following sets:

dom.r.{2}

dom.r.{3}

dom.r.{4}

dom.r.{5}

dom.r.~{2}

dom.r.~{4}

cond.r.{2}

cond.r.{4}

Provide a counter-example that shows

cond.r.(R È Q) Í cond.r.R È cond.r.Q º false

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.