31
$\begingroup$

Perhaps there is not a correct way to think about it but I would want to know how others think about it. Here are my problems/questions, after my definitions:

Definition 1. Let $X$ be a set and $\sim$ be an equivalence relation on $X$. Then $[x]:=\{y \in X \mid y \sim x\}$ and $X/{\sim} := \{[x] \mid x \in X\}$.

My question could be summarized to "How should I think about $X/{\sim}$?". Consider $\mathbf{Z}/{\sim}$ with $z_1 \sim z_2$ $\iff$ $z_1-z_2$ is even. One then obtains $\mathbf{Z}/{\sim} = \{[0],[1]\}=\{\{...,-4,-2,0,2,4,...\},\{...,-5,-3,-1,1,3,5,...\}\}.$

The way I think about the set of all equivalence classes is that one collects all equivalent elements into one set for all elements and obtains the set on the very right in the example. Then one picks a "name" for each of those sets, calling it by one of its members. In the example one has the canonical choices of $[0],[1]$. If I now pick an arbitrary element $a \in \mathbf{Z}/{\sim}$, then there exists a $z \in \mathbf{Z}$ such that $a=[z]$. This is because I can simply call the set $a$ by one of its representatives, in this case $z$ or in the example above $[0]$ or $[1]$. When defining a function it then suffices to define it on all the "names" $[z]$ because I can give each object in $\mathbf{Z}/{\sim}$ one. The function being well defined then comes down to showing that it is independent of the name each object has been given. Is this a valid way to think about this concept or are there other, perhaps better ways to do so? I am not sure if I am satisfied with the way I would explain it to myself since the "giving it a name" does not really sound that rigorous. I guess one could also view this as a sort of assignment which assigns to every set of equivalent elements a member of it (which is not well defined) and then assigns to it a value such that this process is well defined.

Edit: The following is still not entirely clear to me. When defining a function from a quotient set to another set, one usually defines this in the following way: $$f: X/{\sim} \to A, \ [x] \mapsto a(x).$$ How should I think about this? Do I first choose a (arbitrary) complete system of representatives, define this function for them and then show that it is not dependent of the choice of the complete system, or do I map all $[x]$, $ x \in X$ and then realize that the images of equivalent elements are the same, meaning that the function is well defined?

$\endgroup$
5
  • 3
    $\begingroup$ Equivalence classes are pretty much the same thing as partitions. My short notes might help. $\endgroup$
    – Ivo Terek
    Commented Jul 26, 2021 at 18:53
  • 5
    $\begingroup$ I think of the quotient set as taking off my glasses, so that now what seemed like individual items look just like a blurry blob. So now instead of a bunch of individual points, I see a collection of blobs. $\endgroup$ Commented Jul 28, 2021 at 17:20
  • $\begingroup$ The basic "atoms" of mathematics are "sets" and not "elements". Thus, perhaps you want to think of the quotient $X$ as a subset of the power set of $X$. $\endgroup$
    – Kapil
    Commented Jul 29, 2021 at 12:08
  • $\begingroup$ @Kapil What about abstract categories? $\endgroup$
    – Dave
    Commented Jul 29, 2021 at 20:18
  • $\begingroup$ Responding to your edit: the answer to your final question is exactly "yes". $\endgroup$ Commented Jul 29, 2021 at 21:45

9 Answers 9

25
$\begingroup$

Frankly, the way you have worded all this seems very sound to me.

The one issue is that one cannot generally expect to be able to pick a "canonical" element. So we generally are satisfied with the ambiguity of the "name" $[x]$ for the equivalence class that contains $x$. Formally, one simply uses that the statements $[x]=[y]$ and $x \sim y$ are logically equivalent, and one remembers (just as you say) to check that all definitions based on such "names" are well-defined.

In fact, it is even somewhat problematical to assert the existence of an assignment, to each equivalence class, of a member of that class. There is a special set theory axiom devoted to the assertion that such assignments exist in complete generality: the Axiom of Choice. However, there are plenty of situations where one can construct a choice assignment by hand without that axiom, and there are plenty of situations where one does not need to bother with a choice assignment.


Regarding your latest edit, in this situation it is not necessary to choose representatives. To define a function $f : X/\!\sim \, \to A$, you can first define a function $F : X \to A$, and then you prove that $F$ has the following property:

For all $x,y \in X$, if $x \sim y$ then $F(x)=F(y)$.

You may then write down the formula $$f([x])=F(x) $$ and you are guaranteed that this formula gives a well-defined function $f : X / \! \sim \, \to A$.

$\endgroup$
17
  • $\begingroup$ Thank you for your comment! Yes, picking a canonical element is not generally possible, especially in an abstract setting, where one is not given a concrete set. However, as far as I understand, the axiom of choice should always ensures that one is able to pick one representative, when it is not possible to pick one "by hand". $\endgroup$
    – user324789
    Commented Jul 26, 2021 at 21:06
  • $\begingroup$ I edited my post with something that is still unclear to me and that I think I am not getting correctly. If you could also edit your post or write a comment regarding my edit I would be really greatful. Thanks in advance! $\endgroup$
    – user324789
    Commented Jul 27, 2021 at 20:04
  • 2
    $\begingroup$ @user324789: I added some comments about that. $\endgroup$
    – Lee Mosher
    Commented Jul 27, 2021 at 23:55
  • $\begingroup$ I have one more question, which is about how to interpret and solve the following situation. Given $X/{\sim}$ for some equivalence relation. If one wants to define a special type of functions from $X/{\sim}$ to a set $Y$, call them $A$ for example, when they satisfy $f([x])=a(x)$ for all $[x] \in X/{\sim}$ for some property $a(x)$ such that this equality is independent of the choice of represention. Would one prove this property for a function $g$ by picking a $M \in X/{\sim}$, choosing $m \in M$ and then proving it for $[m]$ or choose an arbitrary $x \in X$ and prove it for $[x]$? $\endgroup$
    – user324789
    Commented Jul 28, 2021 at 17:05
  • $\begingroup$ I would think that both methods work: In the first one I showed that all elements of the equivalence class have a representation which satisfies the equality, such that, since it is independent of representation, no matter which element is being chosen, the equation is valid. In the second method I show that no matter which representation I choose, the equality holds, since $x$ was an arbitrary element. I hope this is not confusing in any way. Once again, thank you very much for your time and effort, your answers helped me a lot so far! $\endgroup$
    – user324789
    Commented Jul 28, 2021 at 17:06
11
$\begingroup$

The idea is to view the structure through a lens which discards (or ignores for the moment) certain information. Indeed, even in colloquial language, mathematicians are prone to say things like, “Modding out by (in other words, ignoring) details like X, Y, and Z, the big story is this…”

Human language does this when we abstract, losing some information about particular dogs when we subsume them into the category dog. (This would be something like “Animals mod ‘same species’”.)

This generalizes to arrows in a category…typically you can view the image of a morphism (a subobject of the codomain) as a sort of low-resolution version of the domain. This is the content of the first isomorphism theorem in groups, rings, etc., but you can manage to do similar things in lots of categories, if you’re lucky. See Tom Leinster’s introductory book on category theory for this perspective.

It’s sort of the only trick we have in mathematics…in order to understand X, look at morphisms out of X (“shadows of X”) and morphisms into X (“things of which part of X is a shadow”).

$\endgroup$
10
$\begingroup$

The way I think about the set of all equivalence classes is that one collects all equivalent elements into one set for all elements and obtains the set on the very right in the example. Then one picks a "name" for each of those sets, calling it by one of its members.

Yes, this is exactly what we are doing.

The function being well defined then comes down to showing that it is independent of the name each object has been given.

Yes, again.

However, I suspect that you might be missing/misunderstanding the whole point of this exercise. Our intention is not just to give a name to an equivalence class that we have produced. The whole point of defining an equivalence relation, is to rigorize the concept of identifying different elements of the set.

There might be conditions where we want to consider two elements of a set as 'same', even when they are not actually equal in the normal sense. For example, in Geometry, consider triangles on a plane. Two triangles, with different vertices are not the same, in the strictest sense, as their vertices are different points. However, we can consider two congruent triangles to be the 'same', and this way of thinking might actually prove to be useful.

Similarly, in your case, we need to classify the integers just based on whether they are odd or even (and say that two integers are 'same' if they have the same parity). An equivalence relation is a way to rigorize this, as it divides our elements in to two different classes, with each class consisting of elements that we needed to be the same. Thus, $\{n | n \text{ is even} \}$ is now just a single element of your set, namely $[0]$. We do not care about the fact that it is the set of even numbers, anymore. Similarly, for odd numbers also.

Shortly, an equivalence relation generalises the concept of what it means for two elements to be equal. The quotient set just represents the original set, however, with a different notion of equality than before.

$\endgroup$
3
  • 1
    $\begingroup$ Thanks! I am aware of the fact that it generalizes equality in the way you mentioned, but that wasn't the insecurity I had with the construction. Nevertheless, its good to be reminded. $\endgroup$
    – user324789
    Commented Jul 26, 2021 at 21:12
  • $\begingroup$ I edited my post, trying to explain what remains unclear to me. If you could write a comment on it / edit your post I would be greatful. Thanks in advance for your time and effort! $\endgroup$
    – user324789
    Commented Jul 27, 2021 at 20:07
  • $\begingroup$ @user324789 I have added it as a new, independent answer instead of editing this one, as it seemed to be quite different from the answer mentioned here. $\endgroup$ Commented Jul 28, 2021 at 18:53
8
$\begingroup$

I think of it as the image of a map with the original set as the domain. For every quotient $Z/\sim$ the map $Z\to Z/\sim$ which maps every element of $Z$ to its equivalence class is such a map. And for every surjective map $Z\to Y$, we can define an equivalence relation $\sim$ where the preimage of every element of $Y$ is an equivalence class. And then $Y$ and $Z/\sim$ have the same cardinality.

This kind of thinking extends to all kinds of quotient structures. Quotients of groups, rings, vector spaces, topological spaces, etc. all come to mind. But "same cardinality" can be replaced by "isomorphic". Essentially, the quotients of a set/group/ring/... are exactly all the images of the corresponding morphisms (maps for sets, homomorphisms for groups, continuous maps for topological spaces, etc.), up to isomorphism.

$\endgroup$
1
  • 2
    $\begingroup$ Maybe it's worth pointing out that for topological spaces the topology on the image is not determined by the map and the topology on the domain since you could take a coarser topology on the image and the map would remain continuous. $\endgroup$
    – ronno
    Commented Jul 27, 2021 at 6:15
7
$\begingroup$

$X/{\sim}$ is a partition of $X$. $\sim$ is the relation between two elements in the same piece of the partition. An equivalence relation is a relation that appears in this way from a partition.

In general, you should not think of equivalence classes in "names" so much: in an abstract setting, there may be no obvious way of choosing them. In fact, being able to simultaneously choose a representative for all classes of any equivalence relation is (quite straightforwardly) equivalent to the axiom of choice. In some cases (like for integers), this is easier, but even then, the choice is never really "canonical" in any meaningful manner.

Instead, you should think of equivalence classes as subsets of the domain. They require no special names, they name themselves. It may be useful to call the odd and even integers using $1$ and $0$, but that is no better than simply calling them for what they are: the set of odd integers, and the set of even integers.

Of course, for an arbitrary set of integers, we usually have no name at all (and even less so for an arbitrary subset of an arbitrary set). But that is fine. We have no nice names for most numbers between $0$ and $1$, either.

Re: edit: when we define a map $X/{\sim}$ via a formula of the form $[x]_\sim \mapsto f(x)$ for some function of $x\in X$, it is not usual (in my experience) to think of a complete set of representatives. I can think of two more natural ways of interpreting what happens in those cases, the first one a bit more concrete, the second perhaps a bit more advanced, but also more explicit IMO:

  1. Take any $c\in X/{\sim}$, observe that it is of the form $[x]_\sim$ for some $x$, and then prove that the result $f(x)$ does not depend on the choice of $x$, i.e. the formula $\bar f(c)=f(x)$ is well-defined.
  2. Show that if $x_1\sim x_2$, then $f(x_1)=f(x_2)$, and then use the fact that the quotient map $X\to X/{\sim}$ is universal in the sense that for any map $f\colon X\to Y$ with the property that $f(x_1)=f(x_2)$ whenever $x_1\sim x_2$, there is a unique vertical arrow making the following diagram commute: $$\require{AMScd} \def\diaguparrow#1{\smash{ \raise.6em\rlap{\scriptstyle #1} \lower.3em{\mathord{\diagup}} \raise.52em{\!\mathord{\nearrow}} }} \begin{CD} && Y\\ & \diaguparrow{ f} @A\bar fAA \\ X @>>> X/{\sim} \end{CD}$$

Of course, they are all the same thing, just viewed (slightly) differently.

$\endgroup$
20
  • 1
    $\begingroup$ @user324789: It is problematic because it is not a part of the structure. The equivalence relation/partition does not know its representatives (at least, it does not know any particular set of representatives). You can choose them, but the choice is mostly arbitrary. It can be useful (particularly when you have a less arbitrary choice, as you sometimes do, if the set $X$ or the equivalence relation $\sim$ is sufficiently nice), but it is more of a byproduct than the essence. $\endgroup$
    – tomasz
    Commented Jul 26, 2021 at 22:39
  • 1
    $\begingroup$ @user324789 The problem is not just about using the axiom of choice. The thing is, making any such choice is kind of artificial, and does not provide any extra benefits at all. The problem we have with calling the same element with two different names is entirely psychological, meaning, it just need some time getting used to it. $\endgroup$ Commented Jul 27, 2021 at 14:28
  • 1
    $\begingroup$ To reiterate, even if you don't need axiom of choice to select a set of representatives, the choice is still (typically) quite arbitrary. $\endgroup$
    – tomasz
    Commented Jul 27, 2021 at 14:31
  • 1
    $\begingroup$ @user324789: I made an edit, hopefully containing what you need. $\endgroup$
    – tomasz
    Commented Jul 27, 2021 at 22:01
  • 1
    $\begingroup$ @user324789: By the way, when you use $\sim$ in LaTeX some capacity other than a binary relation (typographically, e.g. in $X/{\sim}$), you should enclose it in braces, otherwise the spacing is all messed up. $\endgroup$
    – tomasz
    Commented Jul 27, 2021 at 22:03
4
$\begingroup$

I think the best way to think about a quotient is through its properties. The construction of $X/\sim$ as a set of sets is just an implementation detail, and it can be very useful to distentangle what a quotient "is" from its implementation.

Suppose $X$ is a set and $\sim$ is an equivalence relation on $X$. A quotient of $X$ by $\sim$ is a set $Q$ along with a surjective function $q:X\to Q$ such that for all $x,y\in X$, $$x\sim y \text{ if and only if } q(x) = q(y).$$ When we've chosen a quotient, we tend to write $X/\sim$ for it and write $[x]$ for $q(x)$.

Anyway, that's it. A quotient is something that interconverts a relation with an equality.

The construction you give, setting $X/{\sim} = \{\{y\in X\mid x\sim y\}\mid x\in X\}$ and defining $q:X\to X/{\sim}$ by $q(x) = \{y\in X\mid x\sim y\}$, merely shows that there is a quotient. It's certainly a useful representation of a quotient, and it can be sometimes convenient to use this as the quotient since you can use the fact that elements of $X/{\sim}$ are sets to simplify notation. But it's limiting to think of it and only it as the quotient.

So, let's understand the ramifications of the abstract definition of a quotient.

  1. To define a function $\overline{f}:X/{\sim}\to Y$, it suffices to define a function $f:X\to Y$ and prove that for all $x,x'\in X$ with $x\sim x'$ that $f(x)=f(x')$. You usually see a definition for $f$ given indirectly as a rule for $\overline{f}$ of the form $[x]\mapsto f(x)$. This rule is shown to be "well-defined" (i.e., that $x\sim x'$ implies $f(x)=f(x')$), and thus $f$ induces this $\overline{f}$ function. Remark: You mention choosing a system of representatives to define a function on a quotient -- this actually constitutes the normal way of defining a function! A system of representatives is just a way to describe $X/\sim$ itself as a plain old set, but in terms of a subset of $X$.

  2. If $Q$ and $Q'$ are both quotients of $X$ by $\sim$, then there is a canonical bijection between them. This gives us the ability to refer to "the" quotient. The idea is that the quotient map $q':X \to Q'$ induces a map $\overline{q'}:Q\to Q'$ since $x\sim x'$ implies $q'(x)=q'(x')$, and similarly $q:X\to Q$ induces a map $\overline{q}:Q'\to Q$. The maps $\overline{q}$ and $\overline{q'}$ are inverses. By using the canonical bijection, you can replace any particular representation of a quotient by any other.

  3. Since $q:X\to Q$ is surjective, by the axiom of choice there is a subset $R$ of $X$ such that $q|_R:R\to Q$ is a bijection. This set $R$ is a system of representatives. But, it may come as a surprise, $R$ is also a quotient of $X$ by $\sim$. Define $r:X\to R$ by $r(x) = (q|_R)^{-1}(q(x))$, which satisfies the necessary properties. For example, from this point of view $\{0,1,\dots,n-1\}$ is the integers modulo $n$ with the quotient function given by reducing modulo $n$.

An application of this point of view in abstract algebra is that it's common to regard $C$ in a short exact sequence $0\to A \to B \to C \to 0$ as "the" quotient of $B$ by the image of $A$ (using the usual equivalence relation that $b\sim b'$ if $b-b'$ is in the image of $A$).


Interestingly, in a certain sense there's no difference between a quotient and a surjective function $q:X\to Q$: a surjective function always has an implicit equivalence relation, where we say $x\sim x'$ if $q(x)=q(x')$. Equivalence classes are simply given by the sets $q^{-1}(x)$, and we can recover the $X/{\sim}$ construction for this relation by taking $\{q^{-1}(x)\mid x\in X\}$. (Hence, the set of preimages of a surjective function is in canonical bijective correspondence with the codomain.)

The idea of defining a function $\overline{f}:Q\to Y$ using a function $f:X\to Y$ from this point of view is usually said using the words "$f$ factors through $q$." That is, if $f(x)=f(x')$ whenever $q(x)=q(x')$, then there is an induced function $\overline{f}:Q \to Y$ such that $f=\overline{f}\circ q$. This is absolutely the same as how it works for defining functions on a quotient.

$\endgroup$
4
$\begingroup$

Your question touches on something I used to be confused about. I am not sure whether or not you are, but I'll point it out.

Let $X$ and $Y$ be sets, let $\sim$ be an equivalence relation on $X$ and let $f : X \to Y$ be a function such that, if $x_1 \sim x_2$ then $f(x_1) = f(x_2)$. Then we would like $f$ to induce a function $g:(X/\sim) \to Y$.

The way I used to think about this was: For $S$ in $X/\sim$, choose $x \in S$ and define $g(S) = f(x)$, then show that this is independent of my choice. Indeed, intuitively, this is still how I think about it. But I was concerned because this seemed to be touching on the Axiom of Choice. Indeed, as Lee Mosher points out, the Axiom of Choice is equivalent to the condition that there is always a function $\sigma : (X/\sim) \to X$ with $\sigma(S) \in S$. It wasn't clear to me whether $g$ always existed without Choice.

From a perspective of formal set theory, here is how to define $g$ without this issue coming up, and without using Choice. Define $R \subseteq (X/\sim) \times Y$ to be the set of ordered pairs $\{ (S, y) : \ \text{there is some}\ x \in S \ \text{with}\ f(x) = y \}$. Then prove that, for each $S \in (X/\sim)$, there is a unique $y \in Y$ with $(S,y)$ in $R$. By definition, this means that $R$ is a function $(X/\sim) \to Y$.

I find the ordered pairs definition of a function very strange; my sympathies are much more with something like ETCS where functions are taken as a primitive concept. But here is some place where the ordered pairs definition helps.

$\endgroup$
4
  • $\begingroup$ Thanks for your comment. Indeed your explanation is probably one that has been written here by some others. I do not quite see, however, why your 2nd viewpoint is not including a choice of representation element, since in order to know what element $M \in X/{\sim}$ is mapped to, I would have to choose one of its members, as far as I understand. $\endgroup$
    – user324789
    Commented Jul 28, 2021 at 20:28
  • $\begingroup$ You don't define the function by making a choice. You define a relation $R$ by considering all possible choices, then you prove that $R$ is a function. $\endgroup$ Commented Jul 29, 2021 at 0:18
  • 1
    $\begingroup$ I am sure that you have left those doubts behind you a long time ago, but for others here: Using the definition of a function as a set of pairs is indeed very elegant here, but regarding AC, this is the same as first proving "for each $S$ there is a unique $y$ such that $f(x) = y$ for all $x\in S$" and then defining "g(S) is the unique $y$ such that $f(x) = y$ for all $x\in S$". In the first part you will "choose" an arbitrary element of $S$, and that sometimes trips up people, but choosing an element of one non-empty set requires no form of AC, only making many of these choices at once. $\endgroup$
    – Carsten S
    Commented Jul 29, 2021 at 12:41
  • $\begingroup$ @DavidESpeyer I think what is strange to me is that one can give the same element different "names", since a set can only contain each element once. As far as I can tell one only has to prove the well definedness, since one defines a function on a set where, in general, some elements are equal. This is perhaps why it helped me to think about it as a completely written out set, as in the RHS of my exmple $\mathbf{Z}/{\sim}$. $\endgroup$
    – user324789
    Commented Aug 1, 2021 at 11:10
2
$\begingroup$

One of the most common intuitions is to simply think of objects equivalent to each other under some equivalence relation as "the same". Obviously this is not rigorous in the sense that these objects are not equal, but so long as you remind yourself of the real meaning of "the same" (equivalence relation), you're often justified to make this simplifying mental image.

For example, when doing modular arithmetic mod $p$, let's take $p=7$ for example, it gets tiring to say things like "$2$ and $9$ are equivalent under the equivalence relation of congruence mod $7$" or "$2$ is a representative of the equivalence class containing $2,-5,9,\cdots$". Instead we just consider $2$ and $9$ to be the exact same thing in $\mathbb Z/7\mathbb Z$ even though, technically, that is not completely correct.

As another example, isomorphic groups are almost always considered to be the exact same thing for the purposes of group theory, or isomorphic rings in ring theory, etc. While there is a necessity to distinguish equality and "equivalent under a relevant equivalence relation" for rigour, amongst other reasons, thinking of them as being the same is often not that far from the correct picture, so long as you're aware what you're actually doing.

What this means is that the process of taking a quotient is basically the quotient of identifying certain points in the original object; in other words, taking different points and making them the same. One of the most clear pictorial examples is in topology: quotients of topological spaces amount to pasting different points together so that they become the same point. The same idea comes up everywhere in mathematics.

$\endgroup$
0
$\begingroup$

Regarding the Edit you had made, I believe both the ways you mention are valid ways to think about defining a function on the equivalence classes. You can either :

  1. Choose a specific representative for each class, which of course involves some arbitrary choice, and then define a function on the collection of these representative elements. This is then extended to the collection of equivalence classes (i.e., the quotient set) in the natural way; OR :
  2. Define a function on the original set in such a way that each of the element in an equivalence class goes to the same value under the function. This gives us a well defined function on the quotient set.

I have very rarely (if any) seen the first method being used, probably because it initially selects a specific (artificial, and thus maybe a bit awkward) choice, even when it finally turns out to be irrelevant (Any such choice gives the same final answer). The second method, however, I have seen being used in most places and is usually the standard way to define a function on a quotient set.

There is no conceptual problem that I can see, with doing (1) , assuming Axiom of Choice can be assumed.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .