Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is problem 11(a) in chapter 1 in 'Topics in Algebra' by I.N. Herstein.

These are the properties of equivalence relation given in this book.

  • Prop 1 $a \sim a$
  • Prop 2 $a \sim b$ implies $b \sim a$.
  • Prop 3 $(a \sim b$ and $b \sim c)$ imply $a \sim c$.

Statement Property 2 of an equivalence relation states that if $a \sim b$ then $b \sim a$. By property 3, we have the transitivity i.e. $a \sim b$, and $b \sim c$ then $a \sim c$. What is wrong with following proof that property 2 and 3 imply property 1? Let $a \sim b$; then $b \sim a$, whence by property 3 (using $a = c$), $a \sim a$.


I think I can prove this to be wrong. Without proving equivalence relation first, one can not use $a = c$. Right? After all, equality is equivalent to 'equivalence relation' and 'axiom of substitution' are satisfied. If this is right, then I have trouble with the next part of this problem.


Part 2 Can you suggest an alternative of property 1 which will insure us that prop 2 and prop 3 do imply 1?

Can one give such a formulation without using the idea of '=' or otherwise?


EDIT : Italics are my comments. Rest is as it appeared in the book.

Notion of Equality

I have read in Terry 'Analysis 1' in Appendix A.7 published by ** Hindustan Book Agency ** that there are four axioms of 'equality'. First 3 are same as equivalence relation where $\sim $ in replaced by $ = $. The fourth one is know as axiom of substitution. Given any two objects $x$ and $y$ of some type, if $ x = y $, then $f(x) = f(y) $ for all functions or operations $f$.

share|improve this question
    
Tried. Finally \sim worked. –  Dilawar May 15 '11 at 16:30
    
By context that qould be reflexivity, symmetry, and transitivity in this order. –  Peter Patzt May 15 '11 at 16:34
    
Ok, One minute. –  Dilawar May 15 '11 at 16:36
    
I think you should maybe rephrase the part 2 of your question. Is this still part of the book or your own? What would such a property really help the case, if it is implied by symmetry and transitivity? And at last the three properties could then obviously not imply the notion of equivalence. –  Peter Patzt May 15 '11 at 16:42
    
Yeah, the second part is also in book. –  Dilawar May 15 '11 at 16:55

5 Answers 5

up vote 5 down vote accepted

Part 1. Here's an example of a relation that is symmetric and transitive, but not reflexive.

The set is $X=\{1,2,3\}$. The relation is $$R = \Bigl\{ (2,2),\ (2,3),\ (3,2),\ (3,3)\Bigr\}.$$ Verify that $R$ is symmetric and transitive. Verify that $R$ is not reflexive. Then try to see why the alleged proof fails in this example. Use that to explain where the fallacy in the proof lies. It does not lie in taking $c$ equal to $a$.

Part 2. Think about what the fallacy is in the proof you are given; what extra hypothesis on $\sim$ would make the argument correct? The argument is fallacious because it assumes that something happens, when you have no warrant for asserting it will happen. So try to come up with some hypothesis that will guarantee this happens.

share|improve this answer
    
Lets assume that $R$ contains all possible relation. Does that imply that prop 1 is redundant i.e. by using 2 and 3, I can prove 1 (using $ a = c $ ). Can we drop prop 1 altogether when $R$ is a 'complete' set of relation? –  Dilawar May 15 '11 at 20:15
    
@Dilawar: A relation is a set of ordered pairs. "$R$ contains all possible relation" makes no sense. Did you mean "Suppose $R$ contains all of $X\times X$"? Yes, the set of all pairs satisfies all three conditions, but that's not what the question is asking you to do. The question is "What extra property will be enough to guarantee that the proposed proof goes through?" You don't need to add everything to $R$ to make it work, you can do with a lot less. –  Arturo Magidin May 15 '11 at 20:49
    
@Dilawar: To nudge you in the right direction: have you figured out what the error in Part 1 is? What is the unwarranted assumption being made, or the incorrect conclusion being drawn? –  Arturo Magidin May 15 '11 at 21:52
    
