Talk:Equivalence relation

Duplication of definition?

Should the three properties really be defined here or is it enough to refer to binary relation? Or should these properties have their own pages a la Eric Weisstein? -- Jan Hidders

I don't think the small amount of duplication is a problem, and it aids understanding.

PS: Hopefully, we can soon get up to the level of depth Weisstein had (unsigned comment by Gareth Owen 09:25, Jul 13, 2001 — Paul August ☎ 17:43, May 23, 2005 (UTC))

Ok. I would agree with that. But do you think that Wikipedia should define the same terms, i.e., if Eric has a definition of a certain mathematical concept then so should Wikipedia? Or should Wikipedia be more "course grained"? -- Jan Hidders

Duplication, in addition to aiding "understanding", also helps to make Wikipedia more robust, in that an error in one place can be corrected by looking somewhere else. Paul August ☎ 17:44, May 23, 2005 (UTC)

Content move

I moved this from the main page:

Given an arbitrary relation R, we define the equivalence relation ~ as follows:

• (Reflexivity) Define x~x.
• (Symmetry) Define x~y whenever R(x,y) *or* R(y,x) is true.
• (Transitivity) Define x~y whenever there exists z such that R(x,z) and R(z,y) is true.

This is incorrect; the equivalence relation generated by R is a bit more complicated. In the third step, one has to allow for a whole sequences z₁,...,z_n of intermediate elements, and for each i one has to allow for R(z_i,z_i+1) *or* R(z_i+1,z_i). AxelBoldt 22:10 Nov 23, 2002 (UTC)

"in thermal equilibrium with"?

On what set is "in thermal equilibrium with" an equivalence relation? (unsigned comment by anon 69.202.74.207 — Paul August ☎ 17:43, May 23, 2005 (UTC))

Asymptotical equivalence

I did not (yet) find anything about the notion of asymptotical equivalence

(x_n) ~ (y_n)  iff  (x_n-y_n) = o(y_n)

and the "crude" equivalence x=Theta(y) <=> x=O(y) and y=O(x). — MFH: Talk 17:14, 23 May 2005 (UTC)

PS: found the first one (slightly different and not completely equivalent definition) at Asymptotic... see Talk:Asymptotic analysis... — MFH: Talk

Doesnt 2 and 3 imply 1?

Hmmmm. Let's see:

• by 2, a~b, then b~a
• take a=c
• So, by 3, a~a

QED

Yes, I know this is wrong, but where's the error?

--User:Mdob

Given a fixed a, there need not exist a b such that a~b. For example, the empty relation is not an equivalence relation. It is symmetric and transitive but not reflexive. -- Fropuff 01:08, 12 October 2005 (UTC)

The definition of Equivalence Relation given in http://www.iscid.org/encyclopedia/Equivalence_Relation seems to say that the empty relation is an equivalence relation. It seems like the empty relation is vacuously reflexive to me. Is this wrong or are there just different interpretations?

I would think that an empty relation on an empty set would vacuuously be an equivalence relation, but that an empty relation on a non-empty set would not be an equivalence relation because it does not satisfy x ~ x for any x in that set. 129.110.241.254 21:18, 22 August 2006 (UTC)

Perhaps empty relation is not well defined. Define a relation ~ on the integers such that for all integers a and b, a~b is false. 2 and 3 are vacuously satisfied but 1~1 is false, so this is not an equivalence relation. The error in your proof is thus the assumption that there exists a, c such that a=c. If there is (well, if for all a there exists c such that a~c) then we have an equivalence relation. —Preceding unsigned comment added by 68.1.101.154 (talk) 07:23, 28 May 2008 (UTC)

This was an exercise in a logic class I had, find a relation that was symmetric and transitive but not reflexive. A simple example, as said before is the relation that maps all pairs to false. It is well defined. The reference book of the course was "Mathematical Logic", by Ebbinghau Flum and Thomas. The statement in the definition section that integers modulo 2 is not an equivalence relation is absolutely incorrect and I am going to change the section in the definitions to reflect this. Antares5245 (talk) 01:31, 7 June 2010 (UTC)

