Math Notes – Theory of Relations – Part 4
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 fourth set of relation theorems.
This page is a continuation of part 3. The theorems on this page are sequenced starting with 1. Any reference to a part-1, part-2, etc. theorem will be so noted.
A function is a relation relation in which the second element of every ordered pair is determined by first element. That is, for every ordered pair each first element has a unique second element.
Definition 1: A relation r is a function º
("b,c,c’ | b r c Ù b r c’ : c = c’)
The notation used for functions on this page is similar to the notation used for relations. Thus
b f c
is a function; where b is a member of the domain, and c is a member of the range.
An example of the function ‘2x + 5’ is
x=3 ‘2x + 5’ f=11
One would describe the function expression as: for x=3 the expression ‘2x +5’ has the value f=11.
‘x=3’ describes a point in the domain where the variable x has the value of 3. ‘f=11’ describes a point in the range where the variable f has the value 11. Other variables in the domain and range are not affected by the function, so they are not listed.
The properties of a function impose certain properties on the function’s range. The first property helps to prove the second. The first property describes the obvious property that having an element in the range is equivalent to having an ordered pair in the relation.
Theorem 1: s Î ran.r.{x} º x r s
The second property uses singleton sets as a metaphor to describe the basic property of functions. When a relation is a function, The image of each singleton set in the domain is also a singleton set.
Theorem 2: r is a function Ù ran.r.{x} ¹ Æ Þ
ran.r.{x} is a singleton set
Theorem 3: r is a function Þ dom.r.P Ç dom.r.Q Í dom.r.(P Ç Q)
The third theorem, when combined with a basic property of domains shows leads to the fourth theorem. The intersection of domains equals the domain of the intersection.
Theorem 4: r is a function Þ dom.r.P Ç dom.r.Q = dom.r.(P Ç Q)
When the relation r is a function, the range of the domain is a subset of the result.
Theorem 5: r is a function Þ ran.r.(dom.r.R) Í R
It follows that when the relation is a function and the result is in the range of the relation, then the range of the domain equals the result.
Theorem 6: r is a function Ù R Í ran.r Þ ran.r.(dom.r.R) = R
Theorems 7 through 10 are related forms that apply to relations that are functions. In a function, the domain of a set is disjoint from the domain of the set’s complement.
Theorem 7: r is a function Þ dom.r.R Ç dom.r.~R = Æ
In a function, the domain of a set is a subset of the complement of the complement’s domain.
Theorem 8: r is a function Þdom.r.R Í ~dom.r.~R
In a function, the domain of the complement is a subset of the domain’s complement.
Theorem 9: r is a function Þdom.r.~R Í ~dom.r.R
In a function, the domain equals the domain minus the domain of the complement.
Theorem 10: r is a function Þ dom.r.R = dom.r.R - dom.r.~R
Problems:
Let the universal set of discourse be the set of integers, and let f be the function x/2.
Fill in the blanks:
24 f _____
8x f _____
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.