I am not exactly clear on what an equivalence relation. If A is a set, then a relation on A is a subset R. The relation R is an equivalence relation on A if it satisfies the reflexive property, symmetric property, and transitive property. What types of relations are we talking about. And when could these relations ever not have these 3 properties. And what are equivalence classes? I need some simple examples to demonstrate this since none are really provided in this textbook.
What are you asking? If there are equivalence relations not satisfying those properties? Obviously not, since then the relations wouldn't be equivalence relations. Maybe you want an example of a relation that's not an equivalence relation. Cconsider the relation "less than" (<) on the real numbers. It is not symmetric, since for example, 3 < 4 doesn't imply 4 < 3.
it's not relflexive either, 3<3? Don't think so! But [tex]\leq[/tex] is reflexive (and transitive) but not symmetirc again. Equivalence relations are the generalization of the relation of being equal - whilst two elements are not the same, they may in share all the properties that you care about. an equivalence realation on a set A is not a subset of A. It is just a relation, a rule for saying how/when two elements are related in some manner. the equivalence class [x] of x in A is the subset of A of all elements that are 'related' to x. The rules for an equivalnce relation imply that if xRy, they [x]=[y] - ie equivalence classes are equal or disjoint. Important examples are modulo arithmetic, conjugacy classes of groups, cosets of subgroups, defining quotient structures such as in the isomorphism theorems of algebra here are several relations on Z say xRy iff x=y+1 this not symmetric transitive or refelxive xRy iff x<y this is only transitive xRy iff x<=y is transitive and relfexive but not symmetric xRy iff x is not equal to y is symmetric but neither reflexive nor transitive.
I think I have a really good way of explaining this so I would like comments. My example of an equivalence relation is x and y have the same parity in other words xRy is true when both x and y are odd. xRy is also true when both x and y are even. If one of the variables x,y is odd or even then xRy false. So xRy is true when x and y are the "same"(equivalent) in some respect. if xRy is true x and y have a specific common property. Exactly what the common property is depends on the problem. This explains all your rules. symmetric xRy => yRx If x has a common property with y then y must have a common property with x. reflexive xRx x and x must have a common propery! transitive xRy and xRz => yRz. If x and y have a common property and x and z have a common property then y and z share a common property. Now cleary an equivalence relation divides the set into distint subset where everything each subset has the same common property. if you remember my original example where the equivalence relation is " both odd or both even" then two subsets are the even numbers and the odd numbers and xRy => x and y are in the same subset.
Hope this helps In general, an n-ary relation (n a positive integer) R on a set A is a subset of the Cartesian product A x A x ... A (n times). Since the most commonly used relations are binary, we are usually dealing with relations that are a subset of A x A. I just thought of a binary relation that is symmetric but not reflexive and not transitive: the relation "is perpendicular to" on the set of vectors in a real three-dimensional vector space.
Examples of binary relations The binary relation "divides," on the set of positive integers (as in "5 divides 15, 5 does not divide 12") is reflexive and transitive, but not symmetric. There are 8 possible "truth tables" (if I can use that terminology for this purpose) for a binary relation to fall into: 1) Reflexive, Symmetric, Transitive 2) Reflexive, Symmetric, not Transitive ... 8) not Reflexive, not Symmetric, not Transitive We now have examples of some of those eight in this thread. Can anybody come up with examples of the others? I don't just mean ad hoc examples, such as: "A Bush-Kerry binary relation on the set (a, b, c) is given by the subset (<a,c>, <b,c>) (or in other terminology, aRc and bRc)" which is not reflexive, not symmetric, and not transitive. Here I am using < , > to mean ordered pair.
Another binary relation The binary relation "is parallel to" on the set of vectors in a real three-dimensional vector space is reflexive, symmetric, and transitive.
Let's do it on N. let R, S T be reflexive etc, and nR be the negations (R)(S)(T): x~y iff x=y one negation: (nR)(S)(T) ??? (R)(nS)(T) x~y iff x<=y (R)(S)(nT) x~y iff x=y+1 or x=y-1 or x=y two negations: (nR)(nS)(T) x~y iff x<y (nR)(S)(nT) x~y iff x is not equal to y. (R)(nS)(nT) x~y iff x=y or x=y+1 three negations: (nR)(nS)(nT) x~y iff x=y+1
Thanks Matt. Now you've got me trying to come up with a relation (nR)(S)(T) on N. By the way, if by N you mean the naturals, should we broaden it to the integers, to avoid lack-of-closure problems with x=y-1?
fine, Z, N, whichever seems most appropriate to you it isn't important I don't beleive (I am not saying every possible relator of every number must exist)
Well, if your relation is symmetric and transitive and you have x~y, then: x~y therefore y~x therefore x~x ! So in order for a relation to be symmetric, transitive, and not reflexive, you must have some element x that is not related to anything. BTW, there are three classes for reflexivity and symmetry; You have reflexive ([itex]\forall x:x\sim x[/itex]), irreflexive ([itex]\forall x: \neg (x \sim x)[/itex]), and neither. You have symmetric ([itex]\forall x \forall y: x \sim y \Leftrightarrow y \sim x[/itex]), antisymmetric ([itex]\forall x \forall y: x \sim y \wedge y \sim x \Rightarrow x = y[/itex]), and neither.
"I am not saying every possible relator of every number must exist." Fair enough! I avoided zero in my "divides" example, but given your proviso, maybe I didn't need to. Thanks.
Thanks Hurkyl for pointing out that "So in order for a relation to be symmetric, transitive, and not reflexive, you must have some element x that is not related to anything." I guess that is why it is hard to come up with an example that doesn't look ad hoc, for that particular case. And thanks for pointing out that one can usefully further subdivide some of my eight cases.
Amplifying on something Matt said- As chance would have it, I came upon a definition today: A relation is total if for all x there exists a y such that xRy. So my "divides" relation is a total relation on Z+ but not on Z.
Elements of the partition on A are subsets of A, and the Union of the partition is A and the intersection of the partition is NULL.
I have a question. For something like x=ymodn, how would you prove something which is intuitively obvious like for this relation, n distinct equivalence classes exist ([0],[1],...[n-1]).
you just need to show that if you have some Natural number x , that you infact have a partition. so x can be in some set A and in some set B iff A = B. how it is partitioned is not as important as showing that it is an equivilence relation because once you establish the EQ Relation on the set, you have no need to proove that a partition exists.
"Is y allowed to be x? For then every reflexive relation is total." - Matt Yes, I didn't see any restriction saying y had to be distinct from x. So you make a good point: every reflexive relation has to be a total relation.