What is Equivalence relations: Definition and 60 Discussions

In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The relation "is equal to" is the canonical example of an equivalence relation.
Each equivalence relation provides a partition of the underlying set into disjoint equivalence classes. Two elements of the given set are equivalent to each other, if and only if they belong to the same equivalence class.

View More On Wikipedia.org
  1. PhysicsRock

    Binary operation on equivalence classes

    So, my approach and solution are as follows: $$ [x * y] = \{ z \in M : z \sim (x * y) \} $$ Since we know that ##a * b \sim a^{\prime} * b^{\prime}## we can rewrite ##z## as ## x^{\prime} * y^{\prime} ##. Plugging this in yields: $$ [x * y] = \{ x^{\prime}, y^{\prime} \in M : x^{\prime} *...
  2. L

    MHB Equivalence Relations: Solving & Proving Reflexivity, Symmetry & Transitivity

    Dear All, I am trying to solve the attached two questions. In both I need to determine if the relation is an equivalence relation, to prove it if so, and to find the equivalence classes. In both cases it is an equivalence relation, and I managed to prove both relations are reflexive. Now I...
  3. WMDhamnekar

    MHB When to use equivalence relations? How to write it in octave?

    Sometimes to help describe one expression, another expression is shown that produces identical results. The exact equivalence of expressions is indicated with ‘ ≡’. For example: rot90 ([1, 2; 3, 4], -1) ≡ rot90 ([1, 2; 3, 4], 3) ≡ rot90 ([1, 2; 3, 4], 7) What is the meaning of 'rot90;? What...
  4. I

    Equivalence Relations and Counter Examples for Equinumerous Sets

    (a) I present the following counter example for this. Let ##A = \{0,1,2,\ldots \}## and ##B = \{ 2,4,6, \ldots \} ##. Also, let ##C = \{ 1, 2 \} ## and ##D = \{3 \}##. Now, we can form a bijection ##f: A \longrightarrow B## between ##A## and ##B## as follows. If ##f(x) = 2x + 2##, we can see...
  5. L

    MHB Equivalence Relations Problem Please help?

    I understand that the first part of the equation is an equivalence class due to reflexivity, symmetry, and transivity... but I am confused on the second part. Could someone please help me out? THANKS
  6. U

    Proof of equivalence relation

    <Moderator's note: Moved from a technical forum and thus no template.> Not sure this should be under Linear and Abstract Algebra, but regardless I need help with a question in my mathematical proofs course. Here it is: Let ∼ be a relation defined on Z by x ∼ y if and only if 5 | (2x + 3y). (a)...
  7. Y

    MHB Different Number of Equivalence Relations

    Hello all, I have a few questions related to the different number of equivalence classes under some constraint. I don't know how to approach them, if you could guide me to it, maybe if I do a few I can do the others. Thank you. Given the set A={1,2,3,4,5}, 1) How many different equivalence...
  8. RJLiberator

    Equivalence Relations Simple Question

    Homework Statement For each of the relations defined on ℚ, either prove that it is an equivalence relation or show which properties it fails. x ~ y whenever xy ∈ Z Homework EquationsThe Attempt at a Solution Here's my problem: I am starting off the proof with the first condition of...
  9. RJLiberator

    Equivalence Relations Questions

    Homework Statement For the set ℤ, define ~ as a ~ b whenever a-b is divisible by 12. You may assume that ~ is an equivalence relation and may also assume that addition and multiplication of equivalence classes is well defined where e define [a]+[ b ] = [a+b] and [a]*[ b ] = [ab] for all [a],[ b...
  10. H

    Are all physical quantities an equivalence relation?

    Consider this self-evident proposition: "If object A has the same mass as object B and object C separately, then object B has the same mass as object C." Why isn't this stated as a law, but the zeroth law of thermodynamics is? Is there a physical quantity u such that the u of A is equal to the...
  11. C

    MHB Proof of Unique Equivalence Relation on Set w/ Partition Classes

    Hello, I've to construct a proof of the following statement: Prove that if S is a set and S_1... S_k is a partition of S, then there is a unique equivalence relation on S that has the S_i as its equivalence classes. I'm really not sure how to go about this proof at all, so any help would be...
  12. N

    Equivalence Relations on Z: Proving m~n and Describing the Partition

    Prove that the following is an equivalence relation on the indicated set. Then describe the partition associated with the equivalence relation. 1. In Z, let m~n iff m-n is a multiple of 10.2. The attempt at a solution Reflexive: m-n = 0 0 ∈ Z, and 0 is a multiple of every number...
  13. K

    What Does Equivalence Relations Mean in Set Theory?

    Hi, I'm reading a book on sets and it mentions a set B = {1,2,3,4} and it says that R3 = {(x, y) : x ∈ B ∧y ∈ B} What does that mean? Does that mean every possible combination in the set? Also the book doesn't clarify this completely but for example using the set B say i had another...
  14. T

    MHB Glad I could help! Good luck with your studies.

    Hi guys! First time poster, long time lurker! I can't make any sense out of equivalence relations:confused: These kinda questions crop up every year on the exam and I was wondering if someone could help me understand the concept behind them. (i)Show that relation R defined on the of the set S =...
  15. K

    What is the equivalence class [3] in a relation defined by powers of 2?

    Homework Statement Let ## H = \{ 2^{m} : m \in Z\}## A relation R defined in ##Q^{+} ## by ##aRb ##, if ## \frac{a}{b} \in H## a.) Show that R is an equivalence Relation b.) Describe the elements in the equivalence class [3]. The Attempt at a Solution For part a, I think I am able to solve...
  16. S

    MHB Partitions and equivalence relations

    i don't have a specific question. i just need an explanation on what this topic is about. i am not understanding it
  17. 3

    Equivalence Relations, Cardinality and Finite Sets.

    Hey everyone, I have three problems that I'm working on that are review questions for my Math Final. Homework Statement First Question: Determine if R is an equivalence relation: R = {(x,y) \in Z x Z | x - y =5} and find the equivalence classes. Is Z | R a partition? Homework...
  18. A

    MHB Equivalence Relation: Partition of {a,b,c} - Andy

    If {{a,b},{c}} is the partition of {a,b,c}. When finding the equivalence relation used to generate a partition, is it enough to say {a,b}x{a,b} U {c}x{c}? Thanks Andy
  19. J

    Composition of two equivalence relations

    Homework Statement The question is let E1 and E2 be equivalence relations on set X. A new relation R is defined as the E1 o E2, the composition of the two relations. We must prove or disprove that R is an equivalence relation.Homework Equations The Attempt at a Solution I know that we must...
  20. B

    Equivalence relations and classes

    Show that if R1 and R2 are equivalence relations on a set X, then R1 is a subset of R2 iff every R2-class is the union of R1 classes. Attempt: I don't understand that if R2 has elements nothing to do with the elements of R1, how can an R2 class be a union of those elements belonging to an R1...
  21. L

    Equivalence Relations in A={a,b,c,d}: Proving the Bell Number Theorem

    Our math Teacher asked us to find how many equivalence relations are there in a set of 4 elements, the set given is A={a,b,c,d} I found the solution to this problem there are 15 different ways to find an equivalence relation, but solving the problem, i looked in Internet that the number of...
  22. G

    Finding Equivalence Relations in a Set of 4 Elements - Juan's Question

    Our math Teacher asked us to find how many equivalence relations are there in a set of 4 elements, the set given is A={a,b,c,d} I found the solution to this problem there are 15 different ways to find an equivalence relation, but solving the problem, i looked in Internet that the number of...
  23. A

    Why define equivalence relations, posets etc.

    I am studying set theory and I came across various definitions like equivalence relations, partial order relations, antisymmetric and many more. I am aware mathematicians don't care about real life applications but still - why are we defining so many relations? What is the use of defining...
  24. J

    Showing that Equivalence Relations are the Same.

    Let G be a group and let H be a subgroup of G. Define ~ as a~b iff ab-1εH. Define ~~ as a~~b iff a-1bεH. The book I am using wanted us to prove that each was an equivalence relation, which was easy. Then, it asked if these equivalence relations were the same, if so, prove it. My initial...
  25. H

    Equivalence Relations on {0, 1, 2, 3}: Understanding Reflexivity and Properties

    Homework Statement Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of an equivalence relation that the others lack a) { (0,0), (0,2), (2,0), (2,2), (2,3), (3,2), (3,3) } This one is not reflexive Homework Equations I understand that...
  26. T

    Equivalence relations and addition

    Homework Statement prove that if a~a' then a+b ~ a' + b Homework Equations The Attempt at a Solution I can prove that if a=a' then a+b = a' + b but how can I apply this to any equivalence relation
  27. C

    Prove Relationship between Equivalence Relations and Equivalence Classes

    I'm not sure if I did these 2 questions correctly, so would someone please check my work for any missing ideas or errors? Question 1: Homework Statement Prove: For every x belongs to X, TR∩S(x) = TR(x) ∩ TS(x) Homework Equations The Attempt at a Solution TR(x) = {x belongs to X such that...
  28. G

    Equivalence Relations on Z - Are There Infinite Equivalence Classes?

    Homework Statement Deciede if the following are equivalence relations on Z. If so desribe the eqivalence classes i) a\equiv b if \left|a\right| = \left|b\right| ii) a\equiv b if b=a-2 Homework Equations The Attempt at a Solution i) \left|a\right| = \left|a\right| so its...
  29. F

    Sets and Algebraic Structures, help with equivalence relations

    Let Q be the group of rational numbers with respect to addition. We define a relation R on Q via aRb if and only if a − b is an even integer. Prove that this is an equivalence relation. I am very stumped with this and would welcome any help Thank you
  30. R

    Proving R is an Equivalence Relation: Steps and Explanation

    1. Let R be a relation on X that satisfies a) for all a in X, (a,a) is in R b) for a,b,c in X, if (a,b) and (b,c) in R, then (c,a) in R. Show that R is an equivalence relation. 2. In order for R to be an equivalence relation, the following must be true: 1) for all a in X, (a,a) is...
  31. R

    Equivalence Relations on a Plane - Proofs, Cases, and Geometric Interpretations

    Homework Statement For each of the relations on the set R x R - (0,0) (ie. no origin) : - prove it is an equivalence - give the # of equivalence cases - give a geometric interpretation of the equivalence cases assuming an element of R x R is a point on a plane a) {((a,b),(c,d)) |...
  32. H

    Why is reflexive property necessary? equivalence relations

    Homework Statement Provide an example that shows why the reflexive property is not redundant in determining whether a relation is an equivalence relation or not. For example, why can't you just say, "If xRy then yRx by symmetric property, and then using transitive property you get xRx."...
  33. P

    Equivalence relations and classes problem.

    Homework Statement Let X = {a,b,c,d}. How many different equivalence relations are there on X? What subset of XxX corresponds to the relation whose equivalence classes are {a,c},{b,d} Homework Equations N/A The Attempt at a Solution So I wrote out all the possible "blocks"...
  34. A

    Equivalence Relations and Partitioning in Sets

    I have two questions: i) Does a distinct equivalence relation on a set produce only one possible partition of that set? ii) Can multiple (distinct) equivalence relations on a set produce the same partition of that set? In other words, given a set S and two distinct equivalence relations ~...
  35. E

    Is R an Equivalence Relation on Functions to [0,1]?

    Homework Statement Given is the set X. The set of functions from X to [0,1] we call Fun(X,[0,1]). On this set we consider the relation R. An ordered pair (f,g) belongs to R when f^{-1}(0)\setminus g^{-1}(0) is a countable set. a) Prove that R is transitive. b) Is R an equivalence relation...
  36. L

    Equivalence Relations on [0,1]x[0,1] and Hausdorff Spaces

    We have a equivalence relation on [0,1] × [0,1] by letting (x_0, y_0) ~ (x_1, y_1) if and only if x_0 = x_1 > 0... then how do we show that X\ ~is not a Hausdorff space ?
  37. D

    Proving Equivalence Relations for Real Numbers x, y, z in R

    x,y,z\in\mathbb{R} x\sim y iff. x-y\in\mathbb{Q} Prove this is an equivalence relation. Reflexive: a\sim a a-a=0; however, does 0\in\mathbb{Q}? I was under the impression 0\notin\mathbb{Q} Symmetric: a\sim b, then b\sim a Since a,b\sim\mathbb{Q}, then a and b can expressed as...
  38. D

    Smallest Equivalence Relation on Real Numbers: Proving with Line y-x=1

    1) Recall that an equivalence relation S on set R ( R being the reals) is a subset of R x R such that (a) For every x belonging to R (x,x) belongs to S (b) If (x,y) belongs to S, then (y,x) belongs to S (c) If (x,y) belongs to S and (y,z) belongs to S then (x,z) belongs to S What is the...
  39. K

    Understanding Equivalence Relations in Real Numbers and Vector Spaces

    Homework Statement I have got myself very confused about equivalence relations. I have to determine whether certain relations R are equivalence relations (and if they are describe the partition into equivalence classes, but I'll worry about that once I understand the first part). Here are...
  40. S

    Is RxS an Equivalence Relation on ExF?

    Homework Statement I need a little help in understand this question: Let E and F be two sets, R a binary relation on the set E and S a binary relation on the set F. We define a binary relation, denoted RxS, on the set ExF in the following way ("coordinate- wise"): (a,b) (RxS) (c,d) <-->...
  41. R

    Equivalence relations and equivalence classes

    Hey! Hoping you guys could help me with a small issue. No matter how hard I try, I don't seem to fully understand the notion of an equivalence relation, and henceforth an equivalence class. What I do understand that, in order to have and equivalence relation, it is defined to satisfy three...
  42. N

    Quantification logic and equivalence relations

    I wasn't sure whether to post this in the algebra forum or here, but it seems that this is more of a logic question so I'm going with here. I am trying to understand whether there is a difference between the following two definitions of an equivalence relation: Definition 1: A binary relation...
  43. D

    Equivalence Relations on Integers with a Unique Property

    This is a question from A consise introduction to pure mathematics (Martin Liebeck) Hi guys, just stuck on one problem was wondering if someone could lend me hand. Let ~ be an equivalence relation on all intergers with the property that for all "m" is an element of the set of intergers ...
  44. D

    Equivalence Relations on Integers: Proving Equivalence for All Elements

    This is a question from A consise introduction to pure mathematics (Martin Liebeck) Hi guys, just stuck on one problem was wondering if someone could lend me hand. Let ~ be an equivalence relation on all intergers with the property that for all "m" is an element of the set of intergers ...
  45. J

    Equivalence Relations proof

    Statement: Prove or Disprove: A relation ~ on a nonempty set A which is symmetric and transitive must also be reflexive. Ideas: If our relation ~ is transitive, then we know: a~b, and b~a \Rightarrow a~a. Therefore our relation ~ is reflexive, since b~c and c~b \Rightarrow b~b, and c~a...
  46. B

    Equivalence Relations on Set S: Description and Number of Classes

    Hello! I'm a bit lost on these questions pertaining to equivalence relations/classes. If someone could run me through either, or both, of these questions, I'd be very thankful! I'm completely lost as to what to do with the z in terms of set S... Homework Statement Show that the given...
  47. J

    Proving R is an Equivalence Relation on R^2

    A relation R on R^2 is defined by (x_{1},y_{1})\mathit{R}(x_{2},y_{2})\;\;\;if\;\;\;x_{1}^{2}+y_{1}^{2}=x_{2}^{2}+y_{2}^{2} How do you show that R is an equivalance relation?
  48. C

    Equivalence relations and connected components(Please look at my calculations)

    Homework Statement Hi I have justed switched to a new subject and have some question. 1) Show that if X is a topology space then there exist an equivalence relation if and only if there exist a connected subset which contains both x and y. 2) Show that the connected components are a...
  49. M

    Equivalence Classes in PxP for (1,2)

    Homework Statement On set PxP, define (m,n)\approx(p,q) if m*q=p*n Show that \approx is an equivalence relation on PxP and list three elements in equivalence class for (1,2) Homework Equations The Attempt at a Solution I will appreciate any help how to start this problem...
  50. V

    Equivalence Relations

    Homework Statement Find relations that satisfying just Reflexive just Symmrtic just Transitive (R) & (S), but not (T) (R) & (T), but not (S) (S) & (T), but not (R) Homework Equations S=Z (a,b) \inR if <=> a>b (T) but, not (S) & (R). the ex is given in the class, but...