Relational Reduction
In logic and mathematics, relation reduction and relational reducibility have to do with the extent to which a given relation is determined by an indexed family or a sequence of other relations, called the relation dataset. The relation under examination is called the reductandum. The relation dataset typically consists of a specified relation over sets of relations, called the reducer, the method of reduction, or the relational step, plus a specified set of other relations, simpler in some measure than the reductandum, called the reduciens or the relational base.
A question of relation reduction or relational reducibility is sometimes posed as a question of relation reconstruction or relational reconstructibility, since a useful way of stating the question is to ask whether the reductandum can be reconstructed from the reduciens. See Humpty Dumpty.
A relation that is not uniquely determined by a particular relation dataset is said to be irreducible in just that respect. A relation that is not uniquely determined by any relation dataset in a particular class of relation datasets is said to be irreducible in respect of that class.
Discussion
The main thing that keeps the general problem of relational reducibility from being fully welldefined is that one would have to survey all of the conceivable ways of “getting new relations from old” in order to say precisely what is meant by the claim that the relation L is reducible to the set of relations {L_{j}Â :Â jÂ inÂ JÂ }. This is tantamount to claiming that if one is given a set of “simpler” relations L_{j}Â , for indices j in some set J, that this collection of data would somehow or other fix the original relation L that one is seeking to analyze, to determine, to specify, or to synthesize.In practice, however, apposite discussion of a particular application typically settles on either one of two different notions of reducibility as capturing the pertinent issues, namely:
 Reduction under composition.
 Reduction under projections.
As it happens, there is an interesting relationship between these two notions of reducibility, the implications of which may be taken up partly in parallel with the discussion of the basic concepts.
Projective reducibility of relations
It is convenient to begin with the projective reduction of relations, partly because this type of reduction is simpler and more intuitive (in the visual sense), but also because a number of conceptual tools that are needed in any case arise quite naturally in the projective setting.The work of intuiting how projections operate on multidimensional relations is often facilitated by keeping in mind the following sort of geometric image:
 Picture a kadic relation L as a body that resides in a kdimensional space X. If the domains of the relation L are X_{1},Â â€¦,Â X_{k}Â , then the extension of the relation L is a subset of the cartesian product XÂ =Â X_{1}Â Ã—Â â€¦Â Ã—Â X_{k}Â .
In this setting, the interval K = [1, k] = {1,Â ;â€¦,Â k} is called the index set of the indexed family of sets X_{1},Â â€¦,Â X_{k}Â .
For any subset F of the index set K, there is the corresponding subfamily of sets, {X_{j} : j ∈ F }, and there is the corresponding cartesian product over this subfamily, notated and defined as X_{F} = Π_{j ∈ F} X_{j}.
For any point x in X, the projection of x on the subspace X_{F} is notated as proj_{F}(x).
More generally, for any relation LÂ ⊆Â X, the projection of L on the subspace X_{F} is written as proj_{F}(L), or still more simply, as proj_{F}Â L.
The question of projective reduction for kadic relations can be stated with moderate generality in the following way:
 Given a set of kplace relations in the same space X and a set of projections from X to the associated subspaces, do the projections afford sufficient data to tell the different relations apart?
Projective reducibility of triadic relations
By way of illustrating the different sorts of things that can occur in considering the projective reducibility of relations, it is convenient to reuse the four examples of 3adic relations that are discussed in the main article on that subject.
Examples of projectively irreducible relations
The 3adic relations L_{0} and L_{1} are shown in the next two Tables:! X !! Y !! Z
0 >  0 > 0 
0 >  1 > 1 
1 >  0 > 1 
1 >  1 > 0 
! X !! Y !! Z
0 >  0 > 1 
0 >  1 > 0 
1 >  0 > 0 
1 >  1 > 1 
A 2adic projection of a 3adic relation L is the 2adic relation that results from deleting one column of the table for L and then deleting all but one row of any resulting rows that happen to be identical in content. In other words, the multiplicity of any repeated row is ignored.
In the case of the above two relations, L_{0}, L_{1} ⊆ X Ã— Y Ã— Z ≈ B^{3}, the 2adic projections are indexed by the columns or domains that remain, as shown in the following Tables.
0 > 0 
0 > 1 
1 > 0 
1 > 1 
! X !! Z
0 > 0 
0 > 1 
1 > 1 
1 > 0 
! Y !! Z
0 > 0 
1 > 1 
0 > 1 
1 > 0 
0 > 0 
0 > 1 
1 > 0 
1 > 1 
! X !! Z
0 > 1 
0 > 0 
1 > 0 
1 > 1 
! Y !! Z
0 > 1 
1 > 0 
0 > 0 
1 > 1 
It is clear on inspection that the following three equations hold:
proj_{XY}(L_{0}) = proj_{XY}(L_{1})  proj_{XZ}(L_{0}) = proj_{XZ}(L_{1})  proj_{YZ}(L_{0}) = proj_{YZ}(L_{1}) 
These equations say that L_{0} and L_{1} cannot be distinguished from each other solely on the basis of their 2adic projection data. In such a case, either relation is said to be irreducible with respect to 2adic projections. Since reducibility with respect to 2adic projections is the only interesting case where it concerns the reduction of 3adic relations, it is customary to say more simply of such a relation that it is projectively irreducible, the 2adic basis being understood. It is immediate from the definition that projectively irreducible relations always arise in nontrivial multiplets of mutually indiscernible relations.
Examples of projectively reducible relations
The 3adic relations L_{A} and L_{B} are shown in the next two Tables:Object  Sign  Interpretant 

