Vjylku

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

A few examples where it doesn't seem easy to find a "has the same _ as" interpretation other than by deriving it from the equivalence relation itself.

• 
  

  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 boolean function", but the situation for intuitionistic logic is not as simple).

  
  


• 
  

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

  
  


• 
  

  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 I wouldn't say it is immediately clear exactly what it would be).

  
  


• 
  

  Let two sets of natural numbers be related if one 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 $ntoinfty$.

  
  
  

  (They have the same asymptotic growth rate).

  
  

All of the above examples can be readily understood as the equivalence relation induced by a (usually larger) preorder. Here are some where such an interpretation is not quite as natural:

• 
  

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

  
  
  

  (They have the same cardinailty, but cardinality is defined through this relation. By the Cantor-Bernstein theorem this is also the same as "each has an injection into the other").

  
  


• 
  

  Let two groups be related if they are isomorphic.

  
  
  

  (Or really any kind of thing you can think of isomorphisms between. Note that for groups this is not the same as "each embeds into the other", which is a different equivalence relation).

  
  


• 
  

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

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.

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

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

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