[Skip Navigation] [CSUSB] / [CNS] / [CSE] / [R J Botting] / [ MATHS ] / logic_42_Properties_of_Relation
[Contents] [Source Text] || [Notation] || [Copyright] || [Contact] [Search ]
Tue Apr 17 14:40:08 PDT 2012

Contents


    Properties of Relations

      Basis

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

      First time readers might like to see

    2. INTRODUCTION::= See http://cse.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,
          Table
          T2\T1x1x2x3x4x5|b./R|
          y1XX---2
          y2X-X--2
          y3--XX-2
          y4-XX--2
          y5XXX--3

          (Close Table)

        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,
          Table
          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

          (Close Table)
          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.
          Table
          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-

          (Close Table)

          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)::=
            Table
            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}{}

            (Close Table)

            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,
          Table
          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

          (Close Table)

          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 and 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.


        Table
        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

        (Close Table)

      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 might be described by Net{radius:Positive Real, center:Point, area:=π*radius^2, ...}.

    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