Examples of non trivial equivalence relations , I mean equivalence relations without the expression " same ... as" in their definition?

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

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

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