Relation Composition Article Index for
Relation 		Website Links For
Relation 		 

Information About

Relation Composition
  CATEGORIES ABOUT RELATION COMPOSITION
   
logic
   
mathematical relations
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...




PRELIMINARIES


The first order of business is to define the Operation on Relations that is variously known as the ''composition of relations'', ''relational composition'', or ''relative multiplication''. In approaching the more general constructions, it pays to begin with the composition of 2-adic and 3-adic relations.

As an incidental observation on usage, there are many different conventions of Syntax for denoting the application and composition of relations, with perhaps even more options in general use than are common for the application and composition of Functions . In this case there is little chance of standardization, since the convenience of conventions is relative to the context of use, and the same writers use different styles of syntax in different settings, depending on the ease of analysis and computation.

  • The first dimension of variation in syntax has to do with the correspondence between the order of operation and the linear order of terms on the page.


  • The second dimension of variation in syntax has to do with the automatic assumptions in place about the associations of terms in the absence of associations marked by parentheses. This becomes a significant factor with relations in general because the usual property of Associativity is lost as both the complexities of compositions and the dimensions of relations increase.


  • These two factors together generate the following four styles of syntax:

  • --- LALA = left application, left association.

  • --- LARA = left application, right association.

  • --- RALA = right application, left association.

  • --- RARA = right application, right association.



DEFINITION


A notion of relational composition is to be defined that generalizes the usual notion of functional composition:

  • Composing ''on the right'', f : X o Y followed by g : Y o Z results in a ''composite function'' formulated as fg : X o Z.


  • Composing ''on the left'', f : X o Y followed by g : Y o Z results in a ''composite function'' formulated as gf : X o Z.


Note on notation. The ordinary symbol for functional composition is the '' Composition Sign '', a small circle  "ο"  written between the names of the functions being composed, as f ο g, but the sign is often omitted if there is no risk of confusing the composition of functions with their algebraic product. In contexts where both compositions and products occur, either the composition is marked on each occasion or else the product is marked by means of a ''raised dot sign'' "\cdot", as f\cdotg.

Generalizing the paradigm along parallel lines, the ''composition'' of a pair of 2-adic relations is formulated in the following two ways:

  • Composing ''on the right'', P \subseteq X imes Y followed by Q \subseteq Y imes Z results in a ''composite relation'' formulated as PQ \subseteq X imes Z.


  • Composing ''on the left'', P \subseteq X imes Y followed by Q \subseteq Y imes Z results in a ''composite relation'' formulated as QP \subseteq X imes Z.



GEOMETRIC CONSTRUCTION


There is a neat way of defining relational compositions in geometric terms, not only showing their relationship to the Projection operations that come with any Cartesian Product , but also suggesting natural directions for generalizing relational compositions beyond the 2-adic case, and even beyond relations that have any fixed Arity , in effect, to the general case of Formal Language s as generalized relations.

This way of looking at relational compositions is sometimes referred to as Tarski 's Trick (\mbox{T}^2), on account of his having put it to especially good use in his work (Ulam and Bednarek, 1977). It supplies the imagination with a geometric way of visualizing the relational composition of a pair of 2-adic relations, doing this by attaching concrete imagery to the basic Set-theoretic operations, namely, Intersection s, Projection s, and a certain class of operations Inverse to projections, here called ' Tacit Extension s'.

The stage is set for Tarski's trick by highlighting the links between two topics that are likely to appear wholly unrelated at first, namely:

  • The use of logical Conjunction , as denoted by the symbol  "∧"  in expressions of the form ''F''(''x'', ''y'', ''z'') = ''G''(''x'', ''y'') ∧ ''H''(''y'', ''z''), to define a 3-adic relation ''F'' in terms of a pair of 2-adic relations ''G'' and ''H''.


  • The concepts of 2-adic '' Projection '' and ''projective determination'', that are invoked in the 'weak' notion of ''projective reducibility''.


The relational composition ''G'' ο ''H'' of a pair of 2-adic relations ''G'' and ''H'' will be constructed in three stages, first, by taking the tacit extensions of ''G'' and ''H'' to 3-adic relations that reside in the same space, next, by taking the intersection of these extensions, tantamount to the maximal 3-adic relation that is consistent with the ''prima facie'' 2-adic relation data, finally, by projecting this intersection on a suitable plane to form a third 2-adic relation, constituting in fact the relational composition ''G'' ο ''H'' of the relations ''G'' and ''H''.

The construction of a relational composition in a specifically mathematical setting normally begins with Mathematical Relations at a higher level of abstraction than the corresponding objects in linguistic or logical settings. This is due to the fact that mathematical objects are typically specified only 'up to Isomorphism ' as the conventional saying goes, that is, any objects that have the 'same form' are generally regarded as the being the same thing, for most all intents and mathematical purposes. Thus, the mathematical construction of a relational composition begins by default with a pair of 2-adic relations that reside, without loss of generality, in the same plane, say, ''G'', ''H'' ⊆ ''X'' × ''Y'', as depicted in Figure 1.

o
-o
  Figure 8 G O H proj_XZ (te(G) ^ te(H))
  Given The Space ''X'' {1, 2, 3, 4, 5, 6, 7}, whose cardinality ''X'' is 7, we naturally observe that there are ''X'' &times ''X'' = ''X'' &middot ''X'' = 7 &middot 7 = 49 elementary relations of the form ''i'':''j'', where ''i'' and ''j'' range over the space ''X'' Although they might be organized in many different ways, it is convenient to regard the collection of elementary relations as being arranged in a lexicographic block of the following form:
  { Cellpadding "2"
  { Cellpadding "2" style="text-align:center"