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

  • 0
    Tried. Finally \sim worked.2011-05-15
  • 0
    By context that qould be reflexivity, symmetry, and transitivity in this order.2011-05-15
  • 0
    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.2011-05-15
  • 0
    Yeah, the second part is also in book.2011-05-15
  • 0
    If memory serves me correctly, this is a problem in Herstein's Topics in Algebra.2011-05-15
  • 0
    @ncmathsadist: In my Spanish version, it is problem 11 from Section I.1; part (b) reads (my translation, and remember the old 'the meat is rotten but the vodka is good' phenomenon for translating back a translation) "Can the reader suggest an alternative to property 1 that will guarantee that properties 2 and 3 imply property 1?"2011-05-16
  • 0
    Related: http://math.stackexchange.com/questions/440/why-isnt-reflexivity-redundant-in-the-definition-of-equivalence-relation2011-11-06

5 Answers 5

11

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.

  • 0
    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?2011-05-15
  • 1
    @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.2011-05-15
  • 1
    @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?2011-05-15
  • 0
    @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.2011-05-16
  • 2
    @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?2011-05-16
  • 0
    @Dilawar: Exactly: that's the unwarranted assumption: that given $x$, there *must* exist some $y$ with $x\sim y$. If you look at the example I give, this is false when $x=1$, which is *precisely* why $R$ is not reflexive. So, if you wanted to make the argument correct without going all the way to assuming reflexivity (or assuming that $R$ is *all* of $X\times X$, what would be *just enough* to make the given argument valid?2011-05-16
  • 0
    Oh, I deleted the previous comment. I thought it was not mathematically precise statement. Anyway, we make sure that for a given $x$ there is some $y$ with $x \sim y$ and for the same $y$ and $x$ we also have $y \sim x$, then we'll have $x \sim x$ and $y \sim y$ also. Is that right?2011-05-16
  • 0
    @Dilawar: Exactly. So, if instead of Prop 1, we had the *strictly weaker* statement "For all $x$ there exists $y$ such that $x\sim y$" (weaker because there are relations that satisfy this but are not reflexive, but every reflexive relation certainly satisfies this), then this weaker statement *together with* Props 2 and 3, *do* imply reflexivity.2011-05-16
  • 0
    The set $X$ is not reflexive since it does not contain $(1,1)$, right?2018-01-10
  • 0
    @RFZ: Correct..2018-01-10
6

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.

  • 0
    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.2011-05-15
  • 0
    ...That is, while symmetric, transitivity fails.2011-05-15
  • 0
    I edited my answer to make it clearer what kind of relation I actually meant.2011-05-15
  • 0
    @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).2011-05-15
  • 0
    @Arturo: That would make a lot of sense, although then the excercise is poorly phrased.2011-05-15
  • 0
    @Peter: I agree it is poorly phrased; I arrive at my "intended meaning" based on seeing that particular problem in several different sources before...2011-05-15
  • 0
    @Peter, @Arturo I have edited the problem. Italics statement are my comment on this problem. Rest is as it appeared in the book. I am still preoccupied with the idea that author is asking : given $R$ which contains all of $X \times X$, discuss if prop 1 is redundant and can be expressed in terms of Prop 2 and Prop 3?2011-05-16
  • 0
    Given $R= X\times X$, we have a specific equivalence relation that says any two elements of $X$ are equivalent. Hence it is not a matter of showing Prop 2 and 3 implies 1 but all these properties hold for this particular $R$.2011-05-16
5

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.

4

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.

  • 0
    I have read in Terry 'Analysis 1' in Appendix A.7 published by Hindustan Book Agency that there are for axioms of equality.2011-05-15
  • 0
    Seethe updated ques for notion of equality.2011-05-15
  • 0
    Yes, and these axioms are always assumed to hold regardless of what axioms are assumed to hold for $\sim$.2011-05-15
3

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.

  • 0
    That certainly is not an **equivalence** relation...2015-08-01