equivalence relation?

Question

An equivalence relation is a binary relation which satisfies the properties:

1) a~a (reflexivity)
2) if a~b then b~a (symmetry)
3) if a~b and b~c then a~c (transitivity)

Find the error in the following argument:
The reflexive property is redundant in the axioms for an equivalent relation. If x~y, then y~x by the symmetry property. Using the transitive property, we can deduce that x~x.

Can you find another axiom to replace axiom 1 such that the other two axioms do imply the new axiom 1?

Answer 1

The problem is that you are assuming that x~y for some y.

For example, if your set S is {1,2,3,4} and your relationship ~ is:

1 ~ 1
2 ~ 2
2 ~ 3
3 ~ 2
3 ~ 3

Then you can see that this satistfies properties 2 and 3, but it is not true that 4~4.

You can replace (1) with the property:

(1') For every a, there is a b such that a ~ b.

Answer 2

Assume that you have a non-empty set of elements and a relation on it, such that the relation is never true.

Then since a~b is never true, a~b ==> b~a vacuously.
Also since a~b and b~c are never true, a~b and b~c ==> a~c is true vacuously.

But a~a is not true.

Thus this is symmetric, transitive, but not reflexive.

Let's assume that the original set of axioms {1,2,3} is denoted by A. Let B denote {1',2,3} where 1' is a result of 2 and 3.

I hope you are humoured by this part.

Define a relation ~ on the set of definitions of an "equivalence relation" such that two definitions X and Y are equivalent (denoted X~Y) if it can be shown that these define "equivalence relation" in the "same" (up to a "definition-morphism") way.

It would be easy to see that this is an equivalence relation (knowing that "definition-morphic" is an equivalence relation).

Now assume that A~B. Since 1' is a result of 2 and 3, B~B\{1'}. Therefore by the transitive property A~B\{1'}, but we already have shown that this is not true.

Thus there does not exist an equivalent definition of "equivalence relation" such that 2 and 3 imply 1'.

Answer 3

Let us be precise and let ~ be an equivalence relation on the set E. The argument you outline starts with 2), that is:

FOR ALL a, b in E, IF a~b THEN b~a.

By 3) we have the following statement, which we call Theorem 1*:

FOR ALL a, b in E, IF a~b THEN a~a. (Theorem 1*)

The important fact here is that Theorem 1* is *different* from Axiom 1), which states:

FOR ALL a in E, a~a.

An example of a relation on E which satisfies 2) and 3) but not 1) is the "empty relation". This is a relation where a~b doesn't hold for *any* a, b in E.

If we replaced 1) with Theorem 1*, then 2) and 3) would imply 1).

Answer 4

The new "axiom" or rather "theorem" would be:

1*) If x~y for at least one y<>x, then x~x.


To see that, suppose that element x is isolated, that is, x~y is false for any y<>x. In that case, the "if x~y" in your argument can never be true, so we can't conclude anything. Choosing y = x does not help either, because the reasoning "if x~x then x~x, therefore x~x" is clearly circular.

Answer 5

Mmmm, Herstein Problem 1.1.11.

Answer 6

isnt it amazing