.Open Properties of Relations . Basis These notes are based on the following page: RELATIONS::=http://www/dick/maths/logic_40_Relations.html. First time readers might like to see INTRODUCTION::=http://www/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 STANDARD_KINDS::=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: For T1,T2:Types, R:@(T1,T2). .Open 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. (RELATIONS)|- pre(R) ==> T1 (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. For T1,T2, R, coi(R) ::@@T1= cod(R)/R. (RELATIONS)|- coi(R) = {b./R||for some b:T2}. (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: (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` .See http://www.csci.csusb.edu/dick/maths/logic_31_Families_of_Sets.html#Simplicial Complexes 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: For T1,T2, R, complex(T1,R) ::={ c:@T1 || for some y:dom(R)( c.R={y})}. ()|- complex(T1,R)={ c:@X || for some y:T2(c==>y./R)}. ()|- complex(T1,R)={ y./R || for some y:T2}./==>. ()|- 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. Example::=following, .Net |- T1={x1,x2,x3,x4,x5}, |- T2={y1,y2,y3,y4,y5}, |- R = following, .Table T2\T1 x1 x2 x3 x4 x5 |b./R| .Row y1 X X - - - 2 .Row y2 X - X - - 2 .Row y3 - - X X - 2 .Row y4 - X X - - 2 .Row y5 X X X - - 3 .Close.Table ()|- R={(x1,y1), (x1,y2), (x1,y5), (x2,y1), (x2,y4), (x2,y5), (x3,y2),(x3,y3), (x3,y4), (x3,y5), (x4,y3). Complex::=following, .Table Label Simplex Dimension .Row b b./R |b./R|-1 .Row y1 {x1,x2} 1 .Row y2 {x1,x3} 1 .Row y3 {x3,x4} 1 .Row y4 {x2,x3} 1 .Row y5 {x1,x2,x3} 2 .Close.Table Here is the resulting picture .Image logic42a.gif Picture of complex Here is an approximation in ASCII: .As_is .As_is x1 .As_is / \ .As_is y1/ y5 \y2 .As_is x2------x3----x4 x5 .As_is y3 y4 .As_is .Close.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 .See 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 .See http://www.math.tu-dresden.de/~ganter. and see .See http://www.mathematik.tu-darmstadt.de/ags/ag1 for the latest research in this area. Here is an informal example of how it works. 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 Modules Control Structures Concurrency Data Abstraction Objects Functional Declarative .Row Language - a b c d e f g .Row FORTRAN IV 1 X - - - - - - .Row FORTRAN 77 2 X X - - - - - .Row FORTRAN 90 3 X X - X - - - .Row Algol 60 4 - X - - - - - .Row Algol 68 5 - X - - - - - .Row Pascal 6 - X - - - - - .Row C 7 X X - X X X - .Row C++ 8 X X - X X X - .Row Ada 83 9 X X X X - - - .Row Ada 95 10 X X X X X - - .Row LISP 11 - - - - - X - .Row CLOS 12 - X - - X X - .Row Prolog 13 - - - - - - X .Row Smalltalk 14 - X - - X - - .Row CPL 15 - X - - - X - .Close.Table Here is the lattice of formal concepts that I calculated from it: .Image PLC.gif [Concepts and attributes of programming languages] The calculations are below the algorithm. .Close.Net Programming_Languages CONTEXT::=following, .Net Object::Sets. Attribute::Sets. Relation::@(Object, Attribute). X::=Object. Y::=Attribute. R::=Relation. com::@X->@Y=map[A:@X](&[a:A](R(a))), the common attributes of A. com::@Y->@X=map[B:@Y](&[b:B](/R(b))), the common objects of B. close::= com; com. For x:Y, x:X. For A,A1,A2:@X. For B,B1,B2::@Y. (com)|-(ca1): com A = {y:Y. for all a:A(a R y)}. (com)|-(ca2): com B = {x:X. for all b:B( x R b)}. (ca1)|- (ca3): if A1==>A2 then com A2 ==> com A1. (ca2)|- (ca4): if B1==>B2 then com B2 ==> com B1. (ca1)|- (ca5): A==>com com A = close A. (ca2)|- (ca6): B==>com com B = close B. (ca6,ca5,ca3)|- (ca7): com com com A = com A. (similarly)|- (ca8): com com com B = com B. (ca7, ca8, close)|-(ca89): close;com = com;close = com. (ca89,close)|-(closure): close; close = close. (com)|-(ca9): A==>com B iff B ==> com A iff A>I. ()|- (ca10): For all T:Sets, a:T->@X, com(|a) = &[t:T]com(a(t)). ()|- (ca11): For all T:Sets, b:T->@Y, com(|b) = &[t:T]com(b(t)). Concept::@(@X><@Y)={ (A,B) || A = com B and B = com A }. For (A,B) :Concept, extent(A,B) = A. For (A,B) :Concept, intent(A,B) = B. sub_super::@(Concept,Concept)=rel[(A1,B1),(A2,B2)](A1 ==> A2). ()|-if (A1,B1) sub_super (A2,B2) then A1 ==> A2 and B2==>A1. sub_super is a partial order that defines a $lattice of concepts: C1 + C2 ::= Concept(extent(C1)|extent(C2), intent(C1)&intent(C2). C1 * C2 ::= Concept(extent(C1)&extent(C2), intent(C1)|intent(C2). Here are some C++ classes that implement and test some of these definitions .See http://www/dick/maths/conceptAnalysis.cpp Example2::= $Example with following, .Net Concept(X,Y,R)::= .Table Intents Extents .Row {} {x1,x2,x3,x4,x5} .Row {y1,y5} {x1,x2} .Row {y2,y5} {x1,x3} .Row {y1,y2} {x1} .Row {y4} {x3,x4} .Row {y2,y3,y4,5} {x3} .Row {y3,y5} {x2, x3} .Row {y1,y3,y5} {x2} .Row {y5} {x1,x2,x3} .Row {y1,y2,y3,y4,y5} {} .Close.Table .Image logic42b.gif 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. .Close.Net Example2 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. There is a O(n^3) algorithm to calculate Concept from Context. algorithm::=following .List Start with an empty table of attributes, intents and extents. Add a row with {}, X, {} as the first concept. For each attribute y:Y do .List Compute A=com{y} -- (A, {y}) is a Concept. For each row (y1,A1,B1) in the table do .List Compute A2 = A & A1. If the A2 is not already in the table .List Compute B2=com A2 Create row with y, A2, B2 -- (A2,B2) is a new concept. Add created row A1 to table. .Close.List .Close.List .Close.List .Close.List Calculating_Concepts_of_Programming_Languages::$Programming_Languages=following, .Table Attribute y com y close y .Row - 1..15 - .Row a 1,2,3,7,8,9,10 a .Row b 2,3,4,5,6,7,8,9,10,12,14,15 b .Row - 2,3,7,8,9,10 a,b .Row c 9,10 a,b,c,d .Row d 3,7,8,9,10 b,d .Row - 3,8,9,10 a,b,d .Row e 8,10,12,14 b,e .Row - 8,10 a,b,d,e .Row - 10 a,b,c,d,e .Row f 7,8,11,12,15 f .Row - 7,8 a,b,d,f .Row - 7,8,12,15 b,f .Row - 8 a,b,d,e,f .Row - 8,12 b,e,f .Row g 13 g .Row - - - .Row - - a,b,c,d,e,f .Close.Table There are other algorithms: .Hole Software can be found using FTP here: .See ftp://ftp.ips.cs.tu-bs.de/pub/local/softech/misc for DOS and UNIX based machines. .Close.Net Here .See http://www/dick/maths/logic42c.gif is another example of different ways of displaying a relationship between two sets: .Close Structure of the Domain of a Relation .Open 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: 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`(`Q`1)-(`Q`2)`B` indicates those relations where each a:A has `Q`2 b: B and each b:`B` has `Q`2 `a`'s. (def): 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)) }. .Close Quantifying relations .Open Relations define mappings The following result has been used in many software development methods to encode relationships using mappings: (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 ) (def)|- For A,B, Q:Quantifiers, R:A(any)-(Q)B = for all a:A(Q b:B (a R b) (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: |-For A:@T1, B:@T2, @(A,B) =(T1~ A)(0)-(any)B & A(any)-(0)(T2~B) . Partial Mappings A<>->B::= @(A,B) & (A(any)-(0..1)B ), A<-<>B::= @(A,B) & (A(0..1)-(any)B ). ()|- if M in A<>->B then /M in B<-<>A. . Mappings/Functions A>->B::= @(A,B) & (A(any)-(1)B ), A->B::=A>->B, A<-->B then /M in B<-<>A. . One-one Mappings/injections/monomorphisms A-->B::= @(A,B) & (A(0..1)-(1)B ), A<--B::= @(A,B) & (A(1)-(0..1)B ), ()|- if M in A-->B then /M in B<--A. . Onto Mappings/surjections/projections/epimorphisms A>--B::= @(A,B) & ( A(1..)-(1)B ), A----B then /M in B--->T2 .Row T1(any)-(0..1)T2 T1<-- ; >->T2 .Row T1(any)-(1..)T2 T1--< ; >->T2 .Row T1(any)-(1)T2 T1 >-> T2 .Row T1(1..)-(any)T2 T1<-< ; >--T2 .Row T1(1..)-(0..1)T2 T1<-- ; >--T2 .Row T1(1..)-(1..)T2 T1--< ; >--T2 .Row T1(1..)-(1)T2 T1 >-- T2 .Row T1(1)-(any)T2 T1 <-< T2 .Row T1(1)-(0..1)T2 T1 <-- T2 .Row T1(1)-(1..)T2 T1 --< T2 .Row T1(1)-(1)T2 T1 --- T2 .Row T1(0..1)-(any)T2 T1<-< ; -->T2 .Row T1(0..1)-(0..1)T2 T1<-- ; -->T2 .Row T1(0..1)-(1..)T2 T1--< ; -->T2 .Row T1(0..1)-(1)T2 T1 --> T2 .Close.Table 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 T1-<->T2::=T1 --<;--> T2, or T1<<>>T2::=T1<-<;>->T2. Notice that --> is a combination of --- and ==>, and >-- is a composed of >== and ---. See .See http://www/dick/maths/logic_5_Maps.html#Arrow Notation . Structures and Relations If we have a structured set S with two components x and y then S ==> $ Net{x:T1, y:T, ....}, x in S->T1 and y in S->T2 so /x;S;y =rel[t1:T1,t2:T2](for some s:S(t1=s.x and t2=s.y)). exampleS0::=following .Net if T1=T2=Natural and factors==>$Net{divisor,multiple:Natural}, then divides = /divisor;factors;multiple. .Close.Net exampleS0 If we have a structured set S with two components x and y, and arrows a1 and a2 with x in S a1T1 and y in S a2 T2 and r1 and r2 the respective reversed arrows then /x;S;y =rel[t1:T1,t2:T2](for some s:S(t1=s.x and t2=s.y)), and /x;S;y is in T1 r1 ; a2 T2 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 x..y::= /x;S;y, y..x::=/y;S;x. exampleS1::= $exampleS0 with following .Net if T1=T2=Natural and factors=$ Net{divisor,multiple:Natural. For some f:Natural(divisor*f=multiple).} then divides = divisor..multiple and divided = multiple..divisor. .Close.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 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 .See http://www/dick/maths/math_12_Structure.html and .See http://www/dick/maths/math_13_Data_Bases.html etc. .Close Relations define maps . Sources and Links (Casti): book .Set John L Casti Reality Rules, Volume 2 Wiley and sons 1992 ISBN 0-471-57798-7 .Close.Set (GanterWille99): Book .Set Bernhard Ganter & Rudolf Wille R Formal concept analysis: Mathematical foundations Springer 1999 QA171.5 G3513 1999 .Close.Set lattice::=http://www.csci.csusb.edu/dick/maths/math_41_Two_Operators.html#Lattice. .Close Properties of Relations