.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 and Functions
A>->B::= @(A,B) & (A(any)-(1)B ),
A->B::=A>->B,
A<-->B then /M in B<-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
**