Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quantification logic and equivalence relations

  1. Feb 12, 2010 #1
    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. [tex]\forall a \in A \ a R a[/tex]
    2. [tex]\forall a, b \in A \ a R b \implies b R a[/tex]
    3. [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]:
    1. [tex]a R a[/tex]
    2. [tex]a R b \implies b R a[/tex]
    3. [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:

    1. [tex]\forall x \ P_1(x) \land \forall y \ P_2(y)[/tex]
    2. [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?
  2. jcsd
  3. Feb 13, 2010 #2


    User Avatar
    Gold Member

    Yes they are equivalent.
  4. Feb 13, 2010 #3
    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:
    \forall x \ P_1(x) \land P_2(x)
    You should use parenthesis:
    \forall x \left(P_1(x) \land P_2(x)\right)
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook