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.3 Properties of Binary Relations

Brief summary:

There are a number of sorts of binary relations. If a relation that relates things to themselves holds for all things, then it is reflexive, and if it holds for no things, then it is irreflexive.

A (binary) relation

Risreflexive in the set Aif for everyxinA,xRx(i.e., ⟨x,x⟩ ∈R):

Rreflexive inA↔ (x)(x∈A→xRx).

A relation

Risirreflexive in the set Aif, for everyxinAit is not the case thatxRx:

Rirreflexive inA↔ (x)(x∈A→ –(xRx)).

When there is a two-place relation, if the order of the relation can be switched for all substitutions, then it is *symmetric*. If for all substitutions it cannot be switched and still be true, then it is asymmetric.

A relation

Rissymmetric in the set Aif for everyxandyinA, wheneverxRy, thenyRx:

Rsymmetric inA↔ (x)(y)[x∈A&y∈A&xRy→yRx].

A relation

Risasymmetric in the set Aif, for everyxandyinA, wheneverxRy, then it is not the caseyRx:

Rasymmetric inA↔ (x)(y)[x∈A&y∈A&xRy→ –(yRx)].

Now ≤ is not symmetric, because although 3 ≤ 3 and 3 ≤ 3, that invertibility does not hold for 2 ≤ 3. It is also not antisymmetric, because although the invertibility does not hold in most cases, it does for 3 ≤ 3. However, it is always symmetric under the condition that both terms are equal to one another. It is thus *antisymmetric*.

A relation

Risantisymmetric in the set Aif for everyxandyinA, wheneverxRyandyRx, thenx=y:

Rantisymmetric inA↔ (x)(y)[x∈A&y∈A&xRy&yRx→x=y].

A relation can also be neither symmetric, asymmetric, nor antisymmetric. One example is the love relation. It is not symmetric, because not every person loves the people who love them. It is also not asymmetric, because there are many cases of mutual love. It is furthermore not antisymmetric, because it is not the case that the only people who are in love are those who love themselves.

A relation is *transitive* if it carries over through a middle term.

A relation

Ristransitive in the set Aif, for everyx,y, andzinA, wheneverxRyandyRz, thenxRz:

Rtransitive inA↔ (x)(y)(z)[x∈A&y∈A&z∈A&xRy&yRz→xRz].

A relation is *intransitive* if for no things that it relates does the relation of a first item to a second one along with and the second one to a third imply that the relation holds as well for the first to the third. Another idea is the difference between intransitive and non-transitive.

A relation

Risintransitive in the set Aif for everyx,y, andzinA, wheneverxRyandyRz, then it is not the case thatxRz:

Rintransitive in

A ↔(x)(y)(z)[x∈A&y∈A&z∈A&xRy&yRz→ –(xRz)].

Note that a relation can be non-transitive without being intransitive, because for some relations, there is transitivity between some triplets of terms but not between others.

A relation is *connected* if it relates any member to any other member.

A relation

Risconnected in the set Aif for everyxandyinA, wheneverx≠y, thenxRyoryRx:

Rconnected inA↔(x)(y)(x∈A&y∈A&x≠y→xRy∨yRx).

A relation is *strongly connected* if it holds for any member with any other member and as well with any member and itself.

A relation

Ris strongly connected in the setAif for everyxandyinA, eitherxRyoryRx:

Rstrongly connected inA↔(x)(y)(x∈A&y∈A→xRy∨yRx).

Summary

Suppes will now discuss some important and useful properties of binary relations.

If a relation that relates things to themselves holds for all things, then it is reflexive, and if it holds for no things, then it is irreflexive.

A (binary) relation

Risreflexive in the set Aif for everyxinA,xRx(i.e., ⟨x,x⟩ ∈R). In symbols:

Rreflexive inA↔ (x)(x∈A→xRx).The relation ≤ for instance, is reflexive in the set of all real numbers, since for every number

x,x≤x. If

A_{1 }= {Descartes, Mersenne},

A_{2 }= {Descartes, 5},and

R_{2}= {⟨Descartes, Descartes⟩, ⟨Mersenne, Mersenne⟩, ⟨5, Λ⟩},then

R_{2 }is reflexive inA_{1 }but is not reflexive inA_{2}, since the ordered couple ⟨5, 5⟩ is not a member ofR_{2}. The relation of loving is probably reflexive in the set of all people; indeed, some moralists maintain that we all love ourselves somewhat too well.A relation

Risirreflexive in the set Aif, for everyxinAit is not the case thatxRx. In symbols:

Rirreflexive inA↔ (x)(x∈A→ –(xRx)).The relation of being a mother is irreflexive in the set of people, since no one is his own mother. The relation < is irreflexive in the set of real numbers, since no number is less than itself. We have already seen that

R_{2 }is not reflexive inA_{2}, but it is also not irreflexive inA_{2}, because ⟨Descartes, Descartes⟩ ∈R_{2}. Consider:A

_{3 }= {5, Elizabeth I}.It is clear that

R_{2 }is irreflexive in A_{3}. From the example ofR_{2}andA_{2}, it should be obvious that for any relationRand setAthere are three possibilities:(1)

Ris reflexive inA.(2)

Ris irreflexive inA.(3) Neither (1) nor (2).

These three possibilities are mutually exclusive, with one exception: every relation

Ris both reflexive and irreflexive in Λ.(Suppes 213)

[In the prior section (10.2), we said that ordered *n*-tuples were important for relations, because often the order counts. For example, the love relation is one where we need to specify who loves whom, as often the feelings are not mutual. However, were they mutual, then the relation would be symmetric. In general terms, when there is a two-place relation, if the order of the relation can be switched for all substitutions, then it is symmetric. If for all substitutions it cannot be switched and still be true, then it is asymmetric.]

A relation

Rissymmetric in the set Aif for everyxandyinA, wheneverxRy, thenyRx. In symbols:

Rsymmetric inA↔ (x)(y)[x∈A&y∈A&xRy→ yRx].| The relation of being cousins is symmetric, but the relation of loving is not, an unfortunate fact which has been remarked upon by many novelists. The relation of being a brother is not symmetric, since any woman who has a brother affords a counterexample. (Notice that in these last three examples we have omitted explicit reference to a set in which the relations are or are not symmetric. We shall often do this when the set we have in mind is obvious, in this case the set of all people.)

R_{2}is symmetric in all three sets,A_{1},A_{2}, andA_{3}.A relation

Risasymmetric in the set Aif, for everyxandyinA, wheneverxRy, then it is not the caseyRx. In symbols:

Rasymmetric inA↔ (x)(y)[x∈A&y∈A&xRy→ –(yRx)].The relation of being a mother is asymmetric, for obvious biological reasons. On the other hand, the relation of loving is neither symmetric nor asymmetric, which fact partly accounts for the dramatic interest of the subject. If we want to show that a particular relation is neither symmetric nor asymmetric, we need to give a definite counterexample to show that it is not symmetric, and a different one to show that it is not asymmetric. (Similarly we need to give two distinct counterexamples to show that a relation is neither reflexive nor irreflexive.) For example, the relation ≤ in the set of numbers is not symmetric, since 1 ≤ 2 but not 2 ≤ 1. On the other hand, it is not asymmetric, since from 3 ≤ 3 it clearly does not follow that not 3 ≤ 3. In the first counterexample we substituted ‘1’ for ‘x’ and ‘2’ for ‘

y’. In the second, we substituted ‘3’ for both ‘x’ and ‘y’. In trying to grasp the exact sense of these definitions of properties of relations it is important to remember that thesameterm can be substituted for different variables such as ‘x’ and ‘y’.(Suppes 213-214)

[So ≤ is not symmetric, because although 3 ≤ 3 and 3 ≤ 3, that invertibility does not hold for 2 ≤ 3. It is also not antisymmetric, because although the invertibility does not hold in most cases, it does for 3 ≤ 3. However, it is always symmetric under the condition that both terms are equal to one another. The term for this sort of relation is *antisymmetric*. Another example is set inclusion, ⊆. (See Suppes section 9.3).]

The relation ≤, which is neither symmetric nor asymmetric, has a closely related property which we now define. A relation

Risantisymmetric in the set Aif for everyxandyinA, wheneverxRyandyRx, thenx=y. In symbols:

Rantisymmetric inA↔ (x)(y)[x∈A&y∈A&xRy&yRx→x=y].As already remarked, ≤ is an example of an antisymmetric relation. The relation ⊆ of inclusion is a second example. The relation

R_{2 }is antisymmetric inA_{1},A_{2}, andA_{3}. On the other hand, only in a world of completely egocentric, narcissistic people would loving be antisymmetric. Notice that vacuously every asymmetric relation is also antisymmetric. I say ‘vacuously’ because if a relation is asymmetric in a setAthen there are no two objectsxandyinAsuch thatxRyandyRx; that is, it is never the case thatx∈Aandy∈AandxRyandyRx. Hence by a | simple application of truth tables (an implication is true when the antecedent is false) it is always the case that ifx∈Aandy∈AandxRyandyRx, thenx=y.(Suppes 215)

[The next point I do not follow as well. So the loving relation is not symmetric, because it not every person loves the people who love them. It is also not asymmetric, because there are many cases of mutual love. It is furthermore not antisymmetric, because it is not the case that the only people who are in love are those who love themselves. So this is one example of a relation that for the set of humans is neither of those three possibilities. There is a little more to what Suppes is saying, so let me quote.]

It is also possible for a relation to be neither symmetric, asymmetric, nor antisymmetric in a set. An example is the relation of loving already mentioned several times. Provided a relation

Rholds between at least two (not necessarily distinct) elements ofA, the mutually exclusive and exhaustive possibilities in the case of symmetry conditions are the following:(1)

Ris symmetric inA.(2)

Ris asymmetric in A.(3)

Ris antisymmetric but neither symmetric nor asymmetric inA.(4) Neither (1), (2), nor (3) .

In order to make the conditions mutually exclusive, we had to require that

Rbe antisymmetric but not symmetric as well as not asymmetric. We leave as an exercise the construction of a relation which is both symmetric and antisymmetric in a set and holds between two not necessarily distinct elements of the set.(Suppes 215)

[A relation is transitive it seems if it carries over through a middle term.]

A relation

Ristransitive in the set Aif, for everyx,y, andzinA, wheneverxRyandyRz, thenxRz. In symbols:

Rtransitive inA↔ (x)(y)(z)[x∈A&y∈A&z∈A&xRy&yRz→xRz].The relations ≤ and ⊆ are obviously transitive. The relation of identity is also transitive. On the other hand, the relation of being a mother is not, since if

xis the mother ofyandyis the mother ofzit cannot be the case thatxis also the mother ofz.(Suppes 215)

[Let me quote the next part, as I am a little confused by it. The basic idea seems to be that in certain models the relation *R*_{2 }is vacuously valid, because the relation does not include any couples where the second member of one is identical with the first member of another. And so the conditions are not there to even test for transitivity. Recall that this was the situation:

A_{1 }= {Descartes, Mersenne},

A_{2 }= {Descartes, 5},

R_{2}= {⟨Descartes, Descartes⟩, ⟨Mersenne, Mersenne⟩, ⟨5, Λ⟩}

And furthermore recall how transitivity is defined:

Rtransitive inA↔ (x)(y)(z)[x∈A&y∈A&z∈A&xRy&yRz→xRz].

The idea might be that in the definition, we have in the antecedent of the right side of the biconditional: ... & *xRy *& *yRz .... *But *R*_{2 }does not fulfill that requirement, making the antecedent false and thus the conditional true. I will note a further confusion after quoting.]

The relation

R_{2 }is transitive inA_{1},A_{2}, andA_{3}in what may be called a vacuous sense, for there are no two ordered couples inR_{2 }which afford a test case, so to speak, of transitivity by having the second member of one ordered couple (theyofxRy) identical with the first member of another ordered couple (theyofyRz), and thereby permit the test of having the remaining two members (xandz) stand in the given relation (xRz). Let us consider a case in which such a test arises:

A_{4 }= {2, 7, Goethe}

A_{5 }= {2, 7, Edgar Guest}

R_{3 }= {⟨2, Goethe⟩, ⟨Goethe, 7⟩, ⟨Edgar Guest, 2⟩, ⟨2, 7⟩}.It should be obvious that

R_{3}is transitive inA_{4 }and not inA_{5}. ForR_{3 }to be transitive inA_{5}, we would need to add the couple ⟨Edgar Guest, 7⟩ toR_{3}. The test case for the transitivity ofR_{3 }inA_{4 }is provided by the couples ⟨2, Goethe⟩ and ⟨Goethe, 7⟩. ForR_{3}to be transitive inA_{4 }the couple ⟨2, 7⟩ must also be inR_{3}. The example ofR_{3}can be misleading. | In general we cannot decide if a relation is transitive in a given set by considering a single test case; it is often necessary to consider several cases or even to decide in a systematic way what the situation is in an infinity of cases (as for ≤).(Suppes 216)

[I will note my confusion and move on. *R*_{3 }includes ⟨2, Goethe⟩, ⟨Goethe, 7⟩, ⟨2, 7⟩. And *A*_{4 }_{}= {2, 7, Goethe}. This is how I understand *R*_{3 }being transitive in *A*_{4 }. If we make substitutions in our definition:

*2 *∈ *A*_{4 }& Goethe* *∈ *A*_{4 }& 7* *∈ *A*_{4 }& 2*R*_{3 }Goethe & Goethe*R*_{3 }7* *→ 2*R*_{3 }7.

Here, both the antecedent and consequent are true. The part that confuses me is when Suppes says, “It should be obvious that *R*_{3} is transitive in *A*_{4 }and not in *A*_{5}. For *R*_{3 }to be transitive in *A*_{5}, we would need to add the couple ⟨Edgar Guest, 7⟩ to *R*_{3}.” If my prior understanding would be right (and I am convinced it is not), then it would seem what we need for transitivity in *A*_{5} is not simply adding ⟨Edgar Guest, 7⟩, because that would not give us a transitively linked trio of couples. How is this trio transitive: ⟨Edgar Guest, 2⟩, ⟨2, 7⟩, ⟨Edgar Guest, 7⟩? (I leave out the options with Goethe, as he does not appear in *A*_{5}.) Would not a transitive trio be something more like: ⟨2, Edgar Guest⟩, ⟨Edgar Guest, 7⟩, ⟨2, 7⟩? Perhaps we can invert the term of ⟨Edgar Guest, 2⟩, and so we would already have the couples that we need. Sorry for my confusion here.]

