Equivalence relation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The equivalence relation is a mathematical relation that is symmetric, transitive and reflexive. Using this relation, it is possible to partition a set into (non-empty) subsets, which are called equivalence classes. As an example, look at the animals on a farm: We now define a relation: we say that two animals are related, if they belong to the same species. That way, a cow is related to an ox, but not to a chicken. The relation we just defined is an equivalence relation:

  • It is reflexive: each animal is of the same species as itself
  • It is symmetric: if the cow is the same species than the ox, then the ox is also the same species as the cow.
  • It is transitive: if a cow and a bull, and a bull and an ox are of the same species, they are all of the same species of cattle

In this example, all cattle form an equivalence class.