An equivalence relation (denoted '~') is a relation with the following properties:

x,y,z ∈ S (Let x, y and z be elements of a set S)

  • x~x  (x is equivalent to x, the reflexive property)
  • x~y ⇒ y~x  (if y is equivalent to x, then x is equivalent to y, the symmetric property)
  • x~y ∧ y~z ⇒ x~z  (if x is equivalent to y and y is equivalent to z then x is equivalent to z, the transitive property)

The best way to understand is with some examples. Let's take the set of all integers, Z. Is < an equivalence relation? We can look at it by plugging in specific values for x, y and z. Let's try x = 1, y = 2, z = 3:

  • 1<1                          Nope.
  • 1<2 ⇒ 2<1              Not a chance.
  • 1<2 ∧ 2<3 ⇒ 1<3  Yep.

On Z, < is transitive, but neither reflexive nor symmetric, and therefore not an equivalence relation. Let's try ≠ with the values x = 2, y = 3, z = 2:

  • 2≠2                          I hope not.
  • 2≠3 ⇒ 3≠2              Tru dat.
  • 2≠3 ∧ 3≠2 ⇒ 2≠2  No.

On Z, ≠ is symmetric, but neither reflexive nor transitive, and therefore not an equivalence relation. A few caveats about this method:

  1. Plugging in specific values can be used to show that a relation doesn't have a property, but it can't be used to show that it does have a property. This is because the property must hold for any value we might plug in. If we had plugged in z = 4 in the previous example, we might have concluded that ≠ is transitive, but you can see that that not the case.
  2. The only reason we can actually plug in numbers is because we are examining the set of integers. If we had taken a different set, x, y and z could be matrices, political figures or hyperactive rabbits. While we can clearly see that 1<2 is a true statement, Bob Hope < chicken noodle soup is not a particularly easy statement to evaluate. This is because < is defined for numbers, but not necessarily for other things.

With those two things in mind, let's look at  =, where x = 1, y = 1 and z = 1:

  • 1=1                          Booya.
  • 1=1 ⇒ 1=1              Huzzah!
  • 1=1 ∧ 1=1 ⇒ 1=1  2 points.

This specific example might not be too illuminating, but let's look at it with variables:

  • x=x                        x is x
  • x=y ⇒ y=x             If x is y then y is x
  • x=y ∧ y=z ⇒ x=z  If x is y and y is z then x is z

These statements are intuitively clear and are fundamental to all of mathematics. This shows that = is an equivalence relation on Z (and on any other set, for that matter). Equivalence relations become much more interesting when you look at relations like (mod n). Let's take x = 12, y = 7, z = 2 and n = 5:

  • 12 ≡ 12 (mod 5)                                                             They're
  • 12 ≡ 7 (mod 5) ⇒ 7 ≡ 12 (mod 5)                               all
  • 12 ≡ 7 (mod 5) ∧ 7 ≡ 2 (mod 5) ⇒ 12 ≡ 2 (mod 5)  true!

Do equivalence relations have any applications in the real world? Yes: people use them every day. How many times have you held up your hand when a hotdog vendor asked you what you wanted? It's unlikely that you really wanted a human hand for lunch, but the man understood that your two extended figures were equivalent to the two hotdogs he was about to overcharge you for. Equivalence relations are the way that people are able to recognize one thing as belonging to the same group as another, even if they don't use little symbols like ∈ and ≡.

Equivalence relations are also used to define equivalence classes, which have a whole realm of niftiness of their own.

The Mathematics of Ciphers: Number Theory and RSA Cryptology, S. C. Coutinho © 1999