Math Notes – Theory of Relations – Part 3
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 part 2. The theorems on this page are sequenced starting with 1. Any reference to a part-1 theorem or a part-2 theorem will be so noted.
A set describes a collection of members. A predicate contains logical and nonlogical variables that evaluate to true or false. The set P describes a subset of the universal set U by limiting the members of set P to those points in the state space that satisfy the expression P. Thus
P = {x|P:x}.
The first occurrence of P denotes a set. The second occurrence of P is an expression denoting the constraint that determines membership to set P.
The relationship between a set and the predicate describing the set is
x Î {x|P:x} º P.
The set expression that denotes the current state as a member of set P is equivalent to the predicate expression that is true for the current state.
The expression P may be a predicate or a set. The context in which the expression P is used should determine whether the usage refers to an expression or a set.
There is a correspondence between set operators and logical operators.
Implication (Þ) corresponds to subset (Í).
Logical equivalence (º) corresponds to set equality (=).
Logical not (Ø) corresponds to set complement (~).
Logical conjunction (Ù) corresponds to set intersection (Ç).
Logical disjunction (Ú) corresponds to set union (È).
Logical constant true corresponds to the universal set of discourse U.
Logical constant false corresponds to the null set (Æ).
All subset operations have corresponding logical implications, but some logical implications do not have corresponding subset operations. Suppose that A is the set of all apple packages sold where the number of apples sold is 10, and that B is the set of all cash transactions where the amount is $5.00. If the price of apples is $0.50 per apple, then A Þ B. If the universal set of discourse is the set of all sales transactions where one property is item sold and another property is amount of sale, then the subset operation A Í B is appropriate. If the set interpretation has sale item as an element distinct from sale price, then the set operation doesn’t make sense.
Under the second interpretation of the sale of apples where the sale item is distinct from the sale price, there is a relationship between the sale item and the sale price.
sale price = $0.50 × (number of items sold)
The theorems on this page describe a generalization of the implication/subset correspondence that takes into consideration two sets whose members are related in some way.
Implication theorems
A relation r describes how members of a domain set correspond to members of a range set. Let P be a subset of the domain. The range or image of P in the range is ran.r.P. The members of ran.r.P correspond to the members of set P according to the rules of the relation r and defined in relation concepts part 1.
The first theorem applies to the range of P, ran.r.P. For every element in P and for every element b associated with element a by relation r, b is an element of the range or P ran.r.P
Theorem 1: Given P Ù r, ("a,b|arb Ù a Î P: b Î ran.r.P)
The second theorem is a restatement of the first theorem using logical operators and introduces the implication operator into the expression.
Theorem 2: Given P Ù r, ("a,b|:r Ù P Þ ran.r.P)
Theorem 2 shows that a subset in the domain of a relation implies its image in the range of the relation. The next three theorems describe how subsets in the range that contain the image are also implied by the subset in the domain. Theorem 5 connects the relation concept of implication to the subset concept of implication.
Theorem 3: ran.r.P Í R Þ ("a,b|:arb Ù aÎP Þ bÎR)
Theorem 4: ("a,b|:arb Ù a Î P Þ b Î R)Þ ran.r.P Í R
Theorem 5: ("a,b|:arb Ù a Î P Þ b Î R) º ran.r.P Í R
Corollary: ("a,b|aÎP: arb Þ b Î R) º ran.r.P Í R
The next theorem is a restatement of the implication theorem using logical operators.
Theorem 6: ("a,b|:r Ù P Þ R)º ran.r.P Í R
Theorem 7 derives the subset model of implication from the relation model. The derivation uses the identity relation in the relation model of the implication.
Theorem 7: ("a|:P Þ R)ºP Í R
Problems:
Let the universal set of discourse U be the set of rectangles with dimensions x and y. The area of each rectangle is the product of x and y.
Let P be the set of rectangles with area greater than 100.
A relation may be formed by a systematic change to each of the rectangles. Suppose that the x dimension of each rectangle is increased by 2 units forming the result set R of rectangles. There is a relation r between set P and set R. Suppose <p,r> Îr. The element p Î P and the element r Î R. The x dimension of a rectangle in set R is 2 units longer than the associated rectangle in set P. The set R = ran.r.P. The set P and the relation r together imply the set R.
Show that set P is not a subset of set R by identifying a member of P that is not in R.
How much must the x dimension increase so that the area increases by 25 square units?
What is the minimum length of the y dimension so that the area increases by at least 60 square units after the x dimension increases by 5 units.
Let s be the relation -- having greater area. For each member of set P, Q contains all rectangles satisfying relation s. Therefore, if rectangle q has an area greater than a rectangle in set P, then q Î Q.
Show that ran.r.P Í Q.
Show that set P and relation r together imply set Q.
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.