Open main menu

Relation reduction

This page belongs to resource collections on Logic and Inquiry.

In logic and mathematics, relation reduction and relational reducibility have to do with the extent to which a given relation is determined by a set 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 set of other relations, called the reduciens or the relational base, each of which is properly simpler in a specified way than the relation under examination.

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.

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.

DiscussionEdit

The main thing that keeps the general problem of relational reducibility from being fully well-defined 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   is reducible to the set of relations   This amounts to claiming one can be given a set of properly simpler relations   for values   in a given index set   and that this collection of data would suffice to fix the original relation   that one is seeking to analyze, determine, specify, or 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:

  1. Reduction under composition.
  2. 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 relationsEdit

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  -adic relation   as a body that resides in a  -dimensional space   If the domains of the relation   are   then the extension of the relation   is a subset of the cartesian product  

In this setting the interval   is called the index set of the indexed family of sets  

For any subset   of the index set   there is the corresponding subfamily of sets,   and there is the corresponding cartesian product over this subfamily, notated and defined as  

For any point   in   the projection of   on the subspace   is notated as  

More generally, for any relation   the projection of   on the subspace   is written as   or still more simply as  

The question of projective reduction for  -adic relations can be stated with moderate generality in the following way:

  • Given a set of  -place relations in the same space   and a set of projections from   to the associated subspaces, do the projections afford sufficient data to tell the different relations apart?

Projective reducibility of triadic relationsEdit

Main article : Triadic relation

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 3-adic relations that are discussed in the main article on that subject.

Examples of projectively irreducible relationsEdit

The 3-adic relations   and   are shown in the next two Tables:


 
     
     
     
     
     


 
     
     
     
     
     


A 2-adic projection of a 3-adic relation   is the 2-adic relation that results from deleting one column of the table for   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,   the 2-adic projections are indexed by the columns or domains that remain, as shown in the following Tables.


 
   
   
   
   
   
 
   
   
   
   
   
 
   
   
   
   
   


 
   
   
   
   
   
 
   
   
   
   
   
 
   
   
   
   
   


It is clear on inspection that the following three equations hold:

     

These equations say that   and   cannot be distinguished from each other solely on the basis of their 2-adic projection data. In such a case, each relation is said to be irreducible with respect to 2-adic projections. Since reducibility with respect to 2-adic projections is the only interesting case where it concerns the reduction of 3-adic relations, it is customary to say more simply of such a relation that it is projectively irreducible, the 2-adic basis being understood. It is immediate from the definition that projectively irreducible relations always arise in non-trivial multiplets of mutually indiscernible relations.

Examples of projectively reducible relationsEdit

The 3-adic relations   and   are shown in the next two Tables:


 
     
     
     
     
     
     
     
     
     


 
     
     
     
     
     
     
     
     
     


In the case of the two sign relations,   the 2-adic projections are indexed by the columns or domains that remain, as shown in the following Tables.


 
   
   
   
   
   
 
   
   
   
   
   
 
   
   
   
   
   
   
   
   
   


 
   
   
   
   
   
 
   
   
   
   
   
 
   
   
   
   
   
   
   
   
   


It is clear on inspection that the following three inequalities hold:

     

These inequalities say that   and   can be distinguished from each other solely on the basis of their 2-adic projection data. But this is not enough to say that either one of them is projectively reducible to their 2-adic projection data. To say that a 3-adic relation is projectively reducible in that respect, one has to show that it can be distinguished from every other 3-adic relation on the basis of the 2-adic projection data alone.

In other words, to show that a 3-adic relation   on   is reducible or reconstructible in the 2-adic projective sense, it is necessary to show that no distinct   on   exists such that   and   have the same set of projections. Proving this takes a much more comprehensive or exhaustive investigation of the space of possible relations on   than looking merely at one or two relations at a time.

Fact. As it happens, each of the relations   and   is uniquely determined by its 2-adic 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   is a relation over a set of domains that includes the domains   and   then the abbreviated notation   can be used for the projection  
  • 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   under a given projection   is called the fiber of   under   and is written   or  
  • If   is a finite set, the cardinality of   written   or   means the number of elements in  

Proof. Let   be either one of the relations   or   Consider any coordinate position   in the  -plane   If   is not in   then there can be no element   in   therefore we may restrict our attention to positions   in   knowing that there exist at least   elements in   and seeking only to determine what objects   exist such that   is an element in the fiber of   In other words, for what   in   is   in the fiber   Now, the circumstance that   has exactly one element   for each coordinate   in   and that   has exactly one element   for each coordinate   in   plus the “coincidence” of it being the same   at any one choice for   tells us that   has just the one element   over each point of   All together, this proves that both   and   are reducible in an informative sense to 3-tuples of 2-adic relations, that is, they are projectively 2-adically reducible.

SummaryEdit

The projective analysis of 3-adic relations, illustrated by means of concrete examples, has been pursued just far enough at this point to state this clearly demonstrated result:

  • Some 3-adic relations are, and other 3-adic relations are not, reducible to, or reconstructible from, their 2-adic projection data. In short, some 3-adic relations are projectively reducible and some 3-adic relations are projectively irreducible.

SyllabusEdit

Document historyEdit

Portions of the above article were adapted from the following sources under the GNU Free Documentation License, under other applicable licenses, or by permission of the copyright holders.