These notes are based on the following page:
 RELATIONS::= See http://cse.csusb.edu/dick/maths/logic_40_Relations.html.
First time readers might like to see
 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
 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:
 For T1,T2:Types, R:@(T1,T2).
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).
Within the preimage
a relation R between a domain T1 and codomain T2 creates a collection of
subsets in T1 called the coimage of R. Each set in the coimage 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./Rfor some b:T2}.
 (RELATIONS)coi(R) = {A:@T1  A = {a:T1 for some b:T2(a R b)} }.
The term coimage 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
[ 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:
 For T1,T2, R, complex(T1,R)::={ c:@T1  for some y:dom(R)( c.R={y})}.
 (above)complex(T1,R)={ c:@X  for some y:T2(c==>y./R)}.
 (above)complex(T1,R)={ y./R  for some y:T2}./==>.
 (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 ndimensional 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,
TableT2\T1  x1  x2  x3  x4  x5  b./R


y1  X  X        2

y2  X    X      2

y3      X  X    2

y4    X  X      2

y5  X  X  X      3

(Close Table)
 (above)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,
TableLabel  Simplex  Dimension


b  b./R  b./R1

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
Here is an approximation in ASCII:
x1
/ \
y1/ y5 \y2
x2x3x4 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.
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.
 Programming_Languages::$ CONTEXT=following,
Net
I wrote down a collection of highlevel 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.
TablePL\Attribute    Separately compiled Modules  Control Structures  Concurrency  Data Abstraction  Objects  Functional  Declarative


Language    a  b  c  d  e  f  g

FORTRAN IV  1  X            

FORTRAN 77  2  X  X          

FORTRAN 90  3  X  X    X      

Algol 60  4    X          

Algol 68  5    X          

Pascal  6    X          

C  7  X  X    X  X  X  

C++  8  X  X    X  X  X  

Ada 83  9  X  X  X  X      

Ada 95  10  X  X  X  X  X    

LISP  11            X  

CLOS  12    X      X  X  

Prolog  13              X

Smalltalk  14    X      X    

CPL  15    X        X  

(Close Table)
Here is the lattice of formal concepts that I calculated from it:
The calculations are below the algorithm.
(End of 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><B ==>I.
 (above) (ca10): For all T:Sets, a:T>@X, com(a) = &[t:T]com(a(t)).
 (above) (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).
 (above)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
[ conceptAnalysis.cpp ]
 Example2::= Example with following,
Net
 Concept(X,Y,R)::=
TableIntents  Extents


{}  {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)
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)
 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
 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
 Compute A=com{y}  (A, {y}) is a Concept.
 For each row (y1,A1,B1) in the table do
 Compute A2 = A & A1.
 If the A2 is not already in the table
 Compute B2=com A2
 Create row with y, A2, B2  (A2,B2) is a new concept.
 Add created row A1 to table.
 Calculating_Concepts_of_Programming_Languages::Programming_Languages=following,
TableAttribute y  com y  close y


  1..15  

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

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

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

c  9,10  a,b,c,d

d  3,7,8,9,10  b,d

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

e  8,10,12,14  b,e

  8,10  a,b,d,e

  10  a,b,c,d,e

f  7,8,11,12,15  f

  7,8  a,b,d,f

  7,8,12,15  b,f

  8  a,b,d,e,f

  8,12  b,e,f

g  13  g

    

    a,b,c,d,e,f

(Close Table)
There are other algorithms:
[click here if you can fill this hole]
Software can be found using FTP here:
//ftp.ips.cs.tubs.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>>
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(Q1)(Q2)B indicates those
relations where each a:A has Q2 b: B and each b:B has Q2 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)) }.
. . . . . . . . . ( end of section Quantifying relations) <<Contents  End>>
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 many1 between one pair of
subsets and manymany 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)
 A<>>B::= @(A,B) & (A(any)(0..1)B ),
 A<<>B::= @(A,B) & (A(0..1)(any)B ).
 (above)if M in A<>>B then /M in B<<>A.
 A>>B::= @(A,B) & (A(any)(1)B ),
 A>B::=A>>B,
 A<<B::= @(A,B) & (A(1)(any)B).
 (above)if M in A>>B then /M in B<<A.
 A>B::= @(A,B) & (A(0..1)(1)B ),
 A<B::= @(A,B) & (A(1)(0..1)B ),
 (above)if M in A>B then /M in B<A.
 A>B::= @(A,B) & ( A(1..)(1)B ),
 A<B::= @(A,B) & ( A(1)(1..)B ),
 (above)if M in A>B then /M in B<A.
 AB::= @(A,B) & ( A(1)(1)B ),
 (above)if M in AB then /M in BA.
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
General  Canonical Form


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

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

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

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

T1(any)(1)T2  T1 >> T2

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

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

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

T1(1..)(1)T2  T1 > T2

T1(1)(any)T2  T1 << T2

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

T1(1)(1..)T2  T1 < T2

T1(1)(1)T2  T1  T2

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

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

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

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
[ Arrow Notation in logic_5_Maps ]
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.
(End of 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.
(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
 T1..T2::=x..y and T2..T1 = y..x.
This generalizes to nary 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>>
(Casti): book
 John L Casti
 Reality Rules, Volume 2
 Wiley and sons 1992 ISBN 0471577987
(GanterWille99): Book
 Bernhard Ganter & Rudolf Wille R
 Formal concept analysis: Mathematical foundations
 Springer 1999 QA171.5 G3513 1999
 lattice::= See http://www.csci.csusb.edu/dick/maths/math_41_Two_Operators.html#Lattice.
. . . . . . . . . ( end of section Properties of Relations) <<Contents  End>>
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 ]
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
 STANDARD::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html
 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).
 given::reason="I've been told that...", used to describe a problem.
 given::variable="I'll be given a value or object like this...", used to describe a problem.
 goal::theorem="The result I'm trying to prove right now".
 goal::variable="The value or object I'm trying to find or construct".
 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.
 hyp::reason="I assumed this in my last Let/Case/Po/...".
 QED::conclusion="Quite Easily Done" or "Quod Erat Demonstrandum", indicates that you have proved what you wanted to prove.
 QEF::conclusion="Quite Easily Faked",  indicate that you have proved that the object you constructed fitted the goal you were given.
 RAA::conclusion="Reducto Ad Absurdum". This allows you to discard the last
assumption (let) that you introduced.