[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci Dept] / [R J Botting] / [ MATHS ] / logic_42_Properties_of_Relation
[Contents] [Source Text] || [Notation] || [Copyright] || [Contact] [Search ]
Tue Sep 18 15:18:07 PDT 2007

Contents

    Properties of Relations

      Basis

       These notes are based on the following page:
    1. RELATIONS::= See http://csci.csusb.edu/dick/maths/logic_40_Relations.html.

      First time readers might like to see

    2. INTRODUCTION::= See http://csci.csusb.edu/dick/maths/intro_relation.html, before looking at RELATIONS above and the rest of this page.

      There is special listing of the special kinds of relations (transitive, reflexive, etc) in

    3. STANDARD_KINDS::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html#Kinds of relations

      In this page T1 and T2 are types and R is a relationship holding between some elements of type T1 and some elements of type T2:

    4. For T1,T2:Types, R:@(T1,T2).

      Structure of the Domain of a Relation

        PreImages

         First, a relation R:@(T1,T2) is not necessarily total. There can exist elements in T1 (the domain of R) that are not related(by R)to any items in T2(the codomain of R). We use several words to indicate those elements in T1 that take part in R.
      1. (RELATIONS)|-pre(R) ==> T1
      2. (RELATIONS)|-for all x:pre(R), some y:T2 ( x R y).

        Coimages

         Within the pre-image a relation R between a domain T1 and codomain T2 creates a collection of subsets in T1 called the co-image of R. Each set in the co-image of R has elements related to the some element of T2.
      3. For T1,T2, R, coi(R)::@@T1= cod(R)/R.
      4. (RELATIONS)|-coi(R) = {b./R||for some b:T2}.
      5. (RELATIONS)|-coi(R) = {A:@T1 || A = {a:T1 ||for some b:T2(a R b)} }.

        The term co-image was used earlier in the theory of structure preserving mappings between mathematical groups. The idea applies in a looser form for all relationships between sets.

        If R is a many to 1 relation then the coimage is a partition of the domain:

      6. (def)|-For T1,T2, R if R in T1(any)-(1)T2 then T1>==coi(R).

        In general, the coimage of a relation is a family of more or less overlapping subsets of the domain. They almost form a simplicial complex [ Simplicial Complexes in logic_31_Families_of_Sets ] all that is needed is complete the coimage by including all subsets of the sets in the coimage: Suppose that T1 and T2 are finite. Then we can define a complex in T1 (and another dual or complementary one in T2) that reflects the structure of R:

      7. For T1,T2, R, complex(T1,R)::={ c:@T1 || for some y:dom(R)( c.R={y})}.
      8. (above)|-complex(T1,R)={ c:@X || for some y:T2(c==>y./R)}.
      9. (above)|-complex(T1,R)={ y./R || for some y:T2}./==>.
      10. (above)|-complex(T1,R)=complex(coi(R))=complex(X/R).

        The eight chapter of the second volume of John Casti's "Reality Rules" is dedicated to the theory and practical applications of such complexes.

        Each subset in coi(R) is the b./R (preimage) of an element b of the image of R. So it can be labeled with the element that generated it. Sometimes a simplex gets several labels this way. When each subset in the complex is finite then they can be called simplexes and each can be given dimension of one less than the number of elements in it. Each simplex with dimension n can be thought as a labeled n-dimensional object. The family of all more or less overlapping subsets is called a simplicial complex. Overlapping sets define subsimplices (or faces) which indicate the connectivity between parts of the domain. There exist matrix calculations that can estimate the degree of connection between elements in the domain as defined by this complex.

      11. Example::=following,
        Net

        1. |-T1={x1,x2,x3,x4,x5},
        2. |-T2={y1,y2,y3,y4,y5},
        3. |-R = following,
          T2\T1x1x2x3x4x5|b./R|
          y1XX---2
          y2X-X--2
          y3--XX-2
          y4-XX--2
          y5XXX--3

        4. (above)|-R={(x1,y1), (x1,y2), (x1,y5), (x2,y1), (x2,y4), (x2,y5), (x3,y2),(x3,y3), (x3,y4), (x3,y5), (x4,y3).

        5. Complex::=following,
          LabelSimplexDimension
          bb./R|b./R|-1
          y1{x1,x2}1
          y2{x1,x3}1
          y3{x3,x4}1
          y4{x2,x3}1
          y5{x1,x2,x3}2
          Here is the resulting picture

          Picture of complex

          Here is an approximation in ASCII: 

          

               x1
          

              /  \
          

           y1/ y5 \y2
          

           x2------x3----x4      x5
          

               y3     y4
          

          


        (End of Net Example)

        
Simplicial complex look good as long as there are very few simplexes
with dimensions larger than 3.
This simplicial analysis exposes the structure of simple domains
with very little calculation. There two dual views of any relation.
One view has points that are simplices in the other and vice versa.
A more complex computation
[ Formal Concept Analysis ]
combines both structures into a single structure.

        Formal Concept Analysis
        
The above looks at the structure induced on the domain alone.
There is a way of looking at the structure induced
by a relation on its domain and codomain.  This takes the form
of a lattice labeled with the elements in both the domain and
the codomain.

        
The theory has been created by Rudolf Wille.  A thorough write up
of the mathematics
is GanterWille99.  There is also a book of applications.
See
[ ~ganter] . 
and see
[ ag1 ]
for the latest research in this area.

        
Here is an informal example of how it works.

      12. Programming_Languages::$ CONTEXT=following,

        Net
          
I wrote down a collection of high-level Programming
languages and numbered them.  I also made a list of possible
attributes of languages and gave them a letter abbreviation.
I then drew up a table relating objects to attributes.  This step
is subjective and I invite you to draw up your one table of languages
and their properties.  Notice I omit languages like Java, COBOL, and Perl and
attributes such as have record structures or being a script or networked
language.

          PL\Attribute-Separately compiled ModulesControl StructuresConcurrencyData AbstractionObjectsFunctionalDeclarative

          Language-abcdefg

          FORTRAN IV1X------

          FORTRAN 772XX-----

          FORTRAN 903XX-X---

          Algol 604-X-----

          Algol 685-X-----

          Pascal6-X-----

          C  7XX-XXX-

          C++8XX-XXX-

          Ada 839XXXX---

          Ada 9510XXXXX--

          LISP11-----X-

          CLOS12-X--XX-

          Prolog13------X

          Smalltalk14-X--X--

          CPL15-X---X-

          

          
Here is the lattice of formal concepts that I calculated from it:
[Concepts and attributes of programming languages]

          
The calculations are below the algorithm.


        (End of Net Programming_Languages)

        

      13. CONTEXT::=following,

        Net
          

        1. Object::Sets.

        2. Attribute::Sets.

        3. Relation::@(Object, Attribute).

        4. X::=Object.

        5. Y::=Attribute.

        6. R::=Relation.

          

        7. com::@X->@Y=map[A:@X](&[a:A](R(a))), the common attributes of A.

        8. com::@Y->@X=map[B:@Y](&[b:B](/R(b))), the common objects of B.

          

        9. close::= com; com.

          

        10. For x:Y, x:X.

        11. For A,A1,A2:@X.

        12. For B,B1, B2::@Y.

        13. (com)|- (ca1):  com A = {y:Y. for all a:A(a R y)}.

        14. (com)|- (ca2):  com B = {x:X. for all b:B( x R b)}.

          

        15. (ca1)|- (ca3):  if A1==>A2 then com A2 ==> com A1.

        16. (ca2)|- (ca4):  if B1==>B2 then com B2 ==> com B1.

        17. (ca1)|- (ca5):  A==>com com A = close A.

        18. (ca2)|- (ca6):  B==>com com B = close B.

        19. (ca6, ca5, ca3)|- (ca7):  com com com A = com A.

        20. (similarly)|- (ca8):  com com com B = com B.

        21. (ca7, ca8, close)|- (ca89):  close;com = com;close = com.

        22. (ca89, close)|- (closure):  close; close = close.

        23. (com)|- (ca9):  A==>com B iff B ==> com A iff A><B ==>I.

          

        24. (above)|- (ca10):  For all T:Sets, a:T->@X, com(|a) = &[t:T]com(a(t)).

        25. (above)|- (ca11):  For all T:Sets, b:T->@Y, com(|b) = &[t:T]com(b(t)).

          

        26. Concept::@(@X><@Y)={ (A,B) || A = com B and B = com A }.

        27. For (A,B) :Concept, extent(A,B) = A.

        28. For (A,B) :Concept, intent(A,B) = B.

          

        29. sub_super::@(Concept,Concept)=rel[(A1,B1),(A2,B2)](A1 ==> A2).

          

        30. (above)|-if (A1,B1) sub_super (A2,B2) then A1 ==> A2 and B2==>A1. 

          

        31. sub_super is a partial order that defines a lattice of concepts:

        32. C1 + C2::= Concept(extent(C1)|extent(C2), intent(C1)&intent(C2).

        33. C1 * C2::= Concept(extent(C1)&extent(C2), intent(C1)|intent(C2).

          
Here are some C++ classes that implement and test some of these definitions
[ conceptAnalysis.cpp ]

          

        34. Example2::= Example with following,

          Net
            

          1. Concept(X,Y,R)::=

            IntentsExtents

            {}{x1,x2,x3,x4,x5}

            {y1,y5}{x1,x2}

            {y2,y5}{x1,x3}

            {y1,y2}{x1}

            {y4}{x3,x4}

            {y2,y3,y4,5}{x3}

            {y3,y5}{x2, x3}

            {y1,y3,y5}{x2}

            {y5}{x1,x2,x3}

            {y1,y2,y3,y4,y5}{}

            

            
Lattice of Concepts

            
Notice that each node in that above lattice corresponds to
a pair of simplexes in the two complexes described
in Example above.  For example the node with labels {x1,x2,x3}
and {y5}
mathces the triangle with label y5 in the complex Example.


          (End of Net Example2)

          

          

        35. The obvious algorithm to compute Concept is to take every A:@X
and calculate (com com A, com A).  This is O( 2^#X) and so too slow
on all but the simplest contexts.

          

        36. There is a O(n^3) algorithm to calculate Concept from Context.

        37. algorithm::=following

            

          1. Start with an empty table of attributes, intents and extents.

          2. Add a row with {}, X, {} as the first concept.

          3. For each attribute y:Y do

              

            1. Compute A=com{y} -- (A, {y}) is a Concept.

            2. For each row (y1,A1,B1) in the table do

                

              1. Compute A2 = A & A1.

              2. If the A2 is not already in the table

                  

                1. Compute B2=com A2

                2. Create row with y, A2, B2 -- (A2,B2) is a new concept.

                3. Add created row A1 to table.


                


              


            


          

        38. Calculating_Concepts_of_Programming_Languages::Programming_Languages=following,

          Attribute ycom yclose y

          -1..15-

          a1,2,3,7,8,9,10a

          b2,3,4,5,6,7,8,9,10,12,14,15b

          -2,3,7,8,9,10a,b

          c9,10a,b,c,d

          d3,7,8,9,10b,d

          -3,8,9,10a,b,d

          e8,10,12,14b,e

          -8,10a,b,d,e

          -10a,b,c,d,e

          f7,8,11,12,15f

          -7,8a,b,d,f

          -7,8,12,15b,f

          -8a,b,d,e,f

          -8,12b,e,f

          g13g

          ---

          --a,b,c,d,e,f

          

          
There are other algorithms:
[click here [socket symbol]  if you can fill this hole]

          
Software can be found using FTP here:
//ftp.ips.cs.tu-bs.de/pub/local/softech/misc
for DOS and UNIX based machines.


        (End of Net)

        

        
Here
[ logic42c.gif ]
is another example of different ways of displaying
a relationship between two sets:

        

        

      . . . . . . . . . ( end of section Structure of the Domain of a Relation)  <<Contents | End>>

      

      Quantifying relations
        
Often a relation has interesting and/or useful quantifiable properties, for
example all amoeba have a single parent, and all dogs have two parents:

      1. parent in amoeba(1)-(2)amoeba & dogs(2)-(0..)dogs.

        
Typically a relation between two types has a quantitative 'ratio' on one or
more subsets of the types.  The notation A(Q1)-(Q2)B indicates those
relations where each a:A has Q2 b: B and each b:B has Q2 a's.

        

        (def): 

      2. For A:@T1, B:@T2,Q1,Q2:Quantifiers, A(Q1)-(Q2)B::= { R:@(T1,T2)|| for all a:A(Q2 b: B( a R b)) and for all b:B(Q1 a: A(a R b)) }.

        

      . . . . . . . . . ( end of section Quantifying relations)  <<Contents | End>>

      Relations define mappings
        
The following result has been used in many software development methods
to encode relationships using mappings:

      1. (def)|-For A,B,Q1,Q2, R, R in A(Q1)-(Q2)B iff 1st in R(Q2)-(1)A and 2nd in R(Q1)-(1)B ) 

        

      2. (def)|-For A,B, Q:Quantifiers, R:A(any)-(Q)B = for all a:A(Q b:B (a R b) 

      3. (def)|-For A,B, Q, R:A(Q)-(any)B = for all b:B(Q a:A (a R b) 

        
Many to one relations define mappings or functions.
Some decades ago I worked out a simple ASCII based arrow notation
for them.
In these we assume that the mapping does not relate
elements outside its domain and codomain.
Note well that a relation can be many-1 between one pair of
subsets and many-many elsewhere however a relation that maps a subset of a
type into another subset can not relate elements outside of those subsets:

        

      4. |-For A:@T1, B:@T2, @(A,B) =(T1~ A)(0)-(any)B  &  A(any)-(0)(T2~B)

        

        Partial Mappings
        

      5. A<>->B::= @(A,B) & (A(any)-(0..1)B ),

      6. A<-<>B::= @(A,B) & (A(0..1)-(any)B ).

      7. (above)|-if M in A<>->B then /M in B<-<>A. 

        

        Mappings/Functions
        

      8. A>->B::= @(A,B) & (A(any)-(1)B ),

      9. A->B::=A>->B,

      10. A<-<B::= @(A,B) & (A(1)-(any)B).

      11. (above)|-if M in A<>->B then /M in B<-<>A. 

        

        One-one Mappings/injections/monomorphisms
        

      12. A-->B::= @(A,B) & (A(0..1)-(1)B ),

      13. A<--B::= @(A,B) & (A(1)-(0..1)B ),

      14. (above)|-if M in A-->B then /M in B<--A. 

        

        Onto Mappings/surjections/projections/epimorphisms
        

      15. A>--B::= @(A,B) & ( A(1..)-(1)B ),

      16. A--<B::= @(A,B) & ( A(1)-(1..)B ),

      17. (above)|-if M in A>--B then /M in B--<A. 

        

        One-one onto mappings/isomorphisms
        

      18. A---B::= @(A,B) & ( A(1)-(1)B ),

      19. (above)|-if M in A---B then /M in B---A. 

        

        Canonical Forms for Relations
        
All relations between two types can be decomposed, in a canonical way, into
mappings with the class of the mappings determined by the kind of relation.
In consequence we can model most situations and systems in terms of sets
and mappings. Thus we have a normal form for all data bases/data
structures.  This property is exploited in several software development
methods including SSADM.  If the quantifiers are numerical then
the structures can be validated by using the pigeon hole principle.
The numbers can also be used to calculate size estimates and optimal
storage structures for data.  Finally the numbers are useful for
estimating the speed of various operations on the data.

        

        GeneralCanonical Form

        T1(Q1)-(Q2)T2T1(1)-(Q2); (Q1)-(1)T2

        T1(any)-(any)T2T1<-< ; >->T2

        T1(any)-(0..1)T2T1<-- ; >->T2

        T1(any)-(1..)T2T1--< ; >->T2

        T1(any)-(1)T2T1 >-> T2

        T1(1..)-(any)T2T1<-< ; >--T2

        T1(1..)-(0..1)T2T1<-- ; >--T2

        T1(1..)-(1..)T2T1--< ; >--T2

        T1(1..)-(1)T2T1 >-- T2

        T1(1)-(any)T2T1 <-< T2

        T1(1)-(0..1)T2T1 <-- T2

        T1(1)-(1..)T2T1 --< T2

        T1(1)-(1)T2T1 --- T2

        T1(0..1)-(any)T2T1<-< ; -->T2

        T1(0..1)-(0..1)T2T1<-- ; -->T2

        T1(0..1)-(1..)T2T1--< ; -->T2

        T1(0..1)-(1)T2T1 --> T2

        

      20. where   A arrow1;arrow2 B = for some C (A arrow1 C and C arrow2 B)

        
One could define a fourfold arrow notation for relations by joining the two arrows and removing the second and fifth symbols (both dashes). Thus getting

      21. T1-<->T2::=T1 --<;--> T2,
or

      22. T1<<>>T2::=T1<-<;>->T2.

        
Notice that --> is a combination of --- and ==>,
and >-- is a composed of >== and ---. See
[ Arrow Notation in logic_5_Maps ]

        

        Structures and Relations
        
If we have a structured set S with two components x and y then

      23. S ==> $ Net{x:T1, y:T, ....},

      24. x in S->T1 and y in S->T2
so

      25. /x;S;y =rel[t1:T1,t2:T2](for some s:S(t1=s.x and t2=s.y)).

        

      26. exampleS0::=following

        Net
          

        1. if T1=T2=Natural and factors==>Net{divisor,multiple:Natural},

        2. then divides = /divisor;factors;multiple.


        (End of Net exampleS0)

        

        
If we have a structured set S with two components x and y, and arrows a1 and a2 with

      27. x in S a1T1 and y in S a2 T2
and r1 and r2 the respective reversed arrows
then

      28. /x;S;y =rel[t1:T1,t2:T2](for some s:S(t1=s.x and t2=s.y)),

      29. and	/x;S;y is in T1 r1 ; a2 T2

      30. and	/(/x;S;y) =/y;S;x is in T2 r2 ; a1 T1

        
Now in many cases there is only one S defined with x and y, and so we can define

      31. x..y::= /x;S;y,

      32. y..x::=/y;S;x.

        

      33. exampleS1::= exampleS0 with following

        Net
          

        1. if T1=T2=Natural and

        2. factors=$ Net{divisor,multiple:Natural.  For some f:Natural(divisor*f=multiple).}

        3. then divides = divisor..multiple

        4. and  divided = multiple..divisor.


        (End of Net exampleS1)

        

        
When we have type T1 and T2 with only one S with maps x:S->T1 and y:S->T2 we can define

      34. T1..T2::=x..y and T2..T1 = y..x.

        
This generalizes to n-ary relations and is used in software development to
define ways of accessing and manipulating data.

        
For more details on defining dtat structures and data bases
see
[ math_12_Structure.html ]
and
[ math_13_Data_Bases.html ]
etc.

        

      . . . . . . . . . ( end of section Relations define maps)  <<Contents | End>>

      Sources and Links
      

      (Casti): book

        

      • John L Casti

      • Reality Rules, Volume 2

      • Wiley and sons 1992 ISBN 0-471-57798-7

      

      (GanterWille99): Book

        

      • Bernhard Ganter & Rudolf Wille R

      • Formal concept analysis: Mathematical foundations

      • Springer 1999 QA171.5 G3513 1999

      

      

    5. lattice::= See http://www.csci.csusb.edu/dick/maths/math_41_Two_Operators.html#Lattice.

    . . . . . . . . . ( end of section Properties of Relations)  <<Contents | End>>

    Notes on MATHS Notation
    
Special characters are defined in
[ intro_characters.html ]
that also outlines the syntax of expressions and a document.

    
Proofs follow a natural deduction style that start with
assumptions ("Let") and continue to a consequence ("Close Let")
and then discard the assumptions and deduce a conclusion. Look
here
[ Block Structure in logic_25_Proofs ]
for more on the structure and rules.

    
The notation also allows you to create a new network of variables
and constraints. A "Net" has a number  of variables (including none) and
a number of properties (including none) that connect variables.
You can give them a name and then reuse them.  The schema, formal system,
or an elementary piece of documentation starts with "Net" and finishes "End of Net".
For more, see
[ notn_13_Docn_Syntax.html ]
for these ways of defining and reusing pieces of logic and algebra
in your documents.  A quick example: a circle = Net{radius:Positive Real, center:Point}.

    
For a complete listing of pages in  this part of my site by topic see
[ home.html ]

    

    Notes on the Underlying Logic of MATHS
    
The notation used here is a formal language with syntax
and a semantics described using traditional formal logic
[ logic_0_Intro.html ]
plus sets, functions, relations, and other mathematical extensions.

    
For a more rigorous description of the standard notations
see

  1. STANDARD::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html

    Glossary
    

  2. above::reason="I'm too lazy to work out which of the above statements I need here", often the last 3 or 4 statements.
The previous and previous but one statments are shown as (-1) and (-2).

  3. given::reason="I've been told that...", used to describe a problem.

  4. given::variable="I'll be given a value or object like this...", used to describe a problem.

  5. goal::theorem="The result I'm trying to prove right now".

  6. goal::variable="The value or object I'm trying to find or construct".

  7. let::reason="For the sake of argument let...", introduces a temporary hypothesis that survives until the end of the surrounding "Let...Close.Let" block or Case.

  8. hyp::reason="I assumed this in my last Let/Case/Po/...".

  9. QED::conclusion="Quite Easily Done" or "Quod Erat Demonstrandum", indicates that you have proved what you wanted to prove.

  10. QEF::conclusion="Quite Easily Faked", -- indicate that you have proved that the object you constructed fitted the goal you were given.

  11. RAA::conclusion="Reducto Ad Absurdum".  This allows you to discard the last
assumption (let) that you introduced.

    



End