by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]
[The following is summary. My commentary is in brackets. Boldface is mine. I apologize in advance for any distracting typos or other errors.]
Introduction to Logic
Ch. 10. Relations
§10.4 Equivalence Relations
A relation is equivalent if it is reflexive (it holds for some object in relation to itself), symmetric (when it holds for one object to a second, it also holds from the second to the first), and transitive (when it holds for one object to a second, and a second to a third, it as well holds for the first object to the third one). Within a set of members, certain groupings can be formed on the basis of equivalent relations holding among all the members of a particular subgrouping. These are equivalence classes. Forming such classes can allow us to reduce a large set of data to a more manageable size, when the differences between the members within an equivalence class are irrelevant to the particular analysis being conducted.
Previously Suppes defined certain types of binary relations. He says now that there are some useful and significant combinations of these relations that he will discuss.
[The first combination will bring together reflexivity, symmetry, and transitivity. So let us review them.If a relation that relates things to themselves holds for all things, then it is reflexive.
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).
When there is a two-place relation, if the order of the relation can be switched for all substitutions, then it is symmetric.
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 is transitive if it (is as 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].
[Let us begin with an example first of an equivalence relation, namely, identity. What does the relation of identity do? It is not explicitly formulated here, but I imagine that it relates any member of a domain to itself. Since it is self-relating, it is reflexive. And since it would only be one same term, there really could not be an issue of which order we list the terms in. It would be something like aRa no matter what. So for that reason it would have to be symmetrical. But let us also suppose that we can have two names for the same object. We might say that a is identical to b. In that case it would not matter if we also say that b is identical to a, as the relation holds both ways. Thus it is also symmetric even if it has another name. (I am not sure how we would show that identity is reflexive if the names are different.) And finally, let us suppose that we have three names for the same object, a, b, and c. And suppose also that our identity relation establishes that we have aRb and bRc. That would be enough to know that aRc.]
A relation which is reflexive, symmetric, and transitive in the set A is an equivalence relation in A. The relation of identity is an equivalence relation.
[Suppes will mention some other equivalence relations, but I am not sure I understand them in each case. The first is having the same mass in a set of physical bodies. I suppose the idea is like the following. An object has the same mass as itself (reflexive), and, if an object has the same mass as another object, then that other object has the same mass as the first one (symmetric), and if a first object has the same mass as a second, and the second the same as a third, then the first has the same as the third (transitive). The next example is having the same volume. If my reasoning is correct for mass, then I think it applies the same for volume. The next example is the relation which holds between two sets if and only if they have the same number of elements. Here I am not sure how to explain the equivalence but perhaps it is just like the others. A set has the same number of members as itself (reflexive), ... etc. He says also the relation of parallelism between straight lines is equivalent. I again suppose the reasoning is like the other cases, where a line is always parallel to itself, etc. We often use the term equality to mean equivalence. I do not understand the distinction Suppes will make between equivalence and equality. He says we will use ‘equality’ as a synonym for ‘identity’ (as a matter of the identity of objects) and ‘equivalence’ as being a matter of some aspect of two objects. I cannot be sure how to clarify what Suppes is saying. I will guess he means that identity is a relation of numerical identity, while equivalence is a relation between certain features of numerically different objects. So in the case of physical bodies having the same mass, we can think of two different bodies (say of gold on the one hand and of some gas on the other, both at the same temperature) having the same mass yet having many other different properties, such as volume and so on, not to mention different spatial locations. So they are not identical at all, and thus in our terminology they are not equal, however, their masses are equivalent. Even so, I am still a little unsure how reflexivity works if we need more than one object. Perhaps the idea is that we can consider one same object twice.]
The relation of identity is an equivalence relation. The same is true of the relation of having the same mass in the set of physical bodies, the relation of having the same volume, and the relation which holds between two sets if and only if they have the same number of elements. The relation of parallelism between straight lines is another example. Both in mathematical language and ordinary language equivalence relations are often called relations of equality. Thus, as was pointed out in §5.1, lines which have the same length are called equal. To avoid the common confusion between equivalence in some aspect of two objects and identity of objects, we always use ‘equality’ as a synonym for ‘identity’.
Suppes will now discuss an important connection between identity and equivalence relations. [The next idea is very difficult for me, so you will have to read the quote to follow and interpret it for yourself. The points he seems to be making are as follows. We can show that a variety of sets are equivalent. We can then simplify the situation by showing that for certain practical purposes at hand, we can regard the equivalent cases as identical, meaning that we can reduce the number of cases we are analyzing by making certain groups of sets be identical. The example he gives is an experiment to test many coins to see if they are “fair” in the sense that the chances of flipping one side or the other is 50/50. So we conduct an experiment. Let us suppose we flip 100 coins. Each coin we flip 15 times. We will obtain for each a series of determinations of how it landed, like ⟨H, H, T ... H⟩. The problem is that now we have 100 such sets of 15-term sequences. It then becomes difficult to compare all 100. But suppose one is:
⟨H, H, H, H, H, H, H, H, H, H, H, H, H, H, T⟩
and the other is:
⟨T, H, H, H, H, H, H, H, H, H, H, H, H, H, H⟩
. Does the difference between the two matter for our experiment? No, it does not, because both show a coin that seems to have the same liklihood of flipping heads. The next part of the reasoning I am missing. But somehow we establish that certain such cases are equivalent and therefore they are identical, and in this way we reduce the number of sequences to a more manageable amount. For details on how this works exactly, please read on.]
Between the relation of identity and equivalence relations there is an intimate kind of connection which has far-reaching applications. We shall describe this connection without developing its consequences. Let R be an equivalence relation in A, and for x ∈ A, we characterize the set [x] as follows:
y ∈ [x] ↔ (y ∈ A & xRy).
The special square brackets enclosing ‘x’ are used to designate the R-equivalence class of x in A; in other words, [x] is the R-equivalence class generated | by x. We may easily show that each element of A belongs to exactly one R-equivalence class in A. Furthermore, we have the important result that
(1) [x] = [y] if and only if xRy.
The general philosophical significance of (1) is that it formulates a principle of abstraction: objects which are equivalent in some respect generate identical classes.
One of the reasons for the importance of this principle of abstraction is that application of it can often lead to a substantial reduction in the number of entities being considered by passing from objects to equivalence classes of objects. For example, suppose we are comparing the apparent fairness of a large number of coins by flipping each of them fifteen times. The complete result of our test of each coin may be represented by an ordered 15-tuple. ‘H’ is used to show that the outcome of a flip was heads and ‘T’ to show that it was tails. Thus, for example,
⟨H, T, H, ... , H⟩
indicates that the first, third, and fifteenth flips came out heads and the second flip tails. Since the outcome of each flip is either H or T, there are 215 (= 32,768) possible outcomes of the test, i.e., 32,768 ordered 15-tuples of the kind described. Developing a theory for comparing these 32,768 possible outcomes seems rather complicated. But an essential simplification suggests itself. In deciding on the fairness of a coin we are really only interested in the ratio of the number of flips with outcome heads (or tails) to the total number of flips. For example, if a coin came up heads fifteen times in a row we would be strongly inclined to conclude that it was not a fair coin, i.e., a coin with respect to which the chances of heads or tails on a flip were about even. Since we are interested only in the ratio of heads to the total number of flips, we may “throw away” the information concerning in what order H and T occurred. We define two of our ordered tuples as ratio-equivalent if H occurs the same number of times in each. Thus,
⟨H, H, H, T, T, T, T, H, T, T, T, H, H, T, T⟩
⟨T, T, H, T, H, H, T, T, T, T, H, H, T, H, T⟩
are ratio-equivalent since six H’s occur in both the ordered 15-tuples. It is obvious that there are 16 ratio-equivalence classes corresponding to 0, 1, 2, . . . , 15 occurrences of heads, and the small number of such equivalence classes compares impressively with the 32,768 ordered tuples. In particular, it is possible to develop rules for accepting or rejecting a coin as fair simply according to which equivalence class its test belongs to. The actual construction of such rules is beyond the scope of our discussion, since it is essentially a problem of statistics rather than logic.
Suppes, Patrick. Introduction to Logic. New York: Van Nostrand Reinhold / Litton Educational, 1957.