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 V is any domain of individuals, then by the universal relation over V we mean the set of all ordered couples (x, y) where x ∈ V and y ∈ V, that is, the Cartesian product V × 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 between x and y if and only if x is the mother of y, and y is the mother of x, then R = Λ, 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 R and S are relations, then R ∩ S is the relation which consists of the intersection of R and S: i.e., x(R ∩ S)y if and only if both xRy and xSy.
(Suppes 225)
Union of relations.
R ∪ S is the union of R and S: x(R ∪ S)y if and only if either xRy or xSy.
(Suppes 225)
Difference of Relations.
R ~ S is the relation such that x(R ~ S)y if and only if xRy and not xSy.
(Suppes 225)
Subrelation.
If R ⊆ S we call R a subrelation of S. Thus brotherhood is a subrelation of siblinghood; for whenever x is a brother of y, then x is a sibling of y. 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 x and y, xRy if and only if yRx. 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 R and S are binary relations, then by the relative product of R and S (in symbols: R/S) we mean the relation which holds between x and y if and only if there exists a z such that R holds between x and z, and S holds between z and y. Symbolically,
x R/S y ↔ (∃z) (xRz & zSy).
If xPy means that x is a parent of y, and xSy means that x is a sister of y, then x(S/P)y means that there is a z such that x is a sister of z and z is a parent of y, and hence such that x is an aunt of y.
(Suppes 226)
Furthermore, the relative product relation can be a reiteration of the same relation.
If xPy when x is a parent of y, then x(P/P)y if and only if x is a grandparent of y; x[(P/P)/P]y if and only if x is a great-grandparent of y; 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 V is any domain of individuals, then by the universal relation over V we mean the set of all ordered couples (x, y) where x ∈ V and y ∈ V, that is, the Cartesian product V × 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 between x and y if and only if x is the mother of y, and y is the mother of x, then R = Λ, 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 R and S are relations, then R ∩ S is the relation which consists of the intersection of R and S: i.e., x(R ∩ S)y if and only if both xRy and xSy. Similarly, R ∪ S is the union of R and S: x(R ∪ S)y if and only if either xRy or xSy. And R ~ S is the relation such that x(R ~ S)y if and only if xRy and not xSy.
(Suppes 225)
[So recall from this quote the formulation for union.
R ∪ S is the union of R and S: x(R ∪ S)y if and only if either xRy or xSy
] 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)y if and only if both xRy and xSy
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 ~ S is the relation such that x(R ~ S)y if and only if xRy and not xSy
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 xBy when x is a brother of y, and xSy when x is a sister of y, then x(B ∪ S)y when x is a sibling of y; but B ∩ S is the empty relation. We notice that B ~ S = B, since the sets of ordered couples B and S are 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 ⊆ S we call R a subrelation of S. Thus brotherhood is a subrelation of siblinghood; for whenever x is a brother of y, then x is a sibling of y. 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 if U is the universal relation over V (i.e., U = V × V), then by ~R, when R is a relation whose field is a subset of V, we mean simply U ~ 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 x and y, xRy if and only if yRx. 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 relation H which holds between x and y if and only if x is the husband of y, is the relation W which holds between y and x if and only if y is the wife of x. 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 R and S are binary relations, then by the relative product of R and S (in symbols: R/S) we mean the relation which holds between x and y if and only if there exists a z such that R holds between x and z, and S holds between z and y. Symbolically,
x R/S y ↔ (∃z) (xRz & zSy).
If xPy means that x is a parent of y, and xSy means that x is a sister of y, then x(S/P)y means that there is a z such that x is a sister of z and z is a parent of y, and hence such that x is an aunt of y. The formation of relative products is not a commutative operation. For instance, with P and S as above, P/S is not the same as S/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 xPy when x is a parent of y, then x(P/P)y if and only if x is a grandparent of y; x[(P/P)/P]y if and only if x is a great-grandparent of y; and so on. On the supposition that creation had no beginning (i.e., every person has parents), the relations P, 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