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)

I misread the relation "a ~ b" iff a and b are both even as "a ~ b" iff a = b (mod 2), which isn't quite the same. Sorry about the misedit there. JamesBWatson restored it correctly, although I'm still not sure that it should be in the definition section. Antares5245 (talk) 09:00, 12 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)

This is not transitive.

If John sibling Mary, then Mary sibling John. By transitivity, John sibling John. Which we already defined to be not part of the relation. Therefore it is NOT transitive. This wikipedia article is the reason why half my math class got this wrong. — Preceding unsigned comment added by 209.6.94.214 (talk) 07:25, 12 February 2012 (UTC)

Why is this article to blame for half your class getting it wrong? It states quite clearly that “sibling” is not an equivalence relation, and it explains why. So the reason must lie elsewhere, is my guess. Hanche (talk) 10:46, 12 February 2012 (UTC)

The article states that is a sibling of is transitive on set of 3 distinct people A,B,C. Since this is not the same as transitive I find the example misleading, and I think it should be removed.80.216.62.225 (talk) 08:53, 15 August 2012 (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)

Please at least one sane example to this article... like taking set of {1,2,3} and building equivalence relations {(x0,y0),(x1,y1)...} using this set. Consider that most readers of this article will be math students like myself. Finding pictographs with obscure meaning is absolutely unhelpful. — Preceding unsigned comment added by 79.183.12.73 (talk) 17:15, 1 May 2012 (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)

The problem is that such a relation isn't transitive either. 2A01:CB10:21:8500:F110:46D6:DB03:EAAB (talk) 21:56, 23 July 2022 (UTC)

That is right. Also, 24.58.63.18's post of 15 Mar 2009 above is right: if R is transitive, symmetric, and non-empty, then aRb holds for some a,b. By symmetry, bRa also holds, Hence, aRa by transitivity from aRb and bRa. That is, R cannot be irreflexive. - Jochen Burghardt (talk) 14:44, 24 July 2022 (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)

The relation of equipollence used by Giusto Bellavitis is an early example with a suggestive label.Rgdboer (talk) 23:01, 3 November 2014 (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)

I too have been feeling like relations should be defined on classes. Doesn't the usual definition of cardinal numbers rely on partitioning the (proper) class of all sets into equivalence classes? That might be important enough to include as a blurb. Rschwieb (talk) 00:47, 26 July 2011 (UTC)

Theorem on projections partially wrong

It is currently written:

Theorem on projections: Let the function f: X → B be such that a ~ b → f(a) = f(b). Then there is a unique function g : X/~ → B, such that f = gπ. If f is a surjection and a ~ b ↔ f(a) = f(b), then g is a bijection.

I think the last sentence is wrong, and here is a counter-example. Let the set X have two elements. Let the equivalence relation be the equality, i.e. a ~ b ↔ a = b. Let the set B be a singleton. The function f: X → B is a constant function and is a surjection. But g : X/~ → B can not be a bijection since X/~ has two elements but B only one. Frozsyn (talk) 12:45, 16 November 2010 (UTC)

In your example, if f is a constant function from a two element set {a,b} to a one element set, since a is not equivalent to b, f does not have the property that a ~ b ↔ f(a) = f(b). That extra property in the last sentence is important. — Carl (CBM · talk) 12:55, 16 November 2010 (UTC)

Thanks for the reply! Somehow, I re-read the statement many times without noticing the property a ~ b ↔ f(a) = f(b). I assumed only a ~ b → f(a) = f(b) as written in the first part. My bad. Frozsyn (talk) 14:16, 16 November 2010 (UTC)

Isn't it ≈ & NOT ~

Hmmmmmmm? Alt 247 —Preceding unsigned comment added by 173.218.85.222 (talk) 20:06, 16 February 2011 (UTC)

No. Algebraist 20:07, 16 February 2011 (UTC)

Imprecise definition of partition

A partition of X is a set P of nonempty subsets of X such that every element of X is an element of a single element of P.

Correct, fixed. McKay (talk) 01:47, 21 February 2011 (UTC)

Projection (relational algebra)

The link to the Projection (relational algebra) (main article) in the "Projection" chapter, is it relevant at all? Should not the "projection" be called the "quotient map"? I do not see how projections and quotient maps are related. --Beroal (talk) 22:59, 1 March 2011 (UTC)

Poor lede

Intersection of three independent conditions

The current lede is unmathematical and suggests segregation:

In mathematics, an equivalence relation is the relation that holds between two elements if and only if they are members of the same cell within a set that has been partitioned into cells such that every element of the set is a member of one and only one cell of the partition. The intersection of any two different cells is empty; the union of all the cells equals the original set. These cells are formally called equivalence classes.

The fact that equivalence classes are the outcome of an equivalence relation is reported deep in the article. As it stands, the article encourages the enemies of social equality who would perpetuate social classes such as the caste system in India. There are elements that feed off class conflict and the lede of this article, which should be on mathematics, suggests that division is natural. The lede should be rewritten as an article on binary relations, with the partition reserved for a conclusion following from the three intersecting properties.Rgdboer (talk) 22:31, 20 July 2015 (UTC)

@Rgdboer: Are you serious? — Arthur Rubin (talk) 20:15, 2 January 2016 (UTC)

The impression was strong enough that it led me to make edits at Social equality in August. — Rgdboer (talk) 21:08, 2 January 2016 (UTC)

The following is my suggestion for the lede:

An equivalence relation is a binary relation that is at the same time a reflexive relation, a symmetric relation and a transitive relation. As a consequence of these properties an equivalence relation provides a partition of a set into equivalence classes.

As written, the current lede (still as quoted above) describes the Partition of a set, not a binary relation upon it. Since 93 Watch this article, discussing a proposed change of lede before posting may produce a consensus. — Rgdboer (talk) 00:53, 3 January 2016 (UTC)

It's an improvement; I think, but, per WP:TECHNICAL, it might be a good idea to include the definition of partition of a set in the lead, as as well. I think the following is a little better, but I'm a professional mathematician, so I'm familiar with the terms involved. How about:

An equivalence relation R over a set X is a binary relation over X that is reflexive, symmetric, and transitive. As a consequence of these properties, an equivalence relation R corresponds to a partition of X.

I think that's both accurate and understandable, but I'll defer to others on "understandable". — Arthur Rubin (talk) 06:12, 3 January 2016 (UTC)

We still need to introduce equivalence classes in the lede, though. I'm just proposing a first sentence. — Arthur Rubin (talk) 06:19, 3 January 2016 (UTC)

In using WP:Pipes it says "keep links as simple as possible." For instance, Partition is a disambiguation page listing 7 mathematical uses of the term so your pipe of Partition of a set leads a reader to underestimate the expanse of the term. Similarly piping the three relation links to their adjectives makes the reading smooth, but detracts from the emphasis on Relation. These comments pertain to internet linguistics and hyperlink grammar, recent developments with differing opinions. However, since the two versions are nearly identical except for these points, the change is due. — Rgdboer (talk) 21:31, 7 January 2016 (UTC)

I can see your point about partition of set, although it makes the sentence slightly incorrect. I disagree about use of relation, though. My version is exactly the way it would be written in a math textbook, is understandable, and has the proper links. The only people hurt are offline readers who don't understand the basic material, and it doesn't hurt them much. — Arthur Rubin (talk) 06:55, 9 January 2016 (UTC)

What do you mean, "...it makes the sentence slightly incorrect" ? — Rgdboer (talk) 20:29, 9 January 2016 (UTC)

Cell

The technical term 'cell' appears to have no entry in the disambiguation page for 'cell'. Jim Bowery (talk) 22:17, 1 January 2016 (UTC)

I've never seen "cell" used in this context in the mathematical literature. A quick Google search finds only a few Wikipedia articles and some quotes from Wikipedia. Objects in "cell"s or "bin"s are sometimes used as examples of equivalence relations. — Arthur Rubin (talk) 20:13, 2 January 2016 (UTC)

The Encyclopedia of Mathematics has no such entry. I think it may be original to Wikipedia. — Arthur Rubin (talk) 20:25, 2 January 2016 (UTC)

@Arthur Rubin: "Cell" and "equivalence relation" are an unusual combination, but "cell" and "partition" (of a set) are often used together. If you search at Scholar for "cell of the partition" and "cells of the partition" (with quotes) you'll find many examples. Given that partitions and equivalence relations are more or less the same concept, that's enough to justify the mention of cells here, imo. McKay (talk) 01:24, 17 March 2016 (UTC)

Math style

@Rushikeshjogdand1: WP:MOSMATH#Typesetting of mathematical formulae says that formatting should not be changed without clear improvement or consensus. Your edit introduced a mix of formattings, as you changed only a part of the article; this was certainly no improvement. For this reason, I reverted your edit. Apart from that, there are problems with the <math> format, such as ugly rendering in Png mode, and MathJax mode sometimes having its caveats, if I remember right. As far as I know, using {{math}} formatting is the most promising alternative to both Html and <math>. - Jochen Burghardt (talk) 22:02, 15 March 2016 (UTC)

OK. And thanks.

I did not know that there are problems with <math> tag and mathjax.Thought that this is the best way to display math currently.

Rushikeshjogdand1 (talk) 04:31, 16 March 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Equivalence relation. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20130509233055/http://planetmath.org/equivalencerelation to http://planetmath.org/equivalencerelation

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 07:10, 25 December 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Equivalence relation. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive http://arquivo.pt/wayback/20160514115224/http://www.bangor.ac.uk/r.brown/topgpds.html to http://www.bangor.ac.uk/r.brown/topgpds.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 05:56, 22 September 2017 (UTC)

Major Mistake

