1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Equivalence relations

  1. Aug 22, 2010 #1
    1. The problem statement, all variables and given/known data
    Given is the set X. The set of functions from X to [0,1] we call Fun(X,[0,1]). On this set we consider the relation R. An ordered pair (f,g) belongs to R when [tex]f^{-1}(0)\setminus g^{-1}(0)[/tex] is a countable set.

    a) Prove that R is transitive.

    b) Is R an equivalence relation? Prove!

    c) Prove that [tex]R \cap R^{-1}[/tex] is an equivalence relation.

    2. Relevant equations
    Transitive means that if (f,g) and (g,h) belong to the relation, that also (f,h) belongs to it.

    Equivalence relation is a relation that is transitive, reflexive ([tex](f,f) \in R[/tex] and symmetric ([tex](f,g) \in R \Rightarrow (g,f) \in R[/tex].

    3. The attempt at a solution
    a) [tex]f^{-1}(0)\setminus g^{-1}(0)[/tex] is a countable set. So [tex]f{-1}(0)[/tex] is a countable set. This means that [tex]f^{-1}(0)\setminus h^{-1}(0)[/tex], because a subset of a countable set is also countable.

    Is this correct?

    b) Reflexivity is easy, because [tex]f^{-1}(0)\setminus f^{-1}(0)[/tex] is the empty set so that is obviously countable.
    How do I prove that it is symmetric?

    c) Is this just the subset of all the reflexive pairs?
    Last edited: Aug 22, 2010
  2. jcsd
  3. Aug 22, 2010 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    You can't conclude [itex]f^{-1}(0)[/itex] is countable. For instance, suppose X is R, the set of real numbers, and f(x)=g(x)=0. Then [itex]f^{-1}(0)\setminus g^{-1}(0)[/itex] is the empty set, but [itex]f^{-1}(0)=R[/itex], which is not countable.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook