11
$\begingroup$

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 known 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$.

$\endgroup$
7
  • $\begingroup$ Tried. Finally \sim worked. $\endgroup$
    – Dilawar
    May 15, 2011 at 16:30
  • $\begingroup$ By context that qould be reflexivity, symmetry, and transitivity in this order. $\endgroup$
    – Peter Patzt
    May 15, 2011 at 16:34
  • $\begingroup$ 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. $\endgroup$
    – Peter Patzt
    May 15, 2011 at 16:42
  • $\begingroup$ Yeah, the second part is also in book. $\endgroup$
    – Dilawar
    May 15, 2011 at 16:55
  • $\begingroup$ If memory serves me correctly, this is a problem in Herstein's <i>Topics in Algebra</i>. $\endgroup$
    – ncmathsadist
    May 15, 2011 at 19:33

5 Answers 5

Reset to default
11
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ 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? $\endgroup$
    – Dilawar
    May 15, 2011 at 20:15
  • 1
    $\begingroup$ @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. $\endgroup$
    – Arturo Magidin
    May 15, 2011 at 20:49
  • 1
    $\begingroup$ @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? $\endgroup$
    – Arturo Magidin
    May 15, 2011 at 21:52
  • $\begingroup$ @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. $\endgroup$
    – Dilawar
    May 16, 2011 at 3:49
  • 2
    $\begingroup$ @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? $\endgroup$
    – Arturo Magidin
    May 16, 2011 at 3:53
6
$\begingroup$

For the first part: The "proof" assumes that for $a$ there is a $b$ such that $a\sim b$. This of course is not necessarily 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 explanatory 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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – amWhy
    May 15, 2011 at 20:38
  • $\begingroup$ ...That is, while symmetric, transitivity fails. $\endgroup$
    – amWhy
    May 15, 2011 at 20:42
  • $\begingroup$ I edited my answer to make it clearer what kind of relation I actually meant. $\endgroup$
    – Peter Patzt
    May 15, 2011 at 23:06
  • $\begingroup$ @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). $\endgroup$
    – Arturo Magidin
    May 15, 2011 at 23:10
  • $\begingroup$ @Arturo: That would make a lot of sense, although then the excercise is poorly phrased. $\endgroup$
    – Peter Patzt
    May 15, 2011 at 23:32
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

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

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.

$\endgroup$
1
  • $\begingroup$ That certainly is not an equivalence relation... $\endgroup$
    – vonbrand
    Aug 1, 2015 at 23:05

Not the answer you're looking for? Browse other questions tagged .