@Magidin First, even if $R$ is symmetric and transitive, it is not a sufficient condition for $R$ being reflexive. I think that this is an unwarranted assumption. –  Dilawar May 16 '11 at 3:49
1  
@Dilawar: You misunderstand me. You were given an argument which is fallacious that claims to show that if $R$ is symmetric and transitive, then $R$ is reflexive. We know it's fallacious, because we have a counterexample. That argument is, like all arguments, a sequence of steps. Now, somewhere there is a first step which is wrong; it's wrong either because it asserts something which is not justified on the basis of previous steps, axioms, tautologies, or hypothesis. What is that first step that is wrong, and what is it asserting that is without warrant? –  Arturo Magidin May 16 '11 at 3:53

For the first part: The "proof" assumes that for $a$ there is a $b$ such that $a\sim b$. This of course is not necessaryly given. The empty relation i.e. for no $a,b$ we have $a\sim b$ is transitive, symmetric but not reflexive. (This example seems to many students not very explainitory although it is the simplest example of this situation. See the example of Arturo Magidin if that helps.)

For the second part: I think the book might ask for something like this.

Prop 1': For any $a$, for which there is any $b$ such that $a\sim b$, we also have $a\sim a$.

This might seem to be an weird property, but we could also take "suffices Prop 2 and Prop 3", which wouldn't make much more sense.

Or as Arturo Magidin suggested

Prop 1'': For any $a$, there is a $b$ such that $a\sim b$

together with Prop 2 and Prop 3 implies Prop 1.

share|improve this answer
    
How can it be that for all $a, b \in S$, $a \not\sim b$ is transitive on $S$? -- unless you add the following qualification: "for all distinct $a, b \in S,\not\sim$ is symmetric and transitive on $S$. Otherwise, you have that, given symmetry, for any $a, b \in S, a \not\sim b \implies b \not\sim a$, by symmetry. So, provided $a \not\sim b$, together with its implication by symmetry that $b \not\sim a$, then by transitivity, it must follow that $a \not\sim a$, which as you note, fails. So your "counter-example" fails to be both symmetric and transitive. –  amWhy May 15 '11 at 20:38
    
...That is, while symmetric, transitivity fails. –  amWhy May 15 '11 at 20:42
    
I edited my answer to make it clearer what kind of relation I actually meant. –  Peter Patzt May 15 '11 at 23:06
    
@Peter: Actually, you can replace Prop 1 simply by "For every $a$ there exists $b$ such that $a\sim b$"; then Prop 1', Prop 2, and Prop 3 will imply Prop 1; I suspect that's the intended meaning of the problem. (That is, you want 1', 2, and 3 to imply 1, not a 1' that is implied by 2 and 3). –  Arturo Magidin May 15 '11 at 23:10
    
@Arturo: That would make a lot of sense, although then the excercise is poorly phrased. –  Peter Patzt May 15 '11 at 23:32

There is no difficulty in supplying a "Prop. $0$" strictly weaker than Prop. $1$ such that Prop. $0$ and Props. $2$ and $3$ imply the current Prop. $1$. Just say that for any $x$ there is a $y$ such that $x \sim y$. (Of course that $y$ might be $x$ itself.) Then Prop. $0$, together with $2$ and $3$, imply Prop. $1$. Thus Prop. $0$, $2$, and $3$ give an alternate axiomatization. Perhaps this is the intended answer. Or not.

share|improve this answer

The problem is that property 1 should hold for any element of the set. Consider a set on which you define an equivalence relation such that an element x of the set is not equivalent to anything. In particular, you won't be able to use 2 and 3 on it. Now property 1 fails since x must be equivalent at least to itself.

share|improve this answer

The axioms are supposed to hold for all choices of $a, b, c$, and this includes the case where $c$ happens to equal $a$. When you conclude that $a \sim b$ and $b \sim a$ implies $a \sim a$, you are only using transitivity and no other property.

I don't understand what you mean by "the idea of '='." It is pretty hard to do any mathematics without using the notion of equality.

share|improve this answer
    
I have read in Terry 'Analysis 1' in Appendix A.7 published by Hindustan Book Agency that there are for axioms of equality. –  Dilawar May 15 '11 at 17:16
    
Seethe updated ques for notion of equality. –  Dilawar May 15 '11 at 17:29
    
Yes, and these axioms are always assumed to hold regardless of what axioms are assumed to hold for $\sim$. –  Qiaochu Yuan May 15 '11 at 17:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.