Skimming this article at 9:01 am, US Central Time, on Friday, July 23rd, 2021, I found the following mistake. I'd correct it immediately if I knew how to do that, but regrettably, I don't know how to edit or write formulas on Wikipedia. In any case, here is the error:

Symmetric and transitive: The relation R on N, defined as aRb ↔ ab ≠ 0. Or any partial equivalence relation;

Transitive means that if aRb and bRc, then aRc. Consider a=2, b=3, and c=2. This counter-example proves that ≠ is not transitive, because 2≠3 is true, and 3≠2 is true, yet 2≠2 is false.

We therefore require a replacement relation that is symmetric and transitive but not reflexive. I would recommend a binary relation that I call the "department head" relation. What ever request you make, the answer is always "no." In other words, for all x and for all y, xRy is false. This binary relation is not reflexive, but it is symmetric, and it is transitive. (Any one who has ever worked in education will find this example intuitive and familiar.)

Respectfully submitted, Gregorybard (talk) 14:09, 23 July 2021 (UTC)

You are right that ≠ itself isn't transitive. However, R defined by aRb ↔ ab ≠ 0 is transitive. (Note that R is different from ≠, e.g. 2R2, but not 2≠2, and e.g. 0≠1, but not 0R1.) The definition of R can be re-phrased as aRb ↔ a≠0 ∧ b≠0. Then aRb and bRc implies a≠0 and b≠0 and c≠0 by the alternate definition, hence a≠0 ∧ c≠0, hence aRc. BTW: your "department head" relation is known as the empty relation. I feel it is too particular to be the only example for a partial equivalence. - Jochen Burghardt (talk) 14:42, 23 July 2021 (UTC)

I find this example and the one given in the article interesting. However they both look like ternary relations in disguise (between a, b and 0, in this case). Which seems inevitable for a non-empty non-reflexive relation to be both symmetric and transitive. I don't know if this is true, have no idea how it could be proved and realize that it doesn't make the example any less correct or relevant. I just thought it would be cool if someone more knowledgeable could explain why. 2A01:CB10:21:8500:CD8:3FB4:5BD5:E3AE (talk) 11:28, 25 July 2022 (UTC)

I'd like to spend some effort on trying to prove your conjecture - if I'd understand what exactly it consists of. Maybe "Every non-empty non-reflexive relation that is both symmetric and transitive is a ternary relation in disguise." But then, how to formalize "ternary relation in disguise"? - Jochen Burghardt (talk) 17:52, 25 July 2022 (UTC)

Transitive Relation

If (a, b), (b, c) (a, c) belongs R, and (b, b) doesn't belongs to R then will it be transitive or not. If not then why? 2409:4063:420B:CD60:75BF:7362:1CFF:DB7E (talk) 05:12, 5 December 2021 (UTC)

Composition notation

Writing the composed relations R and S in the backward fashion of function composition is not recommended. A section using calculus of relations institutes this notion. It ignors the left to right reading of relations. Seeking consensus here to repress this perverse initiative. The greater than (>) and less than (<) relations show importance of direction of text. Habits from calculus of real and complex variables need reformation when addressing relations. Rgdboer (talk) 04:05, 8 June 2022 (UTC)

"simple" example - what are the square brackets?

What are the square brackets in the "simple example" and why are these equivalent classes?

Quote (more or less):

On set X={a,b,c}, R={(a,a),(b,b),(c,c),(b,c),(c,b)} is an equivalence relation.

The following sets are equivalence classes of this relation:

[a]={a}, [b]=[c]={b,c}. [a]={a}, [b]=[c]={b,c}.

פשוט pashute ♫ (talk) 18:55, 16 November 2022 (UTC)

Evidently [–] assigns an element of the set to its equivalence class. Rgdboer (talk) 01:23, 17 November 2022 (UTC)

undue

More examples should be given for quotient sets inherting mathematical properties of the original set (assuming appropriate requirements to the equivalence relation, where necessary). All the examples should be preceeded by a general introduction of 1-2 sentences. The first examples that come to my mind are the construction of the number sets C, R, Q, Z; however, they use pretty particular relations. Some of them may have been generalized, like C=R/~ to field extension. - Jochen Burghardt (talk) 18:55, 29 October 2024 (UTC)

Do you mean the isomorphism theorems ? — Rgdboer (talk) 00:36, 30 October 2024 (UTC)

I'm not too familiar with them. From the introductory sentences at Isomorphism_theorems#Universal_algebra, we could include a summary here (e.g. "If ~ is a congruence relation on a group G, then the quotient set G/~ is a group, too. The same holds for rings, vector spaces, and any other type of algebra.").

Afaik, it doesn't hold for fields, since they can't be defined by equational axioms alone ($0\neq 1$ is required); if I remember correctly, this should be noted at Isomorphism theorems (but not here), imo. Jochen Burghardt (talk) 11:53, 30 October 2024 (UTC)