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

Empty relation

  1. May 29, 2010 #1
    Given any set A, a relation on A is a subset of AxA. Then isn't the empty set a relation also? Doesn't that make it an equivalence relation, vacuously, as well?
    I'm asking because in a book there's a problem stating: show there are exactly 5 equivalence relations on a set with 3 elements. I get the obvious
    {(1,1), (2,2), (3,3)}
    {(1,1), (2,2), (3,3), (1,2), (2,1)}
    {(1,1), (2,2), (3,3), (1,3), (3,1)}
    {(1,1), (2,2), (3,3), (2,3), (3,2)}
    {(1,1), (2,2), (3,3), (1,2), (2,1), (1,3), (3,1), (2,3), (3,2)} = AxA
    But I think the empty set should also be included, because for example in {(1,1), (2,2), (3,3)}, symmetry and transitivity are both trivially satisfied, just as they would be in the empty set.

    But I know equivalence relations correspond to partitions of the set. Then the partitions would be
    {1} {2} {3}
    {1,2} {3}
    {1,3} {2}
    {2,3} {1}
    And the empty set doesn't partition A, so what should it be?
    How is the empty set regarded with respect to (equivalence) relations?
    Last edited: May 29, 2010
  2. jcsd
  3. May 29, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    Hi Bleys! :smile:

    Doesn't an equivalence relation have to be reflexive?

    So (as a subset of AxA), it must at least contain every (a,a)

    (which the empty set doesn't)
  4. May 29, 2010 #3
    The empty set is indeed a relation on A (with indefinite arity), but not an equivalence one, except in the case where A is also empty.

    The catch here is that reflexivity is not (like transitivity or symmetry) expressed as an implication; its formal statement is just:

    [tex]\forall x\left(xRx\right)[/tex]

    Which fails unless A itself is empty.
  5. Jun 1, 2010 #4
    Kind of.

    It's at this point you realize why vacuous definitions are vacuous -- they don't really matter. They have no substance. No one really cares about them because they are totally definition-driven.

    I could easily write my own textbook saying a (binary) relation on a set A is a subset of A x A which has at least one member. My definition is virtually identical to every other math book. All of their proofs will work under my definition because no one writes proofs for vacuous theorems!

    The only difference is I could (if I wanted to) remove all restrictions when a proof requires a non-empty relation. In fact, the equivalent relation-partition theorem imposes this non-empty relation requirement. Go back and check your particular text. Either your text defines relations to be non-empty or the theorem only applies to non-empty relations (or your book has an error).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook