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

 

      rÍ A´B, sÍ 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)

º(definition of 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})

º(definition of dom.r.P)

      ("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)

º(definition of 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})

º(definition of dom.r.P)

      ("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

(Part 1 Theorem 2)

      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

(Part 1 Theorem 3)

      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

(Part 1 Theorem 4)

      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)

(Part 1 Theorem 5)

      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: rÍ A´B Þ ran.r.R = ran.r.(R Ç A)

(Prove LHS Þ RHS)

      rÍ 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: rÍ A´B Þ ran.r.A = ran.r

(given rÍ 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))

º(rÍ 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: rÍ A´B Þ ran.r = dom.(r^-1)

(given rÍ 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: rÍ A´B Ù A Í P Þ ran.r.P = ran.r

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

(property of inverse)

      r^-1Í B´A Ù A Í P

Þ(Part 1 Theorem 8)

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

º(Theorem 1)

      ran.r.P = ran.r

End of Proof

 

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

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

(property of inverse)

      r^-1Í B´A

Þ(Corollary to Part 1 Theorem 8)

      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}

º(Definition of 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})

º(Singleton Set Theorem 1)

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

º(trading)

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

º(One point rule)

     x r y

End of Proof

 

Theorem 14: P Í ~dom.rÞ 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)

      ("a|aÎP: Ø($b |: a r b))

º(DeMorgan)

      ("a|aÎP: ("b |: Ø(a r b)))

º(trading)

      ("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)

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

º(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.rÞ 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)

º(definition of 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}))

º(Part 1 definition of ran.r)

      ("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})

º(definition of dom.r.P)

      ("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:

 

Brettler, Eli 1999, Course notes and comments from M1090 and M2090 math and logic courses,  http://www.math.yorku.ca/Who/Faculty/Brettler/menu.html

 

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.