Partial Order : Lattice theory :: Equivalence relations : ?

I hereby invite someone to add a section on groups and equivalence relations. Lattice theory is the algebraic structure of partial orderings. What is the algebraic structure of equivalence relations? Bas Van Frassen (1989) convinced me that it is (non-Aberlian) group theory, but algebra texts are typically totally silent about this fact, with the possible exception of Birkhoff and MacLane (1979: 72). The mathematicians whom I've queried about this tell me they have no idea what I am talking about. A curious situation indeed... On equivalence relations and group theory, see [1] and the references therein.202.36.179.65 10:22, 18 March 2006 (UTC)

I went to work and answered my own query.202.36.179.65 11:44, 8 August 2006 (UTC)

"Sibling of" is NOT Transitive

If it were, then it would lead to people being their own sibling. A sibling of B implies B sibling of A. Then by transitivity, A would be a sibling of A, which is false. It may sound like I am committing the error "2 and 3 imply 1" above, but I'm not. If the relation were transitive, then anyone that had a sibling would be considered a sibling of themself as well, which is clearly undesirable. —The preceding unsigned comment was added by 67.124.203.53 (talk • contribs) 17:07, May 25, 2006 (UTC)

Correct. Paul August ☎ 17:38, 25 May 2006 (UTC)

It depends on what you mean by "sibling." if we define "A is a sibling of B" to mean "A has the same two parents as B" then surely the sibling relation is an equivalence relation. -Misfit 20:18, 13 September 2007 (UTC)

This further illustrates the dangers in extending the idea of equivalence relation (a mathematical concept) to collections of objects and relationships between those objects which are not mathematical objects. I don't like the idea of the "set" of human beings because I'm not really sure that there is such a thing. Having examples which are not mathematical means that the concepts involved must be really well-defined, or they fall apart (as in the case of sibling). I have never seen the term "sibling" mean "having the same parents as;" in general, as far as I am aware, it means, "is a sister or brother to," and in this sense "sibling" would not be an equivalence relation, as has already been pointed out. Xantharius 03:37, 14 September 2007 (UTC)

The word "set" really ought to be able to include the set of human beings. I don't think this is the issue, and blocking things like that impedes understanding. The issue is that, as we have seen, sibling is not well-defined (or it is, but that definition is not generally agreed upon, which is perhaps worse). We shouldn't block real-world examples, just be more careful with them. —Preceding unsigned comment added by 68.1.101.154 (talk) 07:25, 28 May 2008 (UTC)

That's been sitting there for years? How ridiculous! I've changed it, because it was completely wrong.24.58.63.18 (talk) 22:12, 15 March 2009 (UTC)

Just a thought but sibling is transitive and here's why:

If relation R is Transitive "xRy and yRz implies xRz"

When y = x we have "xRx and xRz implies xRz", "xRx" is fully determined by the reflexive property of relation R. If R is irreflexive x is never related to x by R, hence R being transitive tells use nothing about "xRz". If R is reflexive "xRx" is always true and we have "xRz implies xRz" hardly illuminating for obvious reasons.

The knowledge that relation R is transitive adds information when x != y and nothing when x = y.

When y = z we have "xRz and zRz implies xRz", again "zRz" is determined by the reflexive property of relation R. If R is irreflexive z is never related to z by R, hence R being transitive tells use nothing about "xRz". If R is reflexive "zRz" is always true and we have "xRz implies xRz" again hardly illuminating for the same obvious reasons.

Hence knowing that relation R is transitive adds information when y != z and x != y and nothing when x = y or y = z.

When x != z we find that knowing that relation R is transitive "xRy and yRz implies xRz" is most illuminating.

Now when x = z we have "xRy and yRx implies xRx", If R is reflexive "xRx" is always true and x = z is ok.

However, iff R is irreflexive "xRx" can never be true, hence x = z is false and x != z.

It seems to indicate that when R is irreflexive and transitive, x != z and the transitive property is meaningless when x = z. In other words when x = z "xRy and yRx implies nothing more than the two individual statements themselves imply" and it is NOT CORRECT to say that relation R is NOT Transitive. Note further that the above applies when relation R is symetric, anti-symetric or otherwise.

Now let's take a more concrete example:

Let x = John, y = Mary, z = Susan and R be the relation sibling.

John and Mary are siblings.

"John sibling Mary" and "Mary sibling John" implies "John and Mary are siblings" and nothing more.

Clearly when "John sibling Mary" is known then "Mary sibling John" adds nothing to the discourse because "Mary sibling John" is the same fact not two different facts.

now suppose the following is also true

Mary and Susan are siblings

then "John sibling Mary" and "Mary sibling Susan" implies "John sibling Susan" which adds to the discourse and is the meaning of the transitive property in the first place. [edit] —Preceding unsigned comment added by 64.231.95.9 (talk) 19:59, 11 November 2009 (UTC)

transtive, symmetric and irreflexive

The following doesn't make any sense:--345Kai 23:30, 7 September 2006 (UTC)

Relations that are transitive, symmetric, but irreflexive are very rare (e.g., the empty relation). The previous example illustrates why. More generally, if a relation R is symmetric and transitive, then for any x, y in the field of R, if xRy, then yRx (by symmetry), and xRx (by transitivity). Hence if there exist an x and y in the field of R, such that y≠x and xRy both come out true, the reflexivity of R follows and R must be an equivalence relation. R can be transitive, symmetric but irreflexive iff x is an "island," namely for an x that is not related to anything at all.

What you are objecting to is legacy material I found when I began my major edit of this entry. Feel free to edit or delete.202.36.179.65 14:59, 5 November 2006 (UTC)

From order to equivalence via symmetry

I think this paragraph is incomprehensible, misleading and even wrong

• what could be a "reflexive strict order" ?? strict means non-reflexive !
• what means "antisymmetry enhanced to full symmetry" ??

I think it's better to remove it... — MFH:Talk 21:41, 16 October 2006 (UTC)

Here's what I meant. Begin with a strict order. Then replace non-reflexivity with reflexivity and the result is an equivalence relation. Likewise, start with a partial order, then replace antisymmetry with symmetry to obtain, again, an equivalence relation. It is also valid to go the other way. A variety of of types of relations can be derived from an equivalence relation by suitably relaxing parts of the definition of an equivalence relation. I see relation types as forming a hierarchy in a manner similar to the way normal modal logics form a hierarchy. Equivalence relations are at the top of the relations hierarchy is a manner analogous to the way S5 is at the top of the normal modal logic hierarchy.202.36.179.65 15:11, 5 November 2006 (UTC)

you say "Begin with a strict order. Then replace non-reflexivity with reflexivity", but is that well-defined? In a 2-element set {a, b} if I define the strict partial order to be (a<b) (and thus also ~(b<a)) how do I make that reflexive? "~(b<a) and ~(a<b)" or "(b<a) and (a<b)"? Of course I end up with two equivalence relations, but they are different. If for a general set with s.p. order I have to find its ``corresponding`` equivalence relations, then what algorithm do I follow? Is the answer different from the set of all possible equivalence relations on that set? --MarSch 12:28, 27 November 2006 (UTC)

I rewrote parts of section 2 wishing to satisfy your objections. Does that section now meet with your approval? In any event, above I should have written "Begin with the concept of a strict order" and so on. You ask " If for a general set with s.p. order I have to find its ``corresponding`` equivalence relation, then what algorithm do I follow?" Given a concrete relation defined over a specific set, the answer is that there is no such algorithm.202.36.179.65 09:37, 7 March 2007 (UTC)

huh? What is being talked about here? Certainly you can union the diagonal (x,x) with whatever relation you begin with. Now it is reflexive. Similarly you can union with the reflection through the diagonal, thus you can make symmetric. You can take transitive closure, thus making the smallest transitive relation containing the one you begin with. Depending on starting properties, and the order you add pairs to your relation, you may end up with an ER. For example, for a SPO it is not enough to "reflexivise" then "symmetrize." You need to "transitivise" again! Maybe you are talking about something else, I don't know.24.58.63.18 (talk) 22:25, 15 March 2009 (UTC)

Some examples may indeed be confused and confusing

Most of the Examples are material I found when I began my major rewrite of this entry. More than one Example I cannot follow myself. My main contribution to the examples is pointing out that the usual number systems can all be defined as equivalence relations. My only contributions to the examples of non-equivalences are attempts to clarify by rewording, and those attempts are not a reason for any of you to hold your fire! In any event, those wishing to heavily edit or delete an example should feel free to do so.202.36.179.65 15:28, 5 November 2006 (UTC)

More concrete example of transitive, symmetric, but irreflexive

I think that the example (quote begins)

• The empty relation R on a non-empty set X (i.e. aRb is never true) is vacuously symmetric and transitive, but not reflexive (except when X is also empty).

(quote ends) could be supplied by the concrete case of the relation a R b = "a and b are both even numbers" on the set X of natural numbers (all natural numbers, not just the even numbers). This relation is clearly symmetric (if a and b are both even, b and a are both even), it is transitive (if a and b are both even and if in addition b and c are both even, a and c are both even), but it is not reflexive because 3 and 3 are not both even numbers. 129.132.146.184 09:13, 27 February 2007 (UTC)

Yup, that works. Paul August ☎ 02:37, 8 March 2007 (UTC)

not really. Not considering the headline is "irreflexive." The only relation with those 3 qualities is the empty relation.24.58.63.18 (talk) 22:30, 15 March 2009 (UTC)

Your example is a good one for 'transitive, symmetric, but not reflexive'. Unfortunately, 'irreflexive' doesn't mean 'not reflexive', it means 'never reflexive'. Adammanifold (talk) 21:27, 14 May 2009 (UTC)

A concrete example of an irreflexive, symmetric and transitive relation is Sibling(x,y) where x and y are elements of the set Person.

A commonly accepted definition of Sibling(x,y) is that x and y have the same parents and that x and y are distinct individuals.

The Sibling relation is clearly irreflexive; for all x an element of Person, Sibling(x,x) is false, by definition x is not a sibling of him or herself.

It is clear that the Sibling relation is symmetric; Whenever x and y are siblings, y and x are siblings.

It is also clear that the Sibling relation is transitive; Whenever (x and y are siblings) and (y and z are siblings), it is also true that (x and z are siblings).

Whenever a relation has the distinct individuals clause in its definition, it is irreflexive. Hence, it should be easy to find many examples with the above stated properties. —Preceding unsigned comment added by 64.231.125.50 (talk) 14:09, 10 November 2009 (UTC)

Equivalence relations on objects which are not sets

The article, as way of introduction to the idea of equivalence relation, cites examples of equivalence relations on the "set" of all human beings, and on physical objects. This has been raised previously, but nothing was done. I agree that in order to explain the idea of equivalence relation that these could be cited in a section of analogies of equivalence relations. However, since as far as I am aware neither human beings nor physical objects are members of any set that I am aware of (possibly they are, however, a class) then this should be removed or edited. Unless there are any objections, I shall do exactly that. Xantharius 20:32, 25 June 2007 (UTC)

Please, have a look at Set and in particular the words "any collection of distinct objects considered as a whole", and tell me how they do not apply to human beings or other physical objects. Thus, despite my lack of advanced mathematical compentences, I object (belatedly, also thereby further declaring that I belong to the set of people who object, and in fact the set of objects that object!) and kindly suggest your removal be undone. --Lasse Hillerøe Petersen 20:48, 16 July 2007 (UTC)

