Equivalence Relations

We then have that R is a relation between A and B, although certainly not a very interesting one. However, we’ll use it to illustrate a few facts. First, in a relation, it’s possible for an element of A to be related to multiple elements of B, as in the case for 1 ∈ A in our example R. Also, it’s possible that an element of A is related to no elements of B, as in the case of 2 ∈ A in our example R. For a more interesting example, consider the binary relation on Z defined by R = {(a, b) ∈ Z : a < b}. Notice that (4, 7) ∈ R and (5, 5) / ∈ R. By definition, relations are sets. However, it is typically cumbersome to use set notation to write things like (1, 6) ∈ R. Instead, it usually makes much more sense to use infix notation and write 1R6. Moreover, we can use better notation for the relation by using a symbol like ∼ instead of R. In this case, we would write 1 ∼ 6 instead of (1, 6) ∈ ∼ or 2 6∼ 8 instead of (2, 8) / ∈ ∼. With this new notation, we give a few examples of binary relations on R: • Given x, y ∈ R, we let x ∼ y if x + y = 1. • Given x, y ∈ R, we let x ∼ y if x + y ≤ 1. • Given x, y ∈ R, we let x ∼ y if x = sin y. • Given x, y ∈ R, we let x ∼ y if y = sinx. Again, notice from these examples that given x ∈ R, there many 0, 1, 2, or even infinitely many y ∈ R with x ∼ y. If we let A = {0, 1}∗ be the set of all finite sequences of 0’s and 1’s, then the following are binary relations on A: