Hcfyk

There are certainly examples of such non-trivial equivalence relations. For example, in graph theory, let $G$ be an (undirected) graph and define the relation $sim$ on its set of vertices as follows:

$a sim b$ if and only if $a$ can be reached from $b$ by traversing a finite chain of edges in $G$.

This is an equivalence relation, as can be easily shown by proving that it is reflexive, symmetric and transitive, but its definition makes no reference to any common property shared by all equivalent vertices.

Of course, as the other answers have noted, any equivalence relation $sim$ divides its domain into equivalence classes, and it's always possible to recharacterize the relation as "$a sim b$ if and only $a$ and $b$ belong to the same equivalence class." In the particular case above, the equivalence classes even have an established name: they're called the connected components of $G$.

But taking that characterization as the definition of $sim$ would make no sense, since the equivalence classes are themselves defined by the relation, and so defining the relation by the equivalence classes would be circular!

As a further demonstration of its non-triviality, it may be worth noting that the relation $sim$ defined above would not necessarily be an equivalence relation if $G$ was a directed graph: in that case, while $sim$ is still clearly reflexive and transitive, it may or may not be symmetric. To actually obtain an equivalence relation in that case, one needs to somehow adjust the definition to force it to be symmetric, e.g. by requiring the existence of a chain of edges in both directions (in which case the equivalence classes thus obtained are the strongly connected components of the graph).

As it as been remarked : when you say "same as", for example with "x' has the same age as x" is like saying "a(x')=a(x)" ; otherwise said, $x'$ and $x$ are in the same pre-image $a^{-1}(...)$, for example $a^{-1}(21)$ if both $x$ and $x'$ are 21. There are "as many" equivalence classes as there exists pre-images (see figure below).

In a reverse way, if you have an equivalence relation on a certain set $S$, it determines a partition of $S$ with cardinal $C$ ("number of classes" with possibly a generalized meaning). You will always be able to build a function $f$ from $S$ to a any set $T$ with cardinality $C$ like ${1,2,...,n}$ or $mathbb{N}$, an interval $[a,b]$, $[a,b)$ of $mathbb{R}$, etc., such that the any equivalence class is mapped onto the same element that we could call a (generalized) "label".

Thus the answer to your question : all equivalence relations can be put into the same "mould" : $x'$ is equivalent to $x$ iff $x'$ has the same "label" as $x$.

Fig. 1 : mapping "a" between elements belonging to equivalence classes in set $S$ and "labels" (set $T$). In this way equivalence classes appear as "pre-images" $a^{-1}(ell)$ of the different "labels".

In $mathbb R$, consider the binary relation $R$ defined by $xmathrel Ry$ if and only if $lvert x-yrvert<1$. It is easy to see that it is not an equivalence relation. But it is an equivalence relation if we restrict to $mathbb Z$.

Of course, you can say that it is an equivalence relation on $mathbb Z$ because then $xmathrel Ryiff x=y$. But you can't avoid something like that: given any set $A$ and any binary relation $R$ defined on $A$, $R$ is an equivalence relation if and only if there is a function $f$ from $A$ into some set $S$ such that$$(forall a,bin A):amathrel Rbiff f(a)=f(b).tag1$$In fact, if there is such a function $f$, then it is clear from $(1)$ that $R$ is an equivalence relation. And if $R$ is an equivalence relation, then let $S={text{equivalence classes of }R}$ and define$$begin{array}{rccc}fcolon&A&longrightarrow&S\&a&mapsto&text{equivalence class of }a.end{array}$$

For an example outside mathematics, the zeroth law of thermodynamics states

If two systems are in thermal equilibrium with a third system, then they are in thermal equilibrium with each other.

Since symmetry of the relation follows trivially from the definition, this establishes that thermal equilibrium is an equivalence relation. This is used to define temperature--systems have the same temperature if they are in the same equivalence class under thermal equilibrium.

Here is one way to produce equivalence relations in bulk. Given any reflexive transitive relation $R$ on a set $S$, we can define another relation $E$ on $S$ given by $E(x,y) ≡ R(x,y) ∧ R(y,x)$ for every $x,y∈S$. Then you can in fact prove that $E$ is an equivalence relation on $S$. And of course you can get a reflexive transitive relation from any reflexive relation just by taking the transitive closure.

But here is a non-trivial equivalence relation that is not obviously one in the sense of being a "can get from one to the other" kind of relation:

Define a relation $I$ on well-orderings given by ( $I(K,L)$ iff K embeds into $L$ but $K$ does not embed into any proper initial segment of $L$ ) for every two well-orderings $K,L$. Then $I$ is an equivalence relation on well-orderings.

This fact is non-trivial, because it is not true if "well-ordering" is replaced by "linear ordering". I'll leave it as exercises for you to prove the fact and find a counter-example for linear orderings.

Just adding to the list of examples, the Myhill congruence (indistinguishability) relation is used in the proof of the Myhill-Nerode theorem and minimization of finite automata:

Let $L$ be a language over some alphabet $Sigma$. Then define the relation $equiv_L$ over $Sigma*$ as $$x equiv_L y mbox{ if } forall w in Sigma^*. (xw in L leftrightarrow yw in L).$$

Well, a construction that is not so obvious is the definition of the set of integers from the natural numbers:
$$(m,n)simeq (u,v) :Longleftrightarrow m+v=n+u.$$
The equivalence class of $(m,n)$ can be viewed as the integer "$m-n$".

See also Constructing integers as equivalence classes of pairs of natural numbers

Fix a field $k$ and an algebraic closure $bar{k}$. All polynomials mentioned are assumed to have coefficients in $k$.

Let $f$ be a non-constant, monic polynomial with only simple roots in $bar{k}$. Let $T$ be another polynomial. Define the Tschirnhaus transform $f^T$ of $f$ as follows: Let $alpha_1,ldots,alpha_ninbar{k}$ be the distinct roots of $f$ (where $n=deg f$), then set

$$f^T(X):=prod_{i=1}^n(X-T(alpha_i)).$$

Fix an $ninmathbb{N}$. For monic polynomials $f$ and $g$ of degree $n$ with only simple roots in $bar{k}$ define the following relation:

$$fsim g,:!!iff g=f^Ttext{ for some polynomial $T$.}$$

Then $sim$ is an equivalence relation.

Given any set $S$ of numbers with $$0in Slandforall ain S(-ain S)landforall a,,bin S(a+bin S),$$$a-bin S$ is an equivalence relation. For example, a Vitali set is constructed as follows:

• Take $a-binBbb Q$ as the equivalence relation;


• Form the intersections of $[0,,1]$ with the equivalence classes;


• By the axiom of choice, form a set with one element of each such intersection.

This is no idle curiosity: such a set is provably non-measurable.

Consider the following:

Let two infinite sequences of natural numbers be related if they "end" in the same sequence, or in other words eventually become identical. This is equivalent to them only differing in a finite number of locations.

This was used in some weird puzzle that was also an argument against AOC, but I don't recall what exactly it was or where I found it. If anyone could provide a link, I'd be happy to give credit.