Reading further on in the article for set, we see that it has to be possible, for a collection to be a set, for us to be able to determine whether something is in or out of the set. Well, the idea of set might apply to human beings (maybe), but definitely does not apply to all physical objects, because not all physical objects can be well-defined, necessary for the idea of set to apply. There is no such thing as the set of all clouds, for example, because sometimes it's not possible to tell what is a cloud, and what isn't (How many clouds are there? Is that a cloud, or just some smoke? Are those clouds touching, or not? Does that make them two clouds, or just one?), and I think a cloud counts as a physical (if somehwhat nebulous) object. You might even want to say "solid objects", but then what counts as solid? While it might be argued that a cube of steel is solid, it's not solid if you heat it up high enough. Is the earth a solid object? What about a gel? It's very hard to be precise.

On the subject of humans, I wonder if an unborn baby is considered a human (I would hope so) and thus the equivalence relation "has the same birthday as" on the set of all humans is not well-defined, since there are some humans without birthdays.

Although the colours of the French flag are (possibly) well-defined (see discussion on set), defining objects to be collected is extremely difficult if there is any imprecision as to what exactly counts as defining the object. What colour is red, exactly? We all instinctively know what red is, and even what red is used in the flag, but can I talk about the set of all colours used on flags? I don't think so, because there is disagreement as to exactly what kinds of red are used on different flags.

This all might seem very picky, but I think I've already shown that equivalence relation does not apply to the "set" of all physical objects or the "set" of all humans. Yes, thermal equilibrium and birthdays are analogues of these ideas for non-mathematical scenarios, but they not equivalence relations proper. I have taken the idea of set as applying to collections of mathematical objects. With some work, I suppose that other ideas could be used. I'm going to leave it as it is, but feel free to have a go at precisely defining these ideas for humans and physical objects if you can. Xantharius 23:47, 16 July 2007 (UTC)

It would seem you are saying that because there can be ambiguous or unclear definitions of "human beings" or various other physical objects, it is impossible to talk about sets of any such objects. I think that conclusion is extreme. And I don't understand why you want to impose a different and narrower "standard" for what can constitute a set here, when it obviously doesn't agree with the definition on the Set page. At least be persistent and try have that page changed too: certainly the definition of what can constitute a set and what can not is no less important there than here, right?

(BTW, "same birthday as" can be well-defined if for example the unknown birthday is included as a possible birthday. And that's just one way to do it.)--Lasse Hillerøe Petersen 12:18, 17 July 2007 (UTC)

I understand your points. I think I would first state that I was coming from the point of view of axiomatic (rigorous) set theory, wherein there is no such thing as the set of humans because humans or collections of them cannot be constructed from mathematical ideas.

My main objection, on this basis, is the that the formal definition of "set" (see axiomatic set theory) is, in mathematics, actually a very narrow concept. Although the article on set says that one definition of set is "any collection M of definite, distinct objects m of our perception or of our thought (which will be called the elements of M) into a whole", this is a definition from naive set theory. In axiomatic set theory there is no such thing (and this is not my opinion by the way: it just doesn't exist) as the "set of all sets", or "the set of all groups". These things are too large to be sets: they are instead classes. And, indeed, if one knows about how sets really are constructed, it becomes apparent quite quickly that sets of things that aren't mathematical objects to begin with is impossible.

If we are going to stick with naive set theory, though, I suppose that there might be such a thing as the "set of all people". As far as physical objects go, however, that's a definite no, as I think it impossible to say for sure what constitutes and what does not constitute a physical object. I could consider that I am a physical object. And my hot steak on a plate might be, too. We are not in thermal equilibrium with each other since we are at different temperatures. If I eat the steak, are these objects now in thermal equilibrium, or is there now only one object? What happened to the steak? Is it in thermal equilibrium with me, or not? If one can't say yes or no, then the objects are not members of any real set which is going to be of use

I do take your point on the "set of all people", though, and will put this back in some form, as long as it understood that this comes from naive set theory. Xantharius 15:26, 17 July 2007 (UTC)

I think you are inviting a lot of philosophical rhetoric that is not needed in this context. How many physics and math articles would need to be rewritten to accommodate the the philosophical objection that objects in the real world are not well-defined? And why stop there? We could preface every article on WP with a few paragraphs on the problems of natural language and its referents. One reason it isn't even hypothetically possible to do this is that without some naive set theory you cannot do mathematics, (and without some naive understanding of our world you cannot build natural language), since you're not even sure what it means to be a symbol, let alone distinct symbols. When people first start learning about axiomatic set theory they make this mistake of assuming the mathematics can do itself, without any interpretation, all completely formally and automatically, but it cannot of course. I think it is implicit in "the set of human beings" that in fact what is being discussed is a model where it is unambiguous to determine whether something is a human or not a human. Most of us are comfortable thinking in this model, indeed it is necessary in order to communicate. —Preceding unsigned comment added by 24.58.63.18 (talk) 23:24, 15 March 2009 (UTC)

Rational numbers

Just a quick note: The relation (a,b) equivalent to (c,d) if ad=bc on N x N does not give all rational numbers, but only the positive rational numbers. To get all rationals you have to look at this relation as defined on Z x Z^*, but I'll leave it up to others to make this precise in the article. —Preceding unsigned comment added by 136.152.181.253 (talk) 17:40, 19 October 2007 (UTC)

conjugacy

What about complex, topological or conformal conjugacy ? Is it a Equivalence relation ? --Adam majewski (talk) 08:11, 31 January 2009 (UTC)

Topological conjugacy is an Equivalence relation ( see Scholarpedia )

subs --> subsets?

if this isn't a shorthand, please wikilink it. Thanks! —Preceding unsigned comment added by 128.32.35.76 (talk) 00:46, 13 August 2009 (UTC)

Just random vandalism. Algebraist 00:51, 13 August 2009 (UTC)

Euclid anticipated equivalence

This heading is clearly a complete fabrication and should be deleted. Even the editor who added it admitted to giving Euclid a very generous interpretation. Unless I hear strong objections to the deletion of the section in question I will delete it promptly. ReneGMata (talk) 14:46, 13 January 2010 (UTC)

I agree that in its present form the section is a stretch. However, "complete fabrication" seems a little strong, and it may be worth a mention that Euclid did make use of (essentially) the idea of equivalence in his deductive system. Perhaps a drastic rewrite and abbreviation, rather than total deletion, but I don't have time to do it now. JamesBWatson (talk) 17:03, 13 January 2010 (UTC)

It would be very nice if this section could be supported by reasonable citations or references. In fact it would be very nice if all the editors of Wikipedia adhered to facts rather than speculation. And yes, I believe that "stretching" (your word) is a form of speculation. And no, I do not think that a re-write of speculation will convert it into fact. ReneGMata (talk) 18:08, 14 January 2010 (UTC)

I was not suggesting rewriting speculation: I was suggesting rewriting the element of truth in there. Euclid certainly did use axioms which are now part of the definition of an equivalence relation, and I see no reason not to mention the fact. JamesBWatson (talk) 14:57, 18 January 2010 (UTC)

History

Euclid aside, where is the first recorded explicit defnition of equivalence relation? I think it would be worth adding to the article. Simplifix (talk) 12:15, 10 February 2010 (UTC)

Relations seems to be defined for other classes than "sets"

Jacobson mention that monoid isomorphisms define an equivalence relation (in Basic Algebra I, p. 37). So, is he considering "the set of all monoids"? Is this really a set? (is Mon a small category?)

If not, there should be a note about equivalence relation over more general classes? Helder (talk) 21:32, 13 May 2010 (UTC)