1. Not finding help here? Sign up for a free 30min 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!

Equivalence relation - Proof question

  1. Jun 12, 2013 #1
    1. The problem statement, all variables and given/known data

    Prove that the relation, two finite sets are equivalent if there is a one-to-one correspondence between them, is an equivalence relation on the collection [itex]S[/itex] of all finite sets.

    I'm sure I know the gist of how to do it, but I'm a beginner in proofs, and I'm not sure if I've written it down correctly. I absolutely encourage nitpicking in the following proof, as I wish to learn how proofs are correctly written. Thanks! :smile:


    2. Relevant equations

    N/A

    3. The attempt at a solution

    Let [itex]S[/itex] be the class of all finite sets.
    Let [itex] A, B [/itex] and [itex] C[/itex] be three finite sets.

    Reflexive property

    Now, [itex]n(A) = n(A)[/itex], and hence there exists a one-to-one correspondence between [itex]A[/itex] and [itex]A[/itex]

    Therefore, [itex]A \approx A[/itex] ------------------(1)

    Symmetric property

    Let [itex]A \approx B[/itex]
    [itex]\Rightarrow n(A) = n(B)[/itex]
    [itex]\Rightarrow n(B) = n(A)[/itex], and hence there exists a one-to-one correspondence between [itex]B[/itex] and [itex]A[/itex]

    [itex]\Rightarrow B \approx A[/itex]

    Therefore, [itex]A \approx B \Rightarrow B \approx A[/itex]----------------(2)

    Transitive property

    Let [itex]A \approx B [/itex]
    [itex]\Rightarrow n(A) = n(B)[/itex]---------------------(3)

    Also, let [itex]B \approx C [/itex]
    [itex]\Rightarrow n(B) = n(C)[/itex]---------------------(4)

    From (3) and (4), [itex]n(A) = n(C)[/itex]
    [itex]\Rightarrow A \approx C [/itex]

    Therefore, [itex] A \approx B[/itex] and [itex]B \approx C \Rightarrow A \approx C[/itex]--------(5)

    From (1), (2) and (5), it is clear that the relation, two finite sets are equivalent if there is a one-to-one correspondence between them, is an equivalence relation.

    Q.E.D
     
  2. jcsd
  3. Jun 12, 2013 #2

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    It is certainly true that if two finite sets have the same number of elements then there is a 1-1 correspondence between them. But I doubt you are to use that. Instead of talking about n(A) and n(B) you should be talking about 1-1 correspondence between them. For example, to see if ##A\approx A## you need to demonstrate a 1-1 function ##f## from ##A## onto ##A##. And so forth.
     
  4. Jun 13, 2013 #3
    Why is it that I can't use it? I thought it would be generalized if I prove it this way, using the number of elements.

    But then, doesn't the demonstration of such a function depend on [itex]A[/itex], or to be precise, the domain of [itex]A[/itex]? How can this work for any general [itex]A[/itex]?
     
  5. Jun 13, 2013 #4

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't know what you are allowed to use; ask your teacher. I'm just saying I would expect a simple direct proof using the definition you are given.
    What do you mean by the "domain of ##A##"? ##A## is a set, not a function. If ##A## is any finite set, can't you think of a 1-1 correspondence from ##A## to ##A##? It is really trivial...
     
  6. Jun 13, 2013 #5
    Sorry if I sounded assertive. I don't have a teacher. I'm self-learning from a text named A Concrete Introduction to Higher Algebra, by Lindsay N. Childs.

    Ah, sorry about that. Guess it doesn't make much sense when I read it now. An identity mapping should do the trick, shouldn't it?
     
  7. Jun 13, 2013 #6

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes. So ##A\approx A##. Now how about the symmetric and transitive properties, using the notion of 1-1 correspondence?
     
  8. Jun 13, 2013 #7
    Since [itex] A \approx B[/itex], there exists a one-to-correspondence from [itex]A[/itex] to [itex]B[/itex], and thus, it must have an inverse, which is another one-to-one correspondence from [itex]B[/itex] to [itex]A[/itex]. So, the symmetric property is satisfied.

    I'm not sure about proving the transitive property. If a [itex]f[/itex] is a one-to-one correspondence from [itex]A[/itex] to [itex]B[/itex], and if [itex]g[/itex] is another one-to-one correspondence from [itex]B[/itex] to [itex]C[/itex], is [itex]g \circ f[/itex] a one-to-one correspondence from [itex]A[/itex] to [itex]C[/itex]? If so, how is this proved? If it's true, then the transitive property is also taken care of.
     
  9. Jun 13, 2013 #8

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    OK, that works.
    Yes, that is the only non-trivial part of the problem. The way it is proved is to show ##g\circ f## is 1-1 and onto from ##A## to ##C##. Write down what you have to show and use the properties of ##f## and ##g## to prove it.
     
  10. Jun 13, 2013 #9

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I should also have probably commented a little more on this. It is certainly true that a 1-1 correspondence ##f## must have an inverse which is also a 1-1 correspondence. But, unless you are appealing to a previous theorem, you should prove that. I know it is "obvious", but you can actually show the inverse exists, is defined on all of ##B##, is onto ##A##, and is 1-1. You have simply declared those facts to be true, not proved them.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Equivalence relation - Proof question
  1. Equivalence Relations! (Replies: 2)

  2. Equivalence Relations (Replies: 5)

  3. Equivalence relation ? (Replies: 1)

  4. Equivalence Relations (Replies: 9)

Loading...