by Corry Shores

[**Search Blog Here**. Index-tags are found on the bottom of the left column.]

[Logic & Semantics, Entry Directory]

[Patrick Suppes, entry directory]

[Suppes’ *Introduction to Logic*, entry directory]

[The following is summary. My commentary is in brackets. Boldface is mine. I apologize in advance for any distracting typos or other errors.]

Summary of

Patrick Suppes

*Introduction to Logic*

Ch. 10. Relations

§10.6 Operations on Relations

Brief summary:

Relations can be understood as those subsets they produce when they relate members of some set.

*Universal Relation*. We find every possible coupling of the members of one set with those same members. The resulting set is that of the universal relation. All other relations as sets will be subsets of the universal relation’s set. Formally:

If

Vis any domain of individuals, then by the universal relation overVwe mean the set of all ordered couples (x,y) wherex∈Vandy∈V, that is, the Cartesian productV×V.(Suppes 225)

*Empty set relation*. It is the relation whose corresponding set is empty.

The empty set Λ is the relation which never holds. If

R, for instance, is the relation which holds betweenxandyif and only ifxis the mother ofy, andyis the mother ofx, thenR= Λ, for no one is his own grandmother.(225)

With these notions in mind, we can then see how we apply the normal operations on sets to our relations as sets.

*Intersection of relations*.

if

RandSare relations, thenR∩Sis the relation which consists of the intersection ofRandS: i.e.,x(R∩S)yif and only if bothxRyandxSy.(Suppes 225)

*Union of relations*.

R∪Sis the union ofRandS:x(R∪S)yif and only if eitherxRyorxSy.(Suppes 225)

*Difference of Relations*.

R~Sis the relation such thatx(R~S)yif and only ifxRyand notxSy.(Suppes 225)

*Subrelation*.

If

R⊆Swe callRa subrelation ofS. Thus brotherhood is a subrelation of siblinghood; for wheneverxis a brother ofy, thenxis a sibling ofy. Every relation is a subrelation of the universal relation over its own field.(Suppes 226)

There are also operations for binary relations that are not based on these set operators.

*Converse of a relation*.

The converse of a relation

R

is the relation such that, for all

xandy,xRyif and only ifyRx. Thus the converse of a relation is obtained simply by reversing the order of all the ordered couples which constitute it.(Suppes 226)

*Relative product of two relations. *This operation combines two separate relations by finding ones where the second member of one couple (in the first relation) is the same as the first member of the second couple (in the other relation). From these pairings of couples, you make a new couple that takes the first member of the first couple and the second member of the second couple. Being an aunt is an example, with you and your aunt being the end-terms of separate relations (you being the child of your parent, and your parent being the sibling of your aunt), with your parent being the middle term that gets excluded.

If

RandSare binary relations, then by the relative product ofRandS(in symbols:R/S) we mean the relation which holds betweenxandyif and only if there exists azsuch thatRholds betweenxandz, andSholds betweenzandy. Symbolically,

xR/S y↔ (∃z) (xRz&zSy).If

xPymeans thatxis a parent ofy, andxSymeans thatxis a sister ofy, thenx(S/P)ymeans that there is azsuch thatxis a sister ofzandzis a parent ofy, and hence such thatxis an aunt ofy.(Suppes 226)

Furthermore, the relative product relation can be a reiteration of the same relation.

If

xPywhenxis a parent ofy, thenx(P/P)yif and only ifxis a grandparent ofy;x[(P/P)/P]yif and only ifxis a great-grandparent ofy; and so on.(Suppes 226)

Summary

Suppes will now discuss operations that can be performed upon relations. [Recall the notion of cartesian product from section 10.1:

A *Cartesian product* is all the possible ordered pairs made by taking each element from one set and pairing it with each member of another. So if *A*={1,2} and B={Gandhi,Nehru} then

A×B= {⟨1, Gandhi⟩, ⟨1, Nehru⟩, ⟨2, Gandhi⟩, ⟨2, Nehru⟩}

(Suppes 210)

] [It seems we are considering relations as sets, and vice versa. So consider the example above with Gandhi and so on. We can see

{⟨1, Gandhi⟩, ⟨1, Nehru⟩, ⟨2, Gandhi⟩, ⟨2, Nehru⟩}

as a set. But we can also consider it to be a universal relation, which is obtain by performing the operation of finding the Cartesian product of any set with itself. But I might not be following this well. Let me quote.]

If

Vis any domain of individuals, then by the universal relation overVwe mean the set of all ordered couples (x,y) wherex∈Vandy∈V, that is, the Cartesian productV×V.(Suppes 225)

[The idea here might be that we have a set *V*. Then we ask, what relation holds universally? It would be the relation that allows every member to be related to every member. I am guessing, but that might help us with the next relation, the empty set. This is the relation which never holds.]

The empty set Λ is the relation which never holds. If

R, for instance, is the relation which holds betweenxandyif and only ifxis the mother ofy, andyis the mother ofx, thenR= Λ, for no one is his own grandmother.(225)

[So again, we are understanding a relation as a set. The set is what results when the relation is applied to the members of some domain. Now, since a relation is understood as a set, we can perform the same set operations on relations that normally apply to sets, such as union, intersection, and so on.

Since relations are a special kind of sets, we can consider, as applied to relations, the usual operations on sets. Thus, for example, if

RandSare relations, thenR∩Sis the relation which consists of the intersection ofRandS: i.e.,x(R∩S)yif and only if bothxRyandxSy. Similarly,R∪Sis the union ofRandS:x(R∪S)yif and only if eitherxRyorxSy. AndR~Sis the relation such thatx(R~S)yif and only ifxRyand notxSy.(Suppes 225)

[So recall from this quote the formulation for union.

R∪Sis the union ofRandS:x(R∪S)yif and only if eitherxRyorxSy

] Suppose that *xBy* means *x* is a brother of *y* and that *xSy* means *x* is a sister of *y*. What then, using these new structures, would *x*(*B *∪ *S*)*y* mean? Given the definition, it should mean *xBy* ∨ *xSy*. In other words, it should be anyone who is either a brother or a sister, which would mean the same as *x* is a sibling of *y* (Suppes 225). [Now recall the formulation for intersection.

x(R∩S)yif and only if bothxRyandxSy

Suppose some *x* is a brother of *y*. That means *x* is a male. That further more means he cannot be a sister to someone else. Thus the intersection of these relations is the empty set or empty relation. Now finally suppose we have the operation *B* ~ *S*. This was defined as:

R~Sis the relation such thatx(R~S)yif and only ifxRyand notxSy

In our example, we would wonder who is a brother that happens to not be a sister. That would be all brothers of course.]

If

xBywhenxis a brother ofy, andxSywhenxis a sister ofy, thenx(B∪S)ywhenxis a sibling ofy; butB∩Sis the empty relation. We notice thatB~S=B, since the sets of ordered couplesBandSare mutually exclusive.(Suppes 225)

The subset operation on relations, which we now call being a subrelation, works how we would expect it to.

If

R⊆Swe callRa subrelation ofS. Thus brotherhood is a subrelation of siblinghood; for wheneverxis a brother ofy, thenxis a sibling ofy. Every relation is a subrelation of the universal relation over its own field.(Suppes 226)

[Recall from section 9.6 that the *complement of A *relative to the domain are all those items in the domain that are not in *A*. We symbolize it either as* *V∼*A *or just ∼*A*. Now in the case of relations as sets, we said that the universal relation gives us every possible combination of the set members. Any other more specific relation will have smaller set than the one for the universal relation.]

If we have chosen a domain of individuals

V, and ifUis the universal relation overV(i.e.,U=V×V), then by ~R, whenRis a relation whose field is a subset ofV, we mean simplyU~R.(226)

So we just dealt with operations on relations that were based on operations on sets that we have already seen [sections 9.5, 9.6, and 10.1]. Suppes will now give some that deal with binary relations with sets of ordered couples. [I will not be able to notate converse relation. But the basic idea is that a binary relation will have its set of ordered couples. The converse relation has the set where all the first one’s couples have their order inverted.]

Besides these operations, which are all simply special cases of the operations on sets, it is also possible to define some special operations on binary relations which depend on the fact that they are sets of ordered couples. The converse of a relation

R

is the relation such that, for all

xandy,xRyif and only ifyRx. Thus the converse of a relation is obtained simply by reversing the order of all the ordered couples which constitute it. The converse of the relationHwhich holds betweenxandyif and only ifxis the husband ofy, is the relationWwhich holds betweenyandxif and only ifyis the wife ofx. Thus,

(Suppes 226)

[The next notion of relative product is a little complicated. It seems the idea is that we have two binary relations. We then link them by means of a third term. So suppose we have *xPy* and *xSy*. The first thing to note I think is that when we find the relative product, we do not mean the same terms will hold for *x *and for *y* in both cases. Rather, what we are thinking of is *x* having the first relation to some *z*, which has the second relation to some *y*. The example he will give is being an aunt. This can be seen as being constituted by the relative product of two other relations, namely, being a parent and being a sister. For, as you know, your aunt is your parent’s sister.]

If

RandSare binary relations, then by the relative product ofRandS(in symbols:R/S) we mean the relation which holds betweenxandyif and only if there exists azsuch thatRholds betweenxandz, andSholds betweenzandy. Symbolically,

xR/S y↔ (∃z) (xRz&zSy).If

xPymeans thatxis a parent ofy, andxSymeans thatxis a sister ofy, thenx(S/P)ymeans that there is azsuch thatxis a sister ofzandzis a parent ofy, and hence such thatxis an aunt ofy. The formation of relative products is not a commutative operation. For instance, withPandSas above,P/Sis not the same asS/P: a man’s aunt is seldom a parent of his sister.(Suppes 226)

[We can also compound the same relation, as with the parent relation compounded to get the grandparent relation.]

If

xPywhenxis a parent ofy, thenx(P/P)yif and only ifxis a grandparent ofy;x[(P/P)/P]yif and only ifxis a great-grandparent ofy; and so on. On the supposition that creation had no beginning (i.e., every person has parents), the relationsP,P/P, (P/P)/P, etc., are all different.(Suppes 226)

[Suppes then gives a final example. As we will see, there are two sets of couples. We can perform the relative product operation on the sets only in those cases where the final term of one is the initial term of the other.]

As a final example, if

R= {<1, 3>, <2, 3>},

S= {<3, 1>},then

R/S= {<1, 1>, <2, 1>},

S/R= {<3, 3>},(

S/R)/R =Λ.(Suppes 226)

From:

Suppes, Patrick. *Introduction to Logic*. New York: Van Nostrand Reinhold / Litton Educational, 1957.

.

## No comments:

## Post a Comment