Results 1 to 5 of 5

Math Help - Prove equivalence relation

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Prove equivalence relation

    Please critique the following proof and also let me know if I have defined the equivalence classes correctly.

    Let f:A\longrightarrow B. Define a relation \equiv on A by a_{1}\equiv a_{2} iff f(a_{1})=f(a_{2}). Give a quick proof that this is an equivalence relation. What are the equivalence classes? Explain intuitively.

    Proof: Test reflexive for \equiv. If a\in A then (a,a)\in A: Given f is a funcion then f(a_{1})=f(a_{1}) implies a_{1}\equiv a_{1} because two different values in the domain cannot be mapped to the same value in the range. Therefore (a_{1},a_{1})\in A.

    Test symmetric: Let a_{1}\equiv a_{2} where (a_{1},a_{2})\in A. Then we know f(a_{1})=f(a_{2}). But because = is symmetric we know f(a_{2})=f(a_{1}) and since \equiv is defined with iff, we know a_{2}\equiv a_{1} which implies (a_{2},a_{1})\in A.

    Test transitive: Let a_{1}\equiv a_{2} and a_{2}\equiv a_{3} where (a_{1},a_{2})(a_{2},a_{3})\in A. Then we know f(a_{1})=f(a_{2}) and f(a_{2})=f(a_{3}). Because = is transitive we know f(a_{1})=f(a_{3}), but because \equiv is defined with iff, we can conclude that a_{1}\equiv a_{3}. So (a_{1},a_{3})\in A.QED

    The equivalence classes in A would be the sets \{(a_{i},a_{j})\in A such that a_{i}=a_{j}).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    I agree with everything except your intuitive characterization of the equivalence classes.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by oldguynewstudent View Post
    Proof: Test reflexive for \equiv. If a\in A then (a,a)\in A
    I think you mean ' \equiv' , not 'A', as the last symbol there? I.e., this is what we want to prove.

    Quote Originally Posted by oldguynewstudent View Post
    Given f is a funcion then f(a_{1})=f(a_{1}) implies a_{1}\equiv a_{1} because two different values in the domain cannot be mapped to the same value in the range.
    No, that is backwards (as well as, though it is irrelevant to the actual proof, you can't assume f is an injection as you have).

    All you need to say is that if a=a then f(a)=f(a) so a \equiva.

    Your symmetry and transitivity arguments looked okay, as I glanced over them.

    Quote Originally Posted by oldguynewstudent View Post
    The equivalence classes in A would be the sets \{(a_{i},a_{j})\in A such that a_{i}=a_{j}).
    Wrong. The equivalence classes are not sets of ordered pairs of members of A. Rather, the equivalence classes are certain subsets of A.

    E is an equivalence class (per \equiv) iff there exists an a in A such that E = {x | x \equiva}.

    I.e., E is an equivalence class (per \equiv) iff there exists an a in A such that E = {x | f(x)=f(a)}.

    I.e., the equivalence classes (per \equiv) are the non-empty (assuming A is nonempty) sets each made up of, for some given a in A, all and only those members of A that map, under the function f, to f(a).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Yes, thank you very very much. I have trouble with proofs and have requested a meeting with my professor. The professor I had for Discrete knew his stuff but didn't know how to impart that knowledge very well. This professor for Combinatorics has been great so far. This is a great help. Thanks again!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    In my view, very likely you're not at fault, but rather standard curricula are at fault. In my view, it should be standard for math (and science, and social sciences, and even history and other humanities) students to take a course that teaches them how to work in the predicate calculus (both strictly symbolically and intuitively). Then, for math students, before even calculus, about the first half of a set theory course (through the basics, basic axiom of choice and Zorn's lemma, the naturals, and construction of the reals as a complete ordered field; but don't need the second half that gets into more about transfinite cardinalities, etc.).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: April 6th 2011, 11:46 PM
  2. Replies: 12
    Last Post: June 24th 2010, 12:00 PM
  3. equivalence relation and equivalence classes
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 7th 2010, 06:36 PM
  4. Equivalence relation and order of each equivalence class
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 30th 2009, 09:03 AM
  5. Equivalence relation and Equivalence classes?
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 7th 2009, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum