Dependence of Axioms of Equivalence Relation?

Question

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

Answer 1

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.

Answer 2

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.

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

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

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