Talk:Equivalence relation

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class Top Priority  Field: Foundations, logic, and set theory

Contents

[edit] 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)

[edit] 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 z1,...,zn of intermediate elements, and for each i one has to allow for R(zi,zi+1) *or* R(zi+1,zi). AxelBoldt 22:10 Nov 23, 2002 (UTC)

[edit] "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))

[edit] 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

[edit] 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)

[edit] 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)

[edit] "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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)

[edit] 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)