A >  “A” > “A”  
A >  “A” > “i”  
A >  “i” > “A”  
A >  “i” > “i”  
B >  “B” > “B”  
B >  “B” > “u”  
B >  “u” > “B”  
B >  “u” > “u” 
Object  Sign  Interpretant 

A >  “A” > “A”  
A >  “A” > “u”  
A >  “u” > “A”  
A >  “u” > “u”  
B >  “B” > “B”  
B >  “B” > “i”  
B >  “i” > “B”  
B >  “i” > “i” 
In the case of the two sign relations, L_{A}, L_{B} ⊆ X Ã— Y Ã— Z ≈ O Ã— S Ã— I, the 2adic projections are indexed by the columns or domains that remain, as shown in the following Tables.
Object  Sign 

A > “A”  
A > “i”  
B > “B”  
B > “u” 
Object  Interpretant 

A > “A”  
A > “i”  
B > “B”  
B > “u” 
Sign  Interpretant 

“A” > “A”  
“A” > “i”  
“i” > “A”  
“i” > “i”  
“B” > “B”  
“B” > “u”  
“u” > “B”  
“u” > “u” 
Object  Sign 

A > “A”  
A > “u”  
B > “B”  
B > “i” 
Object  Interpretant 

A > “A”  
A > “u”  
B > “B”  
B > “i” 
Sign  Interpretant 

“A” > “A”  
“A” > “u”  
“u” > “A”  
“u” > “u”  
“B” > “B”  
“B” > “i”  
“i” > “B”  
“i” > “i” 
It is clear on inspection that the following three inequations hold:
proj_{XY}(L_{A}) ≠ proj_{XY}(L_{B})  proj_{XZ}(L_{A}) ≠ proj_{XZ}(L_{B})  proj_{YZ}(L_{A}) ≠ proj_{YZ}(L_{B}) 
These inequations say that L_{A} and L_{B} can be distinguished from each other solely on the basis of their 2adic projection data. But this is not enough to say that either one of them is projectively reducible to their 2adic projection data. To say that a 3adic relation is projectively reducible in that respect, one has to show that it can be distinguished from every other 3adic relation on the basis of the 2adic projection data alone.
In other words, to show that a 3adic relation L on OÂ Ã—Â SÂ Ã—Â I is reducible or reconstructible in the 2adic projective sense, it is necessary to show that no distinct L′ on OÂ Ã—Â SÂ Ã—Â I exists such that L and L′ have the same set of projections. Proving this takes a much more comprehensive or exhaustive investigation of the space of possible relations on OÂ Ã—Â SÂ Ã—Â I than looking merely at one or two relations at a time.
Fact. As it happens, each of the relations L_{A} and L_{B} is uniquely determined by its 2adic projections. This can be seen by following the proof that is given below.
Before tackling the proof, however, it will speed things along to recall a few ideas and notations from other articles.
 If L is a relation over a set of domains that includes the domains U and V, then the abbreviated notation L_{UVÂ } can be used for the projection proj_{UVÂ }(L).
 The operation of reversing a projection asks what elements of a bigger space project onto given elements of a smaller space. The set of elements that project onto x under a given projection f is called the fiber of x under f and is written f^{â€“1}(x) or f^{â€“1}x.
 If X is a finite set, the cardinality of X, written card(X) or X, means the number of elements in X.
Proof. Let L be either one of the relations L_{A} or L_{B}. Consider any coordinate position (s,Â i) in the SIplane SÂ Ã—Â I. If (s,Â i) is not in L_{SI} then there can be no element (o,Â s,Â i) in L, therefore we may restrict our attention to positions (s,Â i) in L_{SI}, knowing that there exist at least L_{SI} = 8 elements in L, and seeking only to determine what objects o exist such that (o,Â s,Â i) is an element in the fiber of (s,Â i). In other words, for what o in O is (o,Â s,Â i) in the fiber proj_{SI}^{â€“1}(s,Â i)Â ? Now, the circumstance that L_{OS} has exactly one element (o,Â s) for each coordinate s in S and that L_{OI} has exactly one element (o,Â i) for each coordinate i in I, plus the “coincidence” of it being the same o at any one choice for (s,Â i), tells us that L has just the one element (o,Â s,Â i) over each point of SÂ Ã—Â I. All together, this proves that both L_{A} and L_{B} are reducible in an informative sense to 3tuples of 2adic relations, that is, they are projectively 2adically reducible.
Summary
The projective analysis of 3adic relations, illustrated by means of concrete examples, has been pursued just far enough at this point to state this clearly demonstrated result: Some 3adic relations are, and other 3adic relations are not, reducible to, or reconstructible from, their 2adic projection data. In short, some 3adic relations are projectively reducible and some 3adic relations are projectively irreducible.
See also


Some content adapted from the Wikinfo article “Relation reduction” under the GNU Free Documentation License.
[ getwiki edits: 1 , site views: 2,549 ]