Math Notes – Theory of Relations – Part 2

In the following theorems, all relations are subsets of the cross-product B´C, so an implicit assumption in all theorems is

A´B, A´B

In some theorems there will be a reference to the universal set of discourse.  The universal set of discourse is denoted by U.

A reference to a theorem from part 1, 2, 3, or 4 is noted.  If there is no reference to part 1,2,3, or part 4 then the theorem reference is on this page.

Definition 1: (inverse) <a,b> Î r º <b,a> Î r-1

Theorem 1: ran.r.P = dom.(r-1).P

(Reflexive property of set =)

ran.r.P = ran.r.P

º(definition of set =)

("x |: x Î ran.r.P º x Î ran.r.P)

("x |: x Î ran.r.P º x Î {b |(\$a |:<a, b> ÎrÙ a Î P):b})

º(definition of Î)

("x |: x Î ran.r.P º (\$b |(\$a |:<a, b> ÎrÙ a Î P):b=x))

º(definition of inverse)

("x |: x Î ran.r.P º (\$b |(\$a |:<b, a> Îr-1Ù a Î P):b=x))

º(definition of Î)

("x |: x Î ran.r.P º x Î {b |(\$a |:<b, a> Îr-1Ù a Î P):b})

("x |: x Î ran.r.P º x Î dom.(r-1).P)

º(definition of set =)

ran.r.P = dom.(r-1).P

End of Proof

Theorem 2: ran.(r-1).P = dom.(r).P

(Reflexive property of set =)

ran.{r-1).P = ran.(r-1).P

º(definition of set =)

("x |: x Î ran.{r-1).P º x Î ran.(r-1).P)

("x |: x Î ran.(r-1).P º x Î {b |(\$a |:<a, b> Îr-1Ù a Î P):b})

º(definition of Î)

("x |: x Î ran.(r-1).P º (\$b |(\$a |:<a, b> Îr-1Ù a Î P):b=x))

º(definition of inverse)

("x |: x Î ran.(r-1).P º (\$b |(\$a |:<b, a> ÎrÙ a Î P):b=x))

º(definition of Î)

("x |: x Î ran.(r-1).P º x Î {b |(\$a |:<b, a> ÎrÙ a Î P):b})

("x |: x Î ran.(r-1).P º x Î dom.r.P)

º(definition of set =)

ran.(r-1).P = dom.r.P

End of Proof

Theorem 3: dom.((r-1)-1).P = dom.r.P

(Prove LHS = RHS)

dom.((r-1)-1).P

=(Theorem 1)

ran.(r-1).P

=(Theorem 2)

dom.r.P

End of Proof

Theorem 4: ran.((r-1)-1).P = ran.r.P

(Prove LHS = RHS)

ran.((r-1)-1).P

=(Theorem 2)

dom.(r-1).P

=(Theorem 1)

ran.r.P

End of Proof

Theorem 5: ran.r.Æ = Æ

(Part 1 Theorem 1)
dom.(
r-1).Æ = Æ

º(Theorem 1)

ran.r.Æ = Æ

End of Proof

Theorem 6: P Í Q Þ ran.r.P Í ran.r.Q

P Í Q Þ dom.(r-1).P Í dom.(r-1).Q

º(Theorem 1)

P Í Q Þ ran.r.P Í ran.r.Q

End of Proof

Theorem 7: P Í Q Þ ~ran.r.~P Í ~ran.r.~Q

P Í Q Þ ~dom.(r-1).~P Í ~dom.(r-1).~Q

º(Theorem 1)

P Í Q Þ ~ran.r.~P Í ~ran.r.~Q

End of Proof

Theorem 8: ran.r.(P È Q) = ran.r.P È ran.r.Q

dom.(r-1).(P È Q) = dom.(r-1).P È dom.(r-1).Q

º(Theorem 1)

ran.r.(P È Q) = ran.r.P È ran.r.Q

End of Proof

Theorem 9: ran.r.(P Ç Q) Í (ran.r.P Ç ran.r.Q)

dom.(r-1).(P Ç Q) Í (dom.(r-1).P Ç dom.(r-1).Q)

º(Theorem 1)

ran.r.(P Ç Q) Í (ran.r.P Ç ran.r.Q)

End of Proof

Theorem 10: A´B Þ ran.r.R = ran.r.(R Ç A)

(Prove LHS Þ RHS)

A´B

º(property of inverse)

r-1Í B´A
Þ(Part 1 Theorem 6)

dom.(r-1).R = dom.(r-1).(R Ç A)

º(Theorem 1)

ran.r.R = ran.r.(R Ç A)

End of Proof

Theorem 11: A´B Þ ran.r.A = ran.r

(given A´B, Prove LHS = RHS)

(definition of ran.r.A)

ran.r.A = {b|(\$a|:a r b Ù a Î A):b}

º(Definition of set equality)

("x|x Î ran.r.A º x Î {b|(\$a|:a r b Ù a Î A):b})

º(definition of Î)

("x|x Î ran.r.A º (\$b|(\$a|:a r b Ù a Î A):x=b))

º( A´B Ù a r b Þ a Î A)

("x|x Î ran.r.A º (\$b|(\$a|:a r b Ù true):x=b))

º(identity of Ù)

("x|x Î ran.r.A º (\$b|(\$a|:a r b):x=b))

º(definition of Î)

("x|x Î ran.r.A º x Î {b|(\$a|:a r b):b})

º(definition of ran.r)

("x|x Î ran.r.A º x Î ran.r)

º(Definition of set equality)

ran.r.A = ran.r

End of Proof

Corollary: A´B Þ ran.r = dom.(r-1)

(given A´B, show LHS = RHS)

(Theorem 11)

ran.r = ran.r.A

º(Theorem 1)

ran.r = dom.(r-1).A

º(r-1Í B´A, Part 1 Theorem 7)

ran.r = dom.(r-1)

End of Proof

Theorem 12: A´B Ù A Í P Þ ran.r.P = ran.r

(given A´B Ù A Í P, prove LHS = RHS)

(property of inverse)

r-1Í B´A Ù A Í P

dom.r-1.P = dom.r-1

º(Theorem 1)

ran.r.P = ran.r

End of Proof

Corollary: A´B Þ  ran.r.(R È ~R) = ran.r

(given A´B, prove LHS = RHS)

(property of inverse)

r-1Í B´A

dom.(r-1).(R È ~R) = dom.r-1

º(Theorem 1)

ran.r.(R È ~R) = ran.r

End of Proof

Theorem 13: y Î ran.r.{x} º x r y

(prove LHS º RHS)

y Î ran.r.{x}

y Î {b|(\$a|:a r b Ù a Î {x}):b}

º(Definition of Î)

(\$b|(\$a|:a r b Ù a Î {x}):b=y)

º(One point rule)

(\$a|:a r y Ù a Î {x})

(\$a|:a r y Ù a = x)

(\$a|a r y :a = x)

º(One point rule)

x r y

End of Proof

Theorem 14: P Í ~dom. ran.r.P = Æ

P Í ~dom.r

º(definition of Í)

("a|aÎP: aÎ~dom.r)

º(definition of ~)

("a|aÎP: aÏdom.r)

º(definition of dom.r)

# ("a|aÎP: aÏ{x:A |(\$b:B |: x r b):x})

º(definition of Ï)

# ("a|aÎP: Ø(\$x|(\$b |: x r b):x=a))

º(one point rule)

º(DeMorgan)

# ("a|:aÏPÚ("b |: Ø(a r b)))

º(distribute Ú over ")

# ("a|: ("b |: aÏPÚØ(a r b)))

º(exchange variables)

# ("b|: ("a |: aÏPÚØ(a r b)))

º(DeMorgan, twice)

º(DeMorgan)

# Ø(\$b|: (\$a |: aÎP Ù (a r b)))

Þ(instance (\$x|:), contrapositive)

Ø(\$a |: aÎP Ù (a r x))

º(one point rule)

Ø(\$b|(\$a |: aÎP Ù (a r x):b=x)

º(definition of Î)

Ø(x Î {b|(\$a |: aÎP Ù (a r x):b})

º(definition of ran.r.P)

Ø(x Î ran.r.P)

º(definition of Æ)

ran.r.P = Æ

End of Proof

Theorem 15: P Í dom. P Í dom.r.(ran.r.P)

(Prove LHS Þ RHS)

P Í dom.r

º(PÍP, PÍQÙPÍRºPÍQÇR)

P Í PÇdom.r

º(definition of Í)

("s|s Î P: s Î PÇdom.r)

º(definition of Ç)

("s|s Î P: s Î P Ù s Î dom.r)

("s|s Î P: s Î P Ù s Î {a|(\$b|a r b):a})

º(definition of Î)

("s|s Î P: s Î P Ù (\$a|(\$b|a r b):a=s))

º(Ù distributes over \$)

("s|s Î P: (\$a|(\$b|a r b Ù s Î P):a=s))

º(Ù is idempotent)

("s|s Î P: (\$a|(\$b| a r b Ù a r b Ù s Î P):a=s))

º(One point rule)

("s|s Î P: (\$b| s r b Ù s r b Ù s Î P))

Þ(existence, P Þ (\$x|P))

("s|s Î P: (\$b| s r b Ù (\$c|:c r b Ù c Î P)))

º(One point rule)

("s|s Î P: (\$b| s r b Ù (\$d|(\$c|:c r d Ù c Î P):d=b)))

º(definition of Î)

("s|s Î P: (\$b| s r b Ù b Î {d|(\$c|:c r d Ù c Î P):d}))

("s|s Î P: (\$b| s r b Ù b Î ran.r.P))

º(One point rule)

("s|s Î P: (\$a|(\$b| a r b Ù b Î ran.r.P):a=s))

º(definition of Î)

("s|s Î P: s Î {a|(\$b| a r b Ù b Î ran.r.P):a})

("s|s Î P: s Î dom.r.(ran.r.P))

º(definition of Í)

P Í dom.r.(ran.r.P)

End of Proof

Theorem 16: P Í ran.r Þ P Í ran.r.(dom.r.P)

(Theorem 15)

P Í dom.(r-1) Þ P Í dom.(r-1).(ran.(r-1).P)

º(Theorem 1)

P Í dom.(r-1) Þ P Í ran.r.(ran.(r-1).P)

º(Theorem 2)

P Í dom.(r-1) Þ P Í ran.r.(dom. r.P)

º(Corollary to Theorem 11)

P Í ran.rÞ P Í ran.r.(dom. r.P)

End of Proof

References:

Dijkstra, Edsgar W. and Scholten, Carel S. 1990 Predicate Calculus and Program Semantics, New York, NY: Springer-Verlag

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.