# What's the point of learning equivalence relations?

I teach an introductory discrete mathematics course at a community college to math and computing majors, usually in their sophomore year. As is common, it's partly used as the first foray into formal and proof-based math courses in the case that they later proceed to a bachelor's program.

Probably the most abstract topic that we get to are binary relations, culminating in identifying and proving that things are equivalence relations. This is particularly hard for our students, and perhaps once or twice I've had students ask the question, "What's the point of learning equivalence relations?"

Now, obviously I'm familiar with reading more advanced math texts, being told that something is an equivalence relation, and grokking the rather large number of facts that have just been communicated. But I'm accustomed to being able to answer these "why this?" questions pretty well with specific applications in most cases, whereas in this case I'm drawing a total blank. The book has no example of applications in this case (and I'm not sure what any such would look like).

So: What's a good response to a student in their first semi-formal discrete math course asking, "What's the point of learning equivalence relations?" Are there any good applications or use-cases where knowing something is an equivalence relation makes some particular work feasible or easier in some sense (esp. in computing)?

(Side note: Up until this semester, I had one lecture on n-ary relations in the context of DBMS's, but I've had to cut that out due to credit-hour reductions in our program. Even when I had that there wasn't any explicit connection to the equivalence relation concept.)

• Do you learn modular arithmetic in these courses? Knowing that congruence is an equivalence relation, and that the operations of addition and multiplication respect this equivalence relation, is essential and readily understandable. Arguing that 6^n-1 is a multiple of 5 is a challenging induction problem without these facts, but it a trivial induction problem with these facts, for instance. Sep 8, 2020 at 18:10
• @StevenGubkin: We do, briefly. But I fear that response would be too abstract to satisfy my students on this question. (E.g., I also get "why do we learn modular arithmetic?", and at least with that I can point to concrete applications like hash values, pseudorandom numbers, check digits). And no induction problem is trivial for my students, to most they're all equally opaque (e.g., most leave it blank on final). Sep 8, 2020 at 19:45
• I think making the connection between equivalence relations and modular arithmetic is vital. I haven't taught the class often enough yet to have a meatier response, but maybe I can come back to this question in a year or two... Sep 9, 2020 at 4:13
• You might get some good examples from computer science in the context of a functional programming language, such as Scala. It may not be at the programming level of someone just starting out, but it may give them something to look forward to as their CS career progresses. Sep 9, 2020 at 16:53
• The rational and real numbers are often defined via equivalence relations. Sep 10, 2020 at 6:17

Perhaps emphasize to students the spirit of equivalence relations. They partitions sets into equivalence classes--cutting down the amount of cases necessary to prove something.

To illustrate this, take a geometry example first. "Is similar to" is an equivalence relation on the set of regular polygons (I'll omit a proof here). Now say I need to prove something about squares. If I don't use the "square" equivalence class, then I have to consider every possible square and make a general proof. But instead, if I frame my proof in such a way that respects the "is similar to" relation, then I no longer need to prove it for all squares, but just any single one. This cuts down the amount of cases significantly.

In programming, we should constantly test our code in as many conditions as possible. But for many functions, there are a potentially infinite number of inputs--far too many to run unit tests for in reasonable time. Instead, if we look at our tests through the lens of equivalence classes, we can usually cut down our test cases into a finite (and often small) number of cases, and still feel confident that it will run correctly in all contexts. Granted, this often more easily said than done, but it usually leads to more coherent unit tests and frankly more coherent code.

Say, going back to our regular polygons example, I am working on a geometry library. I have a function that calculates the angles of a regular polygon. Without thinking about equivalence classes, I would have to test EVERY square, EVERY regular pentagon, EVERY regular hexagon, etc... This is an uncountably infinite number of tests. No one has enough compute or patience for that.

Instead, since I know that angles are respected by the equivalence classes under similarity (since that's part of the definition of similarity), I only need to check one of each shape, and I can be confident that it will work for every instance of that similar shape.

Even better, we can actually use that mindset to guide our coding process! If we know that similarity preserves angle, we can simply acknowledge that in our code. Instead of calculating the angles between lines (which is complicated in general), we can simply use the properties of squares/pentagons/whatever, which is a much simpler process. If we're even more clever, we can reduce this down to a single arithmetic statement.

So, equivalence relations partition sets of inputs into cases. In pure math, these cases guide our proofs, but even in coding, they can guide our testing. If we start through this lens, instead of retroactively applying it, it can even simplify our code.

• Backing up a step, equivalence relations create equivalence classes / partitions. Sep 9, 2020 at 4:13
• The student in me really wants to see what that proof would look like. I never had the question the OP poses answered when I took theoretical concepts of calculus, basically one step before intro to analysis. Sep 9, 2020 at 17:34
• @OwenReynolds Excellent point! I edited the beginning of the answer to make that clarification. Sep 9, 2020 at 21:23
• @gen-ℤreadytoperish The proof isn't terribly difficult. Similarity just preserves equality of angles and further states that there is some proportionality between corresponding sides. Since equality is an equivalence relation (quite trivially), we know that the equality of angles must be transitive, symmetric, and reflexive. The other half requires more work, especially if you don't want to use linear transforms. But the gist is: transitivity comes from the fact that proportionality is transitive. It's symmetric because it's invertible. And it's reflexive because the constant can be 1. Sep 9, 2020 at 21:28
• I've selected this as the approved answer, because (a) it's most upvoted, and (b) "Perhaps emphasize to students the spirit of equivalence relations" is exactly the crux of how I've decided to improve my lecture (reflecting on natural-language meaning of the phrases; see my answer below), among elements taken from other answers. It almost pains me to select a single answer, because so many interesting ones keep getting posted. I could imagine some really amazing answer being added later (maybe with a very concrete real-world example) and shifting the selection to that. Sep 11, 2020 at 4:40

In general, all applications are going to be more of the "here is what we have to check to make sure that our algorithm/theory/definitions work". We don't usually encounter practical problems where we're given a completely arbitrary relation and have to check if it's an equivalence relation.

Here are some of the more common equivalence relations that we might care about:

• In graph theory, "being connected by a path" is an equivalence relation; proving that lets us say that graphs are divided into equivalence classes called "connected components". This one might be the most relevant for students focused on computer science.
• A variant of this is communicating states in Markov chains, which also tell us a lot about the structure of a Markov chain, and save us work determining which states are transient/recurrent.
• Asymptotic analysis has a couple of equivalence relations: the stricter one where $$f,g$$ are equivalent if $$f \sim g$$ or $$\lim_{x \to \infty} \frac{f(x)}{g(x)} = 1$$, and the looser one where $$f \in \Theta(g)$$. This might also be interesting for computer science applications.
• In linear algebra, matrices being similar is an equivalence relation; when we diagonalize a matrix, we choose a better representative of the equivalence class.
• Various quotient objects in abstract algebra and topology require having equivalence relations first. That's in particular what happens with modular arithmetic. But this might be too abstract to make good examples.
• Sometimes we use them in definitions to say "there are many ways to arrive at this thing; we don't care about which way we do it, because they're all basically the same". That's what happens when we define real numbers via Cauchy sequences, or the fundamental group via closed loops.

Maybe it's equally important to look at examples of things we wish were equivalence relations, but aren't. For example, in a directed graph, the relation "$$v \sim w$$ if there is a path from $$v$$ to $$w$$" is not symmetric; if we try to patch it to "$$v \sim w$$ if there is a path from $$v$$ to $$w$$ or a path from $$w$$ to $$v$$" then it's not transitive. As a result, it's much harder to take a directed graph and solve the problem of which vertices can reach which other vertices, compared to the undirected case.

Additionally, I think the definition of equivalence relations looks unmotivated, not just because students don't see any direct applications, but because the three properties (reflexive, symmetric, and transitive) seem arbitrary.

So it's worth explaining that the reason these three properties exist is not just "these are the three properties of $$=$$ that we liked". They are exactly the things we need to check in order to be able to group things into equivalence classes, and that's the motivation for asking for them.

Admit honestly that pretty much nobody cares about reflexivity, since you can always "patch" it by replacing relation $$R$$ with relation $$R'$$ where $$a \mathrel{R'} b$$ whenever $$a \mathrel{R} b$$ or $$a=b$$; also, it almost follows from the other two properties, except in the awkward case where some object is not related to any other object, not even itself.

For some students, it might help to mention that there's alternate (equivalent) definitions of equivalence relations. Hilbert used a two-property definition where we first check that $$a \mathrel{R} a$$ for all $$a$$, then check that if $$a \mathrel{R} b$$ and $$b \mathrel{R} c$$, then $$c \mathrel{R} a$$, which is a concise but not very clear way of getting symmetric and transitive at once.

• +1 for the answer, and I wish I could +1 again for the addendum! Sep 9, 2020 at 20:31
• +1 Thanks for writing this. I'll just say I did a double-take at "pretty much nobody cares about reflexivity", because I feel like I've seen a large number of proofs that start with reflexivity and then start manipulating both sides to the relation/equation we desire. Sep 11, 2020 at 2:34
• @DanielR.Collins I guess there's different notions of "cares". We want reflexivity to be true. In formal proofs, it's pretty important because it's the only one of the three properties that tells us something "for free". But in definitions, it's often the case that we define $a \mathrel{R} b$ to be "some nice relationship between $a$ and $b$ holds, or $a=b$" just to make it an equivalence relation. Sep 11, 2020 at 16:02

# Equality vs. Identity

Alexei touched on this topic by mentioning hash tables, but I would like to spell it out more explicitly, because this is a critical and fundamental topic in software engineering, and essential for every programmer to know and understand.

Every high level programming language has a mechanism for comparing two values for "equality". But every PL with reference types must also provide one more ability: comparing whether two references point to the same object. In Java, D, C#, Kotlin, and many other similar languages, the == operator tests for identity (do these two references point to the same address?), while the equals() method tests for equivalence (may I regard these expressions as having the same value?). Like I said, understanding this distinction and when to use which operator is absolutely essential to writing correct code.

A non-programmer (especially a mathematician, perhaps), might assume that == is the more useful function, because pure math and common experience can usually make do with identity (all instances of the number $$\pi$$ are identical in math). The reality is that in the majority of production code, equals() far outnumbers ==. That's because the majority of objects in production code are mutable and lack referential transparency.

# Strings

To understand the above, we need look no further than strings. In Java, strings are immutable, but still require comparison via equals() rather than ==. To see why, consider this Java code fragment:

void areEqual() {
String a = "hello";
String b = "hello";
if (a == b) System.out.println("Same");
else System.out.println("Different");
}


Now, as the naive reader expects, the function above will print Same, but only because the strings in question are literals, and thus, the compiler will generate code which causes a and b to point to the same memory address. One small change will break this code:

void areEqual() {
String a = "hello";
String b = "hel";
String c = b + "lo";
if (a == c) System.out.println("Same");
else System.out.println("Different");
}


This function will print Different, even though we could print out a and c and they would look the same to anyone who stared at them. In this case, we defeat the string interning mechanism, and c resolves to a different object than a. Under the covers, the first example might produce something like: a == 0x1234abcd; b == 0x1234abcd while the second example might produce: a = 0x1234abcd; b == 12349876. So the values of the strings are equivalent, but the addresses of the strings are quite distinct.

This is important, because if one has a container of strings, and one wishes to see if some new string exists in that container, in virtually every real-world program, the programmer wants to know if an equivalent string exists in the container (i.e., an object in the same equivalence class, or, the same sequence of characters), rather than the identical string.

The discussion above might lead one to assume that identity vs. equality is just an esoteric implementation detail of programming languages with reference semantics, and that we can simply switch to calling equals() everywhere and be done with it. But it's not so simple. Suppose we have a shopping website, and a large catalog with millions of items and their descriptions. An item description might be a surprisingly complex composite object, consisting of a short text blurb in addition to structured data about the item (its weight, shipping box dimensions, manufacturer, etc.). However, there may be duplicates within the catalog. When this happens, we can save precious memory by reusing the same object when two descriptions are equivalent even though they are not identical. Now, if we have defined the naive equals() method on the class ItemDescription which compares every field one by one, then this seems like another boring application of equals().

But it's not that simple. You see, data like this will almost certainly come from a database, and any good DBA will demand that every table contain a primary key, which will usually be a synthetic autoincrement value. So, it is very, very likely, that there will exist two sets of records in the item catalog which are the same up to their PKey. An app which stores huge portions of the catalog does not want to waste memory storing these duplicates separately. Thus, it is useful to define an additional equality operator that detects this "equality-up-to-pkey". That is, we wish to traffic in the equivalence class of ItemDescription - PKey. One way to do this would be to define another method on the ItemDescription class which implements this equivalence class, and use that comparator on a collection of unique ItemDescription. This will ensure there is only one copy of each equivalent ItemDescription in the in-memory collection. This kind of equivalence class occurs frequently in the industrial programming world.

# Inheritance

One of the defining characteristics of Object-Oriented Programming (OOP) is the mechanism of "inheritance". When a type Child "inherits" from a type Parent, we say that a Child "is-a" Parent. This notion is neither identity nor the naive field-by-field notion of equivalence that is commonly assumed. The "is-a" relation really means: "can be substituted for". That is, any code which expects a value of type Parent will gladly accept a value of type Child. But what does that mean? What if the Child class introduces new fields which don't exist in Parent? Well, those fields are ignored. When you pass a Child in as a Parent, only the Parent portion of the object is considered.

Here is a small code example:

class Animal {
protected String sound = "<gurgle>";
public Animal(String sound) {
this.sound = sound;
}
...
}
class Bird extends Animal {
int wings = 2;
public Bird() {
super("<tweet>");
}
...
}
class Pigeon extends Bird {
String trait = "annoying";
...
}
class Dog extends Animal {
int legs = 4;
public Dog() {
super("<woof>");
}
...
}
void tickle(Animal animal) {
System.out.println("You tickle the animal, and it goes: " + animal.sound);
}


Note that you are free to pass an Animal, Bird, Pigeon or Dog to tickle(). It will accept any of them. This fact alone illustrates that "is-a" defines an equivalence class over types, given that the type system requires an argument's type to match the type of the parameter. Given that almost every major programming language with mutable data supports OOP features, one could say that equivalence classes are again pervasive in the type system.

# Conclusion

There are many more examples of equivalence classes used commonly within professional software engineering, but hopefully this is enough to get you started.

• +1 I'm pretty sure this is the most concrete-example answer posted so far, thanks for this. I'm thinking on how exactly I can work some of this into the course in limited time. Sep 10, 2020 at 6:40
• I suppose you have more than twenty years of experience doing software dev. Nowadays kids prefer composition over inheritance even when inheritance would do fine. In your case, your animals have wings, legs and trait split into different classes instead of bundling them all into a map of traits, so your dog cannot be annoying. Sep 10, 2020 at 22:27
• @RustyCore I agree that there are good reasons to prefer composition, but I was trying to pack as much info as possible into the smallest example while making many necessary sacrifices to good software engineering practices. Sep 10, 2020 at 23:00
• I thought someone would mention equals vs equalsIgnoreCase as an easy example of defining several equivalence relations on the same set, which can more easily be explained without reference to programming. But if we use programming as the motivation, this makes sense. Sep 11, 2020 at 0:30
• @MarcGlisse I think that would make a great answer! Technically, any kind of search, e.g., regex, would also define an implicit equivalence relation. I think you could expand that into a pretty nice answer. Sep 11, 2020 at 4:28

If you have looked at modular arithmetic, then one possibility is: Give/recall some example of an algebraic argument in modular arithmetic; then point out that the argument is implicitly relying on the fact that congruence is an equivalence relation. So then you can explain: equivalence relations are designed to axiomatise what’s needed for these kinds of arguments — that there are lots of places in maths where you have a notion of “congruent” or “similar” that isn’t quite equality but that you sometimes want to use like an equality, and “equivalence relations” tell you what kind of relations you can use in that kind of way.

Finding a good specific example argument will depend on what you covered in modular arithmetic. Almost any algebraic argument will use “chains of equalities”, and so illustrate transitivity. Going through the proofs you cover, it’s pretty likely that you can find one that uses symmetry. Reflexivity is much less often used — but if your example illustrates two out of the three defining properties, then it will serve well enough as a “motivational application”.

• I actually have a note to myself in my lecture addendum on this fact. But: unfortunately the time constraints in my class are so severe that the lecture section on modular arithmetic is exactly two slides that get maybe 10 minutes total, followed by some exercises. So I'm guessing that my students have a sketchy enough relation to that to not really hit them in the gut in any way. Sep 10, 2020 at 19:04

The notion of equivalence relation is one of the basic building blocks out of which all mathematical thought is constructed. (Paul Halmos)

• What's the point of learning equivalence relations?

The concept of equivalence relation is a generalization of the concept of equality. Why is it good to know that $$a$$ is equal to $$b$$? Because, in this case, all we know about $$a$$ is also true for $$b$$, and vice versa (they are the same thing!). Analogously, why is it good to know that $$a$$ is equivalent to $$b$$? Because, in the case, "almost" all we know about $$a$$ is also true for $$b$$, and vice versa (they are "almost" the same thing!). However, for any practical purposes, "almost" in this context is as good as if it was "all". Why? Because, when it is needed, the equivalence relation is defined in a way that the elements of the equivalence class differ only with respect to irrelevant aspects (anyone we choose in the class will do the job).

Example. If we are interested only in the area below the graph, we can regard the functions f(x)=\left\{\begin{aligned} 1,&&0\leq x\leq 1\\ 2,&&1< x\leq 2 \end{aligned}\right.\qquad \text{and}\qquad g(x)=\left\{\begin{aligned} 1,&&0\leq x< 1\\ 2,&&1\leq x\leq 2 \end{aligned}\right. as being the same function because a single point does not change the area. In this case, we define $$f\sim g$$ if $$f(x)\neq g(x)$$ only for a finite number of values of $$x$$. This seemingly simple idea is actually used in more advanced contexts.

[What I have in mind here is that $$\int f g$$ is an inner product on the space of (equivalence class of) piecewise continuous functions (we can use it in the study of Fourier series (which can be used to solve partial differential equations (which can be used to solve "real-world" problems (thus we have an indirect/artificial application here. Of course, it is not satisfactory for the student but reflect the relevance of the subject)))).]

• What's a good response to a student ... (esp. in computing)?

You could try to elaborate on the last example of Teaching equivalence relations using collaborative activities by Janet E. Mills:

In the area of coding theory, one needs to know if two codes are doing essentially the same thing. The distance between code words is a critical factor in analysing a code. Let $$S$$ and $$T$$ be subsets of $$Z^n_2$$ (i.e. codes). Define $$\sim$$ on $$Z^n_2$$ by by $$S \sim T$$ if and only if there exists a one-to-one onto linear function $$\varphi:S\to T$$ such that $$d(x, y) = d(\varphi(x), \varphi(y))$$ for all $$x, y$$ in $$S$$, where $$d(x, y)$$ is the number of nonzero components in $$x- y$$ (or the number of digits where $$x$$ and $$y$$ differ, called the Hamming distance).

You could to try to define what a code is (mention message, encoder, channel, noise, decoder), define Hamming distance, define equivalence of codes (you can use permutation if $$\varphi$$ is too abstract), exploit the fact that equivalent codes are "the same" (though "different"), for example, have the same error correction capability. Maybe this situation could be sufficiently simple, interesting and convincing.

• +1 Great quote. While we don't have time to add new subject matter, we do at least have Gray codes and Huffman codes in the textbook, so maybe I could at least refer to those and scope out the possible analysis. Sep 10, 2020 at 13:47

Dictionary/hash table relies on equivalence to bucketize items.

So knowing that one would never try to build a hashtable by a distance between cities (objects on a plane): distance is not transitive.

In real programming there is another common way to violate equivalence which is sort of implied in pure math/CS: "a == b hence in 5 minutes a == b too" can broken very easily. This is again directly leads to requirements of dictionary/hash table - equivalence between items must never change while items in that data structure.

Rotation of a physical object or an observer in most cases considered to be equivalent by module 360 (or 2*Pi whatever you like). Combined with knowledge that addition and multiplication preserves that relationship one can safely say that both spinning 5 times by 361 degree or 5 times by 721 degree would result in an equivalent position. It is somewhat intuitive for +5 degrees, but far less obvious for multiplying. As result one does not need to normalize rotation on every step of they code:

  angle = prevAngle * 4 + 32 + otherAngle


instead of something like following after every step of the operation:

  normalizedOther = otherAngle < 0 ?
otherAngle + 360 : otherAngle > 360 ?
otherAngle - 360 : otherAngle;

• Hash tables is an excellent connection that I haven't explicitly connected before. This could actually be turned into a great exploratory activity using Python dictionaries and custom classes, defining eq and hash. (Assuming this is a CS class). Sep 9, 2020 at 21:30

One of the more popular high-school proofs (Pappus's) that the base angles of an isosceles triangle are equal relies on an equivalence relation. They typically don't call it that in high-school, but that's what it is.

Indeed much of high-school geometry and trigonometry relies on this equivalence relation (the SSS equivalence).

OP here: There's so many good answers here, this is possibly my favorite question that I've ever asked on SE! I'm so glad that I thought to post the question here.

For comparison purposes, having considered all the great responses to date, I'll share how I've decided to revise my lecture notes. Observe that we have a crushing time constraint in the course, as about half the lecture time needs to be spent on cooperative exercises. As-is there's only about 30 minutes of lecture on binary relations, 30 on equivalence relations, and about 10 on modular arithmetic. So I don't have time to expand on new subject matter in full, but really need a "snappy" reference or retort to the original question. What I've done is:

• Worked in more explicit comparisons to the "natural language" meaning of the phrases, straight from a standard dictionary, so we can reflect on what these definitions are trying to pin down in our formal mathematics. For "relation" we see: "an existing connection; a significant association between or among things". For "equivalent" we find: "equal in value, measure, force, effect, significance, etc." -- that is, two things that are "the same" in some important way.

• Included the quote by Halmos (1982): "It is one of the basic building blocks out of which all mathematical thought is constructed". That is incredibly lovely, so glad to have that in my slides.

• Exchanged the former lecture example from a rather arbitrary one ($$aRb$$ iff $$a = b$$ or $$a = -b$$) to congruence modulo $$m$$, as several people highlighted as being of critical importance. This also gives some extra precious minutes thinking about modular arithmetic at all, of which we're sorely lacking.

Now if a student still asks the question, I can at least riff a bit on the importance of identifying any two things as being "the same", or being in the same category, in any way (to sciences in general) -- and then also mention that in later courses having this tool makes a wide variety of definitions and proofs easier to handle. That's a bit more abstract than I was hoping for, but it's a significant improvement to where I was previously.

• I don't think the Halmos quote will leave much of an impression on students if they were not already convinced that "mathematical thought" is of long-term importance to them. I remember as a student being confused about the big deal made in a book over the equivalence (!) between equivalence relations on a set and partitions of the set into disjoint subsets, presented abstractly. When I later understood what the big deal was, I didn't think it gave much insight to stress that equivalence, and that it is better just to use it in meaningful concrete examples, where the equivalence is obvious.
– KCd
Sep 12, 2020 at 1:03
• When teaching modular arithmetic, for example, I never assume the students mastered an understanding of the general "theory" of equivalence relations and equivalence classes. I might point out that congruence mod m is transitive, if time allows for it, but I don't bother with the other two aspects because I think students implicitly expect them to work and I have better things to spend time on. The number of students who ever raised an objection about that in my experience is zero. However, now that I see this post, I could direct a student to it.
– KCd
Sep 12, 2020 at 1:06
• @KCd: Well in my lectures (following Rosen text), I certainly don't expect students learning modular arithmetic to know the theory of equivalence relations; it comes much later. When we finally get there, granted that we'll be asking students to prove that some relations are equivalences, they need at least one example of establishing each of the three properties; and I now think, why not use congruence modulo m as that example? (As I say, previously I used an even less interesting example.) Sep 12, 2020 at 1:20
• Equivalence relations serve as an introduction to the types of "order-like" relations that one may impose on a set. Rather than directly discussing preorders without motivation, it's a lot nicer to first get the hang of equivalence relations, observe the very surprising similarity between equivalence relations and partial orders (some analogy exists to the surprising similarity between exponential and periodic functions, and that's all I'll say about it) and then abstract to preorders. In a sense, it's like teaching linear algebra early as motivation for abstract mathematics.
• More generally, equivalence relations are a particularly good way to introduce the idea of a mathematical structure and perhaps even to the notion of stuff, structure, property. An equivalence relation makes a set "less discrete", reduces the distinctions between points. You see this idea appear over and over again, in probability theory, in topology, and even in geometry (you may notice the axioms for a metric look weirdly similar to those of equivalence relations). The general notion of a structure is a bit more general than this but still has to do with "imposing relations on points", which is the basic moral.
• A lot of the things that you "thought" were equalities as a child, like remainders and improper integration, are actually equivalences. This is around the least significant reason to care about equivalence relations but a good criminal mastermind achieves multiple goals with one plot.
• OK, I'll bite, how is the analogy between symmetry and antisymmetry for relations like the analogy between $e^x$ and $e^{ix}$? Sep 11, 2020 at 0:25

It may be useful to show that some forms of genealogical relationships are equivalence relations and some aren't. Consider the following for relationships:

• A person #1 is M-related to #2 if both were borne to the same mother [one kind of half- or full sibling]
• A person #1 is F-related to #2 if both were sired by the same father [another kind of half-sibling]
• A person #1 is S-related to #2 if both were sired by the same father and borne to the same mother [full siblings]
• A person #1 is H-related to #2 if both were sired by the same father or borne to the same mother [half siblings]

Any two people who are M-related to the same person will be M-related to each other. That would likewise be true for any F-related and S-related pairs of people, but would not be true for all possible pairs of H-related people who share a common H-relative. Thus, the M-, F-, and S-relationships defined above are equivalence relations, but H-relationship is not an equivalence relation.

An important thing about equivalence relationships is that it makes it possible to identify relationships between objects without having to individually compare the objects to each other. If one has lists of people and all of the people within each list are M-related to each other, but one also knows that there is at least one person in the first list to whom at least one person on the second are not M-related, that would be sufficient to prove that nobody on the first list is M-related to anybody on the second. By contrast, it would be possible to have disjoint lists of people, where all the people on each list were H-related to each other, and some people on the first list were not H-related to some on the second, but there would still be some people on the first list who were H-related to some people on the second. Even if one knew that the two people were on different lists, that would prove nothing about any possible H-relationship between them.

This is a challenging question to answer in the way you want it answered, because the temptation is strong to say something like "Of course equivalence relations are interesting, every concept arises from an equivalence relations!" More precisely, the two fundamental ways of carving up the universe are (a) looking at just part of it at a time and (b) saying certain overly specific bits of it are "basically the same", i.e. applying an equivalence relation. For instance:

1. There's an equivalence relation on points in your retinal image given by "these points are part of the same object" which gives rise to visual perception, and the trickiness of calculating this equivalence relation in your brain gives rise to certain optical illusions. Similarly, for perception through other senses.
2. Or, focusing more on math, much of the entire subject of high school algebra can be reduced to the study of equivalence classes of algebraic expressions under the equivalence relation "these expressions evaluate to the same number for every input."
3. Or elsewhere in science, "an element of matter" is an equivalence class of atoms under the equivalence relation "these atoms have the same number of protons in their nucleus."
4. Of course this is not limited to chemistry: numerous abstract concepts can be treated in this way, sometimes controversially. For instance, a species is an equivalence class of organisms under "can reproduce with each other".
5. An academic field can (arguably!) be identified with an equivalence class of academics under the relation "these people agree they study the same thing".
6. A nation's cuisine is, perhaps, an equivalence class of meals under the relation "the same people make this food" or alternatively, "these foods use the same characteristic spices, ingredients, and methods of preparations..."
7. A triangle is a member of an equivalence class of polygons under the equivalence relation "these polygons have the same number of sides", or alternatively, the concept "triangle" is this equivalence class.
8. An algorithm is an equivalence class of programs under the (sometimes difficult to assess!) relation of "these programs perform the same high-level steps"
9. A family is an equivalence class of people...

OK, so every concept is an equivalence relation; you can generate examples ad infinitum and painlessly. That said, this doesn't seem to be quite the kind of justification you're looking for, and I understand the sense that students might find this all a bit far out and vague. This is, I guess, the justification I wish I were a good enough pedagogue to communicate convincingly.

A more concrete motivation for equivalence relations is to connect with the study of surjections and to combinatorics, via Bell numbers. This is most natural, of course, if you're already counting the surjections between two finite sets of fixed size at some point in the course, via inclusion-exclusion for instance. Indeed, equivalence relations are relation to surjections as subsets are to injections, once you identify an equivalence relation on $$A$$ with the surjection from $$A$$ to the set of equivalence classes. This is, incidentally, the quotient set that people seem to assume you can't tell community college students about that, though I'm not so sure--first, I tell my community college students about it, and second, we certainly talk about individual equivalence classes! A hard problem this leads to, which kind of crowns all the emphasis on injections, surjections, and bijections: any function $$f:A\to B$$ can be uniquely written as a composite of three pieces: the standard map to the set of equivalence classes of an equivalence relation (namely the relation $$f(a_1)=f(a_2)$$, then a bijection, then the inclusion of a subset (namely the image.)

I always thought it was interesting that you could use equivalence relations to make "higher" definitions. You collect a bunch of objects which have a common attribute and then you formally define an abstract idea to be an equivalence class. For example, a geometric vector (the abstract idea) can be thought of as an equivalence class. In axiomatic geometry, the set of equivalence classes of congruent segments becomes a field (so an equivalence class can capture the idea of a number). Same thing with Cauchy sequences. You can also use equivalence classes to define the idea of direction.

Equivalence classes provide a tool for describing information. If you have an object $$x$$ and an equivalence relation $$R$$, one piece of information about $$x$$ is "which $$R$$-equivalence class is it in". What's more, any piece of information can be described in this way by constructing an equivalence relation where two things are equal if this attribute of theirs is the same.

Usually we have the notion of information first, and can construct an equivalence relation based on that, but sometimes it's reversed: the equivalence relation allows us to capture an important piece of information that's hard to describe. For instance, the asymptotic behavior of a function is a really important piece of information, but to get at that information you really need to start with the notion of asymptotic equivalence.

This is close to one of my favorite equivalence relations: two sequences being eventually equal, which doesn't actually capture any information about the particular value of the sequence at any point, but still captures important information about it.

The best example of this is Myhill-Nerode equivalence. We say that two computers in particular states are Myhill-Nerode equivalent if no matter what inputs we feed into both computers, we get the same outputs. This equivalence relation captures exactly the information we need to keep track of to determine the future behavior of a computer. Any other information we're keeping track of is unnecessary.

One of my replies to such a question would be "You know how most software doesn't work very well ? Well the people who wrote it also didn't see the point of studying basic logic and set theory". Although I would take pleasure in the provoking tone of such a reply, yet I also believe it is a very important point.

EDIT: The kernel of any function is an equivalence relation on the domain of the function. In particular this applies to hashes. Why not learn a general idea that unifies this idea and all the many other concrete examples of equivalence relations ? If that seems too boring or arduous to the student then I don't have high hopes for the quality of the code they will eventually write.

EDIT: The Mr. Miyagi principle: Just paint the damn fence and tell me at the end of the movie whether you think it was a waste of time ! I'm sure that plumbing and roofing apprentices don't dare trouble their gnarled mentors with questions about the value of what they are being taught. Why should it be different for university students ? I suppose one reason might be that while there probably aren't many bad master plumbers nor bad master roofers, yet there are plenty of bad teachers. The answer to which is: Don't be a bad teacher.

• Not 4. Just 2. I won't bother to downvote. But isn't your "answer" just a bunch of snark? You might have a good point to make, but I'll be able to find it easier if you write a post in a more positive style. Sep 11, 2020 at 5:01
• Thank you for your comment. I think at least 4, and some upvotes too. My answer is not just a bunch of snark, no. I gave one example as requested, and made two serious points, which to me at least are easily seen, in spite of my tone. Sep 11, 2020 at 9:39
• @Simon The answer currently has no upvotes, but there is no specific requirement to make popular posts on stackexchange sites. You have two good options: either edit your answer to make it easier for people to see the points you are making, or stop worrying about its score. Both are fine! Sep 11, 2020 at 13:29
• Thank you for your comment Chris. I think I misinterpreted the numerical feedback from the app. I'll trust people to be able to see my points, if they want to, that is. I'll go with the second option and stop worrying ! :D Sep 11, 2020 at 13:38
• I upvoted for snark. We need more snark. Sep 13, 2020 at 2:58

I wonder if it is not so much a direct application (in a coding problems) as it is very similar in thought process to being rigorous about your code structure.

That, and I think CS likes to dress up the curriculum with some math, mostly not useful for B.S. students. But it's just part of the dynamic.

FWIW, a Google search found some (but not much...definitely have to weed through it for genuine applications as opposed to "used in math" applications. But you could sift through.

• Back when I was an undergrad, CS students were expected to include in their comments a proof that their code was correct in all cases, and write proofs that algorithms worked as expected. Having programmers who can do that definitely meant much cleaner code with much fewer bugs. Then again, back in those days, it was considered shameful to release code with any bugs at all; nowadays it's just another minor thing to fix on the next release. Sep 9, 2020 at 3:37