# Tag Info

## Hot answers tagged discrete-math

25

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

16

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

11

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

9

It's a bad idea. (1) It's not that special. He can get a game from chess very easily from anyone. An individual session with you is not high value, not best use of time. (2) It will raise hackles. I would suggest instead introducing some recreations that are less familiar instead. Playing Hex for instance is an idea. The value is much higher than chess, ...

6

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

6

First, let's note that the terms as used by Rosen are standard definitions, as we can see on Wikipedia (here and here), as well as other resource sites. There was some question about this in the comments, so I thought to clarify this first. Perhaps reading those articles will give an added perspective for the OP. Now, I'm not going to offer a mnemonic -- I ...

6

I'd avoid introducing a new notation for such a limited scope: you won't probably use it elsewhere during the class, and it wouldn't be used elsewhere in the literature. I have three suggestions. The first is a simple variation of Trevor Wilson's answer, which mirrors the first relation sign to keep the bridging elements together: R\ni(1,3) \And (3,2) \in ...

6

To explain why any particular ordered pair is in $S \circ R$, you can just show that it satisfies the definition, which says that $(a,c)$ is in $S \circ R$ if there exists $b$ such that $(a,b) \in R$ and $(b,c) \in S$. To show this is true, you can just give an example of such $b$ and observe that $(a,b) \in R$ and $(b,c) \in S$. The two things here are ...

6

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

5

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

5

This is not a question that can be easily answered without careful historical research. Here are some guesses in the absence of such research. What's been added? Algorithm analysis: big-$O$ notation. Dijkstra's algorithm. Aspects of complexity theory: polynomial-time vs. beyond polynomial. Discussion of the TSP problem, Christofides' heuristic. Cryptography,...

4

I taught a geometry course which counted both for math majors (sophomore level), and was required for the math education program secondary education teacher majors, and we used the text: Edwin Moise: Elementary Geometry from an Advanced Standpoint, 3rd Edition, which was amply challenging for both cohorts of students. For math majors completing this course,...

4

If you are teaching to an audience that will largely be computer science majors (which is often the case), then you should look at the ACM guidelines for an undergraduate computer science curriculum, which includes guidelines for what should be in a discrete math course. Looking at older versions of these guidelines will also give you some sense of how this ...

4

“ I know it has a lot of relations with the mathematics, with the logic, many applications in computer science, game theory and so on.“ Do you know these specific relationships and are you prepared to introduce/explain these things in the context of the game? If so, that sounds like it should take quite a bit of preparation on your part to teach a complex ...

3

Thanks for your feedback on my previous answer, which contained a misunderstanding. Here's a new try. I believe the following is the way to express the thought that you were trying to express as $(1,2) + (2,1) \implies (1, 1)$, using only the notation your book seems to be using: $\{(1,2)\}\circ\{(2,1)\}=\{(1,1)\}.$ That is, your book defines a relation as a ...

3

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

3

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

2

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

2

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

2

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

2

You should look at the stated contents of the course you are being asked to teach. Then take a look at what they already have learned when taking this course (perhaps add a bit of refresher, or give them a summary text). Next look at the use they'll have of the material included in the course in later courses, or perhaps in their later life. The above should ...

1

You might point out that the $3$-trial experiment has $8$ possible outcomes and $256$ possible events, which are subsets of the sample space; whereas each trial has $2$ possible outcomes, which can be contextually characterised as a success and a failure. To distinguish between trial outcomes and experiment outcomes (or to remind about their distinction), I ...

1

I recommend to do some analysis of the situation. Telling us how the long the chapter is means nothing if we don't know how fast you have to cover things. Try to look at the situation as pages per day. Recommendations: Work every day and do the required pages every day, to stay on track. (Perhaps) just chalk this up as a course that is going to take more ...

1

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

1

I am not a fan of the so-called "Cauchy induction" mentioned in the other answer, for the reasons mentioned in my comment there. So here is my own offered answer (taken from an earlier post of mine): Given $f:\mathbb{Z}{\to}\mathbb{R}$ such that $f(0) = 0$ and $f(1) = 1$ and $f(x{+}1) + 6 f(x{-}1) = 5 f(x)$ for any $x {\in} \mathbb{Z}$, prove that ...

1

Answered in comments: brilliant.org/wiki/forward-backwards-induction – Bill Cook Nov 9 '18 at 3:35 Maybe not quite what you're looking for, but have you heard of Cauchy induction? You prove your base case, then you prove that $P(n) \implies P(2n)$ and that $P(n) \implies P(n-1)$, which covers all cases. – Mike Pierce Nov 9 '18 at 16:12

Only top voted, non community-wiki answers of a minimum length are eligible