Intransitivity is related to transitivity, but it is less important. [A relation is intransitive if for no things that it relates does the relation of a first item to a second one along with and the second one to a third imply that the relation holds as well for the first to the third. Another idea is the difference between intransitive and non-transitive. A relation can be non-transitive without being intransitive. I am not exactly sure why, but I suppose it is because for some relations, there are transitive relations between some triplets of terms but not between others.]

Related to transitivity is the less important notion of intransitivity. A relation

Risintransitive in the set Aif for everyx,y, andzinA, wheneverxRyandyRz, then it is not the case thatxRz. In symbols:

Rintransitive in

A ↔(x)(y)(z)[x∈A&y∈A&z∈A&xRy&yRz→ –(xRz)].The relation of being a mother is a familiar example of an intransitive relation. There is a general tendency, particularly in the literature of the social sciences, to confuse non-transitive and intransitive relations. Clearly a relation may be non-transitive without being intransitive.

(Suppes 216)

[A relation is connected if it relates any member to any other member.]

A relation

Risconnected in the set Aif for everyxandyinA, wheneverx≠y, thenxRyoryRx. In symbols:

Rconnected inA↔(x)(y)(x∈A&y∈A&x≠y→xRy∨yRx).From the definition it is obvious that

a relation is connected in a set when it connects any two distinct members of the set; that is, given any two distinct members, one stands in the relation to the other. The relations ≤ and < are both connected in the set of numbers. On the other hand, the relation of being a mother is not connected in the set of people, since given two people chosen at random it is seldom the case that one is the mother of the other. The relationR_{2 }is not connected in eitherA_{1},A_{2}, orA_{3}. For instance, it is not connected inA_{1}because neither ⟨Descartes, Mersenne⟩ ∈R_{2 }nor ⟨Mersenne, Descartes⟩ ∈R_{2}. However, the relationR_{3 }is connected inA_{4}, but it is not connected inA_{5}. ForR_{3 }to be connected inA_{5 }we would need to have either ⟨Edgar Guest, 7⟩ ∈R_{3 }or ⟨7, Edgar Guest⟩ ∈R_{3}.(216)

[A relation is strongly connected if it holds for any member with any other member and as well with any member and itself.]

We now introduce a property very similar to connectedness. A relation

Ris strongly connected in the setAif for everyxandyinA, eitherxRyoryRx. In symbols:

Rstrongly connected inA↔(x)(y)(x∈A&y∈A→xRy∨yRx).It should be clear that if

Ris strongly connected inAthenRis also connected inA. The relation ≤ is strongly connected in the set of all numbers. On the other hand, the relation < is not strongly connected in the set of numbers, since not 1 < 1, that is, ifx=y= 1 then neitherx<ynory<x.(Suppes 216)

Suppes now makes two general points on the topic of connectedness. consider this situation.

A_{6 }= {2, the author ofHamlet, Francis Bacon}

R_{4 }= {⟨2, Francis Bacon⟩, ⟨2, 2⟩}(Suppes 217)

*R*_{4 }is connected in *A*_{6 }if Bacon wrote *Hamlet* and it is not connected otherwise. [The relation is connected if it holds for each member with each other member. If Bacon wrote *Hamlet*, then there are only two members, which are related in *R*_{4}. But if he did not write *Hamlet*, then there are three members that are not related in *R*_{4}.] So Suppes’ point is that sometimes knowing the nature of the relations between members is an empirical matter.

The point to be noted is that different names or descriptions may be used in referring to a single individual. If Bacon had written the plays, then

Francis Bacon = the author of

Hamlet,and in describing

A_{6}we would have been referring to the man Bacon in two different ways. A final example also illustrating this last point is the following. Let

A_{7 }= {1, 2}

R_{4 }= {⟨1, 1⟩, ⟨1 + 1, 2⟩, ⟨1, 2⟩, ⟨1 + 1, 1 ⟩} .Since 2 = 1 + 1,

R_{4 }is both reflexive and symmetric inA_{7 }.(Suppes 217)

From:

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

.

## No comments:

## Post a comment