Suppes (10.3) Introduction to Logic, “Properties of Binary Relations’, summary

 

by Corry Shores

 

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

[Central Entry Directory]

[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 R is reflexive in the set A if for every x in A, xRx (i.e., ⟨x, x⟩ ∈ R):

R reflexive in A ↔ (x)(x ∈ A → xRx).

 

A relation R is irreflexive in the set A if, for every x in A it is not the case that xRx:

R irreflexive in A ↔ (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 R is symmetric in the set A if for every x and y in A, whenever xRy, then yRx:

R symmetric in A ↔ (x)(y)[x ∈ A & y ∈ A & xRy → yRx].

 

A relation R is asymmetric in the set A if, for every x and y in A, whenever xRy, then it is not the case yRx:

R asymmetric in A ↔ (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 R is antisymmetric in the set A if for every x and y in A, whenever xRy and yRx, then x=y:

R antisymmetric in A ↔ (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 R is transitive in the set A if, for every x, y, and z in A, whenever xRy and yRz, then xRz:

R transitive in A ↔ (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 R is intransitive in the set A if for every x, y, and z in A, whenever xRy and yRz, then it is not the case that xRz:

R intransitive 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 R is connected in the set A if for every x and y in A, whenever x ≠ y, then xRy or yRx:

R connected in A ↔ (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 R is strongly connected in the set A if for every x and y in A, either xRy or yRx:

R strongly connected in A ↔ (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 R is reflexive in the set A if for every x in A, xRx (i.e., ⟨x, x⟩ ∈ R). In symbols:

R reflexive in A ↔ (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₁ = {Descartes, Mersenne},

A₂ = {Descartes, 5},

and

R₂ = {⟨Descartes, Descartes⟩, ⟨Mersenne, Mersenne⟩, ⟨5, Λ⟩},

then R₂ is reflexive in A₁ but is not reflexive in A₂, since the ordered couple ⟨5, 5⟩ is not a member of R₂. 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 R is irreflexive in the set A if, for every x in A it is not the case that xRx. In symbols:

R irreflexive in A ↔ (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₂ is not reflexive in A₂, but it is also not irreflexive in A₂, because ⟨Descartes, Descartes⟩ ∈ R₂. Consider:

A₃ = {5, Elizabeth I}.

It is clear that R₂ is irreflexive in A₃. From the example of R₂ and A₂, it should be obvious that for any relation R and set A there are three possibilities:

(1) R is reflexive in A.

(2) R is irreflexive in A.

(3) Neither (1) nor (2).

These three possibilities are mutually exclusive, with one exception: every relation R is 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 R is symmetric in the set A if for every x and y in A, whenever xRy, then yRx. In symbols:

R symmetric in A ↔ (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₂ is symmetric in all three sets, A₁, A₂, and A₃.

A relation R is asymmetric in the set A if, for every x and y in A, whenever xRy, then it is not the case yRx. In symbols:

R asymmetric in A ↔ (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 rela­tion ≤ 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 the same term 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 R is antisymmetric in the set A if for every x and y in A, whenever xRy and yRx, then x=y. In symbols:

R antisymmetric in A ↔ (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₂ is antisymmetric in A₁, A₂, and A₃. 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 set A then there are no two objects x and y in A such that xRy and yRx; that is, it is never the case that x ∈ A and y ∈ A and xRy and yRx. Hence by a | simple application of truth tables (an implication is true when the antecedent is false) it is always the case that if  x ∈ A and y ∈ A and xRy and yRx, then x=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 R holds between at least two (not necessarily distinct) elements of A, the mutually exclusive and exhaustive possibilities in the case of symmetry conditions are the following:

(1) R is symmetric in A.

(2) R is asymmetric in A.

(3) R is antisymmetric but neither symmetric nor asymmetric in A.

(4) Neither (1), (2), nor (3) .

In order to make the conditions mutually exclusive, we had to require that R be 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 R is transitive in the set A if, for every x, y, and z in A, whenever xRy and yRz, then xRz. In symbols:

R transitive in A ↔ (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 x is the mother of y and y is the mother of z it cannot be the case that x is also the mother of z.

(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₂ 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₁ = {Descartes, Mersenne},

A₂ = {Descartes, 5},

R₂ = {⟨Descartes, Descartes⟩, ⟨Mersenne, Mersenne⟩, ⟨5, Λ⟩}

And furthermore recall how transitivity is defined:

R transitive in A ↔ (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₂ 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₂ is transitive in A₁, A₂, and A₃ in what may be called a vacuous sense, for there are no two ordered couples in R₂ which afford a test case, so to speak, of transitivity by having the second member of one ordered couple (the y of xRy) identical with the first member of another ordered couple (the y of yRz), and thereby permit the test of having the remaining two members (x and z) stand in the given relation (xRz). Let us consider a case in which such a test arises:

A₄ = {2, 7, Goethe}

A₅ = {2, 7, Edgar Guest}

R₃ = {⟨2, Goethe⟩, ⟨Goethe, 7⟩, ⟨Edgar Guest, 2⟩, ⟨2, 7⟩}.

It should be obvious that R₃ is transitive in A₄ and not in A₅. For R₃ to be transitive in A₅, we would need to add the couple ⟨Edgar Guest, 7⟩ to R₃. The test case for the transitivity of R₃ in A₄ is provided by the couples ⟨2, Goethe⟩  and ⟨Goethe, 7⟩. For R₃ to be transitive in A₄ the couple ⟨2, 7⟩ must also be in R₃. The example of R₃ 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₃  includes ⟨2, Goethe⟩, ⟨Goethe, 7⟩,  ⟨2, 7⟩. And A₄  = {2, 7, Goethe}. This is how I understand R₃ being transitive in A₄ . If we make substitutions in our definition:

2 ∈ A₄  & Goethe ∈ A₄  & 7 ∈ A₄  & 2R₃  Goethe & GoetheR₃ 7 → 2R₃ 7.

Here, both the antecedent and consequent are true. The part that confuses me is when Suppes says, “It should be obvious that R₃ is transitive in A₄ and not in A₅. For R₃ to be transitive in A₅, we would need to add the couple ⟨Edgar Guest, 7⟩ to R₃.” 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₅ 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₅.) 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 R is intransitive in the set A if for every x, y, and z in A, whenever xRy and yRz, then it is not the case that xRz. In symbols:

R intransitive 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 R is connected in the set A if for every x and y in A, whenever x ≠ y, then xRy or yRx. In symbols:

R connected in A ↔ (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 relation R₂ is not connected in either A₁, A₂, or A₃. For instance, it is not connected in A₁ because neither ⟨Descartes, Mersenne⟩ ∈ R₂ nor ⟨Mersenne, Descartes⟩ ∈ R₂. However, the relation R₃ is connected in A₄, but it is not connected in A₅. For R₃ to be connected in A₅ we would need to have either ⟨Edgar Guest, 7⟩ ∈ R₃ or ⟨7, Edgar Guest⟩ ∈ R₃.

(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 R is strongly connected in the set A if for every x and y in A, either xRy or yRx.  In symbols:

R strongly connected in A ↔ (x)(y)(x ∈ A & y ∈ A → xRy ∨ yRx).

It should be clear that if R is strongly connected in A then R is also connected in A . 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, if x = y = 1 then neither x < y nor y < x.

(Suppes 216)

 

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

A₆ = {2, the author of Hamlet, Francis Bacon}

R₄ = {⟨2, Francis Bacon⟩, ⟨2, 2⟩}

(Suppes 217)

R₄ is connected in A₆ 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₄. But if he did not write Hamlet, then there are three members that are not related in R₄.] 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₆ 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₇ = {1, 2}

R₄ = {⟨1, 1⟩, ⟨1 + 1, 2⟩, ⟨1, 2⟩, ⟨1 + 1, 1 ⟩} .

Since 2 = 1 + 1, R₄ is both reflexive and symmetric in A₇ .

(Suppes 217)

 

 

From:

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

  

.