- #1
nhamann
- 1
- 0
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:
Definition 2: A binary relation R on set A is an equivalence relation if [tex]\forall a, b, c \in A[/tex]:
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:
where [tex]P_1[/tex] and [tex]P_2[/tex] are propositional functions. To me, then, it seems that you should be able to do the following:
let [tex]P_1(a) = a R a[/tex]
let [tex]P_2(a, b) = a R b \implies b R a[/tex]
let [tex]P_3(a, b, c) = a R b \land b R c \implies a R c[/tex]
Definition 1 can now be written as:
Definition 1a: A binary relation R on set A is an equivalence relation if:
It seems that this is analogous to the situation above, so that the universal quantifiers can be collapsed:
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?
Definition 1: A binary relation R on set A is an equivalence relation if:
- [tex]\forall a \in A \ a R a[/tex]
- [tex]\forall a, b \in A \ a R b \implies b R a[/tex]
- [tex]\forall a, b, c \in A \ a R b \land b R c \implies a R c[/tex]
Definition 2: A binary relation R on set A is an equivalence relation if [tex]\forall a, b, c \in A[/tex]:
- [tex]a R a[/tex]
- [tex]a R b \implies b R a[/tex]
- [tex]a R b \land b R c \implies a R c[/tex]
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:
- [tex]\forall x \ P_1(x) \land \forall y \ P_2(y)[/tex]
- [tex]\forall x \ P_1(x) \land P_2(x)[/tex]
where [tex]P_1[/tex] and [tex]P_2[/tex] are propositional functions. To me, then, it seems that you should be able to do the following:
let [tex]P_1(a) = a R a[/tex]
let [tex]P_2(a, b) = a R b \implies b R a[/tex]
let [tex]P_3(a, b, c) = a R b \land b R c \implies a R c[/tex]
Definition 1 can now be written as:
Definition 1a: A binary relation R on set A is an equivalence relation if:
[tex][\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)][/tex]
It seems that this is analogous to the situation above, so that the universal quantifiers can be collapsed:
[tex]\forall a, b, c \in A \ P_1(a) \land P_2(a, b) \land P_3(a, b, c)[/tex]
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?