12
$\begingroup$

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

$\endgroup$
11
  • 3
    $\begingroup$ Given a set, I can partition it into equivalence classes in any way I like, and this will define an equivalence relation. There is no need for a "same as" property. $\endgroup$ – TonyK Apr 27 '19 at 11:26
  • 9
    $\begingroup$ Ultimately, "$x$ is in the same $R$-equivalence class as $y$" is always possible $\endgroup$ – Hagen von Eitzen Apr 27 '19 at 11:31
  • 2
    $\begingroup$ What about $x\operatorname Ry$ iff $f(y)^2=f(0)f(2x)$ for some non-constant global solution $f\colon \Bbb R\to\Bbb R$ of the differential equation $f'(x)=f(x)$? $\endgroup$ – Hagen von Eitzen Apr 27 '19 at 11:34
  • 4
    $\begingroup$ But the intuitive ground of an "equivalence relation" is exactly the fact that different objects have some feature in common between them; thus, different objects are equivalent with respect to that feature exactly when the "value" of that feature is the same. $\endgroup$ – Mauro ALLEGRANZA Apr 27 '19 at 11:46
  • 2
    $\begingroup$ On the other hand, there are many "same... as" statements that aren't equivalence relations. E.g.: "X is parent of the same child as Y". $\endgroup$ – Daniel R. Collins Apr 27 '19 at 19:49

11 Answers 11

Active Oldest Votes
40
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ @HenningMakholm.Thanks a lot for these examples! $\endgroup$ – user654868 Apr 27 '19 at 13:27
  • 2
    $\begingroup$ For details on the example with groups each of which admits an injective group homomorphism into the other, see the thread If there are injective homomorphisms between two groups in both directions, are they isomorphic? where the answers give some examples. The comments to the question there link some related threads. $\endgroup$ – Jeppe Stig Nielsen Apr 29 '19 at 10:43
  • $\begingroup$ "Let two infinite sequences of natural numbers be related if each of them is a subsequence of the other." - Could this be rephrased as "... if they have the same set of subsequences"? (That is, if the set of all subsequences of $S$ is the same as the set of all subsequences of $T$.) $\endgroup$ – Tanner Swett May 20 '19 at 1:00
  • $\begingroup$ @TannerSwett: Well, that's technically true, but it feels rather like a cop-out to me, since it's still defining the property in terms of the subsequence relation. $\endgroup$ – hmakholm left over Monica May 20 '19 at 1:22
10
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @llmanKaronen. Thanks for your answer! $\endgroup$ – user654868 Apr 27 '19 at 13:28
10
$\begingroup$

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

enter image description here

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

$\endgroup$
3
  • 2
    $\begingroup$ +1 for the last sentence. $\endgroup$ – Ethan Bolker Apr 27 '19 at 11:50
  • $\begingroup$ Shouldn't that read, "There are 'as many' equivalence classes as there exist distinct images"? $\endgroup$ – Daniel R. Collins Apr 28 '19 at 7:04
  • $\begingroup$ @Daniel R. Collins In my mind, I was assuming that these pre-images (aka equivalence classes) are distinct (I am refering to the $f^{-1}(\ell)$ where $\ell$ is any element of what I have called the set $T$ of labels). $\endgroup$ – Jean Marie Apr 28 '19 at 7:09
4
$\begingroup$

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}$$

$\endgroup$
5
  • $\begingroup$ @JoseCalrlosSantos.Thanks. Could you please give a reference in which I could finfd an explanation of this interesting alternative definition of "equivalence relation" in terms of function from A to S. $\endgroup$ – user654868 Apr 27 '19 at 11:36
  • 1
    $\begingroup$ I'll add it to my answer. Please wait a few minutes. $\endgroup$ – José Carlos Santos Apr 27 '19 at 11:37
  • $\begingroup$ I've already done it. $\endgroup$ – José Carlos Santos Apr 27 '19 at 11:52
  • $\begingroup$ @JoseCarlosSantos.Thanks. $\endgroup$ – user654868 Apr 27 '19 at 11:52
  • $\begingroup$ The equivalence relation that comes from a surjection $f$ still has the "as same as" form: $a$ is equivalent to $b$ just when $f(a)$ is the same as $f(b)$. As @AnneMarie says, there's no escaping that. $\endgroup$ – Ethan Bolker Apr 27 '19 at 12:34
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ The well-ordering example is interesting, because it is not even clear from the definition that it's symmetric. Armed with my knowledge of ordinals I can easily agree that it must be an equivalence relation because it happens to coincide with "same order type" -- but is there a natural way to see it that does not go through such an obviously-symmetric concept? $\endgroup$ – hmakholm left over Monica Apr 27 '19 at 16:47
  • $\begingroup$ @HenningMakholm: I think there is no natural way, because it is necessarily non-trivial to prove that any two countable well-orderings are comparable by embedding. Wikipedia on Reverse Mathematics states that this is actually equivalent to ATR0 over RCA0. In any reasonable foundational system, I would first prove that any two well-orderings are comparable by embedding, since it quite easily yields the more general theorem that embedding is a non-strict total order on well-orderings, and that proper embedding is the strict version. $\endgroup$ – user21820 Apr 29 '19 at 7:22
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I tend to think of that as "has the same extension set as", though... $\endgroup$ – hmakholm left over Monica Apr 28 '19 at 17:18
3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Also the definition of the rationals from the integers. $\endgroup$ – Q the Platypus Apr 29 '19 at 1:27
2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Do you restrict the choice of $T$ somehow? If it can ba an arbitrary polynomial, it seems everything will be related to everything of the same degree. $\endgroup$ – hmakholm left over Monica Apr 28 '19 at 22:57
  • $\begingroup$ Oh, I forgot to mention that all polynomials have coefficients in the same field. But the degree of $T$ should not matter. For any $T$ we can use long division to obtain $T=qf+r$, where $\deg r<\deg f$, while for every $i$ we have $T(\alpha_i)=q(\alpha_i)f(\alpha_i)+r(\alpha_i)=r(\alpha_i)$. The relation is not trivial, because in particular for irreducible polynomials as above, $f\sim g$ if and only if $k[X]/(f)\cong k[X]/(g)$. $\endgroup$ – Joffysloffy Apr 29 '19 at 6:35
  • $\begingroup$ I'm confused. If I have arbitrary monic $f$ and $g$ of degree $n$ and with $n$ simple roots each, then what prevents me from using Lagrange interpolation to find a $T$ that maps the roots of $f$ to the roots of $g$? $\endgroup$ – hmakholm left over Monica Apr 29 '19 at 9:59
  • $\begingroup$ @HenningMakholm The fact that the coefficients of $T$ must also lie in $k$, whilst the roots of $f$ and $g$ need not. $\endgroup$ – Joffysloffy Apr 29 '19 at 10:08
  • $\begingroup$ You have specified that $f$ and $g$ are polynomials "with only simple roots". That seems to assume that those roots exist in the first place -- i.e. they are particular elements of the field the things happen in. Are you secretly talking about two fields? $\endgroup$ – hmakholm left over Monica Apr 29 '19 at 10:10
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I can't understand your displayed line. Please could you add some parentheses or something so that it's clear how to parse it? It seems to be strange, anyway; as it's a condition on $S$ rather than a theorem; I'd expect a $\forall$ in there somewhere. $\endgroup$ – Rosie F Apr 29 '19 at 16:25
  • $\begingroup$ @RosieF Is that better? $\endgroup$ – J.G. Apr 29 '19 at 16:31
  • $\begingroup$ Thank you! Your original had misled me because I thought that the $\iff$ and $\implies$ must be the primary (least closely binding) operators. $\endgroup$ – Rosie F Apr 29 '19 at 16:34
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ It's often used in a variant of a prisoners-with-hats puzzle, where the prisoners can guarantee survival for all but one prisoner if they can pick a choice function for the set of equivalence classes. (Though in the variants I remember the elements in the sequence, corresponding to hart colors, must be bounded). $\endgroup$ – hmakholm left over Monica Apr 28 '19 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy