Quantification logic and equivalence relations

[nhamann]

I wasn't sure whether to post this in the algebra forum or here, but it seems that this is more of a logic question so I'm going with here. I am trying to understand whether there is a difference between the following two definitions of an equivalence relation:

Definition 1: A binary relation R on set A is an equivalence relation if:

1. \forall a \in A \ a R a
2. \forall a, b \in A \ a R b \implies b R a
3. \forall a, b, c \in A \ a R b \land b R c \implies a R c

Definition 2: A binary relation R on set A is an equivalence relation if \forall a, b, c \in A:

1. a R a
2. a R b \implies b R a
3. a R b \land b R c \implies a R c

Definition 1 can be found in Dummit & Foote's Abstract Algebra, while Definition 2 can be found in Topics in Algebra by Herstein. A professor told me that the second definition is incorrect. However, it seems to me that the definitions are the same.

My present idea is that the following two statements are equivalent:

1. \forall x \ P_1(x) \land \forall y \ P_2(y)
2. \forall x \ P_1(x) \land P_2(x)

where P_1 and P_2 are propositional functions. To me, then, it seems that you should be able to do the following:

let P_1(a) = a R a
let P_2(a, b) = a R b \implies b R a
let P_3(a, b, c) = a R b \land b R c \implies a R c

Definition 1 can now be written as:

Definition 1a: A binary relation R on set A is an equivalence relation if:

[\forall a \in A \ P_1(a)] \ \land \ [\forall b, c \in A \ P_2(b, c)] \ \land \ [\forall d, e, f \in A \ P_3(d, e, f)]​

It seems that this is analogous to the situation above, so that the universal quantifiers can be collapsed:

\forall a, b, c \in A \ P_1(a) \land P_2(a, b) \land P_3(a, b, c)​

This latter statement is equivalent to Definition 2.


While this reasoning seems solid to me, I do not have a strong enough grasp of logic to be completely convinced of it. Can anyone fill me in where my analysis is wrong if it is wrong, and perhaps point me towards what I should study in order to understand this better?

 

[MathematicalPhysicist]

Yes they are equivalent.

 

[JSuarez]

The problem is that some mathematicians are a little sloppy with logic notation. Both definitions are equivalente; in the second one it's assumed that the quantification is over the conjunction of the three formulas, while in the first, the author quantifies each one independently. Personally, I prefer the first one and, regarding logical form, is more correct. Mathematically, they are equivalent.

Regarding your argument, it's basically correct either; just a few comments, thought:

1. When you write something like this:
<br /> \forall x \ P_1(x) \land P_2(x)<br />
You should use parenthesis:
<br /> \forall x \left(P_1(x) \land P_2(x)\right)<br />
Otherwise, the expression is ambiguous: I assume that your intended meaning is that the quantifier bounds both variables but, without parenthesis, it could be read as an expression with a free variable, with a completely different meaning.

2. When you transport the universal quantifiers to the beginning of the formula, as they quantify over distinct bound variables, you should rename them first. But this is a minor point, only of interest to logicians.