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

(a C b) and (b C a) implies a=b?

  1. May 29, 2015 #1
    Greetings. I have been studying David Poole's Linear Algebra textbook and I discovered in the Appendix that if it can be shown that if the set A is a sub-set of B and B is a sub-set of A, then the set A is exactly the same as the set B. And this all seems intuitively plausible, but for the life of me I couldn't prove it. No proof was adduced in the textbook, but I assume such a proof exists.

    Is it simply an axiom or is it derived from something else?

    I tried to take it along these lines: Some of the elements of B form the entirety of the elements of A. And the some of the elements of B form the entirety of the elements of B.

    I even tried to pictorialize it with an ad hoc variation of the Venn diagram, where the bubble representing B curled around and entered A in a sort of two-dimensional Klein bottle. No help here either.

    Any suggestions?
     
  2. jcsd
  3. May 29, 2015 #2

    Orodruin

    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    Try to assume the opposite and show that it leads to a contradiction.
     
  4. May 29, 2015 #3
    Hmmmm. I'll try.

    Okay, let Na represent the number of elements of the set A. Let Nb represent the number of elements of set B.

    Then, if every element of set A is an element of set B it follows that Na is less than or equal to Nb. Also, if every element of set B is an element of set A, it follows that Nb is less than or equal to Na.

    But if Na < Nb then Nb cannot < Na, therefore the number of elements of B equals the number of elements of A.

    Does that work? Or is something missing?
     
  5. May 29, 2015 #4

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I'm not sure what you are trying to picture. A = B clearly meets the criteria. Remember that "subset of" means "proper subset of or equal to".

    There can be no other option. B cannot be a proper subset of A, because then A cannot be a subset of B, so B must be equal to A.

    You can in fact take this as the definition of equality for sets:

    ##A = B## iff ##A \subset B## and ##B \subset A##

    It's a similar argument to: ##a \le b## and ##b \le a## implies ##a = b##
     
  6. May 29, 2015 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

  7. May 29, 2015 #6

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    No. Two different sets can have the same number of elements. So proving that the sets have the same cardinality will not prove that the sets are equal. For a formal proof, you need to rely on the formal definition of equality of 2 sets. I am sure you can prove it directly or by contradiction. Assume A and B are different. Does that mean there is an element in one that is not in the other? Then where does that lead you?
     
  8. May 30, 2015 #7
    That last one did it for me. Thank you, FactChecker.
     
  9. Jul 1, 2015 #8
    Yup, thats right. But this is wrong ##a < b, b < a \Rightarrow a = b##
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: (a C b) and (b C a) implies a=b?
  1. A->b, C->~b, A /\ C->? (Replies: 3)

Loading...