Examples of non trivial equivalence relations , I mean equivalence relations without the expression “ same … as” in their definition?

Question

Relations defined by formulas such as " x has the same age as y" , " x comes from the same country as y " " a has the same image under function f as b " are obviously equivalence relations, due to the presence of the expression " same ... as".

Are there many examples of equivalence relations that do not contain this " same ... as" expression and , consequently, that cannot immediately be recognized as equivalence relations?

Are there many examples of equivalence relations that , at first sight, for someone who reads their defining formula for the first time, do not at all look like equivalence relations?

What I am looking for is relations such as

" a is congruent to b ( modulo n) iff n divides a-b"

in which one does not see any " same ... as" .

Answer 1

As other answers point out it is always possible to phrase an equivalence relation as "has the same _ as" -- but sometimes the only natural way to do that is to start with the equivalence relation itself and say "same equivalence class".

An important kind of equivalence relation have definitions of the shape "one thing can be reversibly made into the other by such-and-such kind of transformation":

• Let two closed curves in some topological space be related if they are homotopic.

  (They have the same homotopy class, but homotopy classes are themselves defined through this relation).

• Let two square matrices be related if they are similar.

  (Or congruent. Or variants of these where you require that the basis change is in some particular subgroup of $GL_n$).

• Let two elements of a group be related if they're conjugates.

• Let two sets be related if there exists a bijection between them.

  (They have the same cardinality, but cardinality is defined through this relation).

• Let two groups be related if they are isomorphic.

  (Or really any kind of thing you can speak of isomorphisms between).

• Let two polyhedra be related if one can cut one into a finite number of smaller polyhedra and reassemble them to produce the other.

  (This is actually the same relation as "the two polyhedra have the same volume and the same Dehn invariant", but that is a somewhat deep result).

Alternatively you can make an equivalence relation by taking the symmetric part of a larger preorder:

• Let two formulas of the propositional calculus be related if intuitionistic logic proves them to be equivalent.

  (With classical logic this would be the same as "they define the same truth function", but the situation for intuitionistic logic is not as simple).

• Let two infinite sequences of natural numbers be related if each of them is a subsequence of the other.

  (It feels plausible that one can puzzle out an equivalent characterization with a "has the same _ as" flavor that doesn't feel unnatural, but it's not immediately clear exactly what it would be).

• Let two sets of natural numbers be related if each is Turing reducible to the other.

  (They have the same Turing degree, but that is defined through this relation).

• Let two functions from naturals to naturals be related if each is Big Oh of the other as $n\to\infty$.

  (They have the same asymptotic growth rate).

• Let two sets be related if each of them admits an injection into the other.

  (This is the same as having the same cardinality, by the Cantor-Bernstein theorem. But that is not quite trivial).

• Let two groups be related if each of them admits an injective homomorphism into the other.

  (This is not the same relation as being isomorphic!)

And here is a completely different approach:

• Let two real functions be related if they coincide on an open neighborhood of $0$.

  (They have the same germ, but that is defined through this relation).

• Choose a free ultrafilter on $\mathbb N$ and let two sequences of real numbers be related if the set of indices where they agree is in the ultrafilter.

  (This example produces an ultrapower, which is used in non-standard analysis).

Algebraic quotients are a bit of a corner case. You can define the equivalence relation as "generates the same coset as", but it is usually more natural to think of it as "the difference of the elements is in the chosen kernel".

Answer 2

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).

Answer 3

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".

Answer 4

In $\mathbb R$, consider the binary relation $R$ defined by $x\mathrel Ry$ if and only if $\lvert x-y\rvert<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 $x\mathrel Ry\iff 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,b\in A):a\mathrel Rb\iff 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}f\colon&A&\longrightarrow&S\\&a&\mapsto&\text{equivalence class of }a.\end{array}$$

Answer 5

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.

Answer 6

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.

Answer 7

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).$$

Answer 8

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

Answer 9

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_n\in\bar{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 $n\in\mathbb{N}$. For monic polynomials $f$ and $g$ of degree $n$ with only simple roots in $\bar{k}$ define the following relation:

$$f\sim g\,:\!\!\iff g=f^T\text{ for some polynomial $T$.}$$

Then $\sim$ is an equivalence relation.

Answer 10

Given any set $S$ of numbers with $$0\in S\land\forall a\in S(-a\in S)\land\forall a,\,b\in S(a+b\in S),$$$a-b\in S$ is an equivalence relation. For example, a Vitali set is constructed as follows:

• Take $a-b\in\Bbb 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.

Answer 11

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.