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

B How many possible relations between two sets?

  1. Jun 9, 2016 #1
    Say you have set A with n elements and set B with m elements. If I recall, there are a total of 2nm relations between them. But my question is, does this count redundancies? What I mean is, if in the relation A~B = B~A. I don't want to count identical relations twice.


    Thanks!
     
  2. jcsd
  3. Jun 9, 2016 #2
    In principle A~B = B~A can never be correct because A~B means to for EVERY element in A there is a UNIQUE element in B to which is supposed to be related. And so is the fact with B~A means for EVERY element in B there is a UNIQUE element in A to which is supposed to be related. So they cannot be equal.
     
  4. Jun 9, 2016 #3
    Okay well what I mean is, say the relation is multiplication in a subset of R. Then 3*2 = 2*3. And so on.
     
  5. Jun 10, 2016 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Multiplication is not a relation, it is an operation.
     
  6. Jun 10, 2016 #5
    A relation between sets A and B is by definition a subset of AxB. If A has n elements and B has m elements, AxB has nm elements. Such a set has 2nm subsets, therefore there are 2nm relations between A and B.
     
  7. Jun 10, 2016 #6
    I thought all operations were types of relations. It appears i mixed some stuff up. Lets just rephrase the question as multuplication instead.
     
  8. Jun 10, 2016 #7

    Mark44

    Staff: Mentor

    So what is the new question?
     
  9. Jun 10, 2016 #8
    Im sorry I havent slept in 38 hours that last post was nonsense.

    But as a test, a specific example:

    Say I have a set with 6 elements and a set with 4 elements. Call them set A=[a1, a2, a3, a4, a5, a6] and set B=[b1,b2,b3,b4] Each of the 6 elements can be matched with one of the 4 elements, but each of the 4 elements can be matched to any number of the 6. So you can end up with all 6 of set A being associated with the first element of set B, or a1 and a2 being mathed woth b1, a3 being matched with b2, a4 and a5 being mathed with b3, and a6 being matched with b4. And so on. Any combination as long as all 6 from set A are matched with elements from set B and
     
  10. Jun 10, 2016 #9
    I am sorry the definition which I wrote was that of a function and not of relation. Every function is a relation but every relation is not a function.
     
  11. Jun 10, 2016 #10
    What is the difference between mapping and relation? You have to consider this question as well. I think mapping involves every element of say A whereas relation does not if its definition is any subset of AXB. Are the sets AXB and BXA identical I do not think so. That partly answers your self imposed equation A~B = B~A?
     
  12. Jun 11, 2016 #11

    Stephen Tashi

    User Avatar
    Science Advisor

    To investigate the correctness of that statement, we would need an clear definition for the statement "##R## is a relation between set ##A## and set ##B##".

    For example, if ##R =\{(1,4), (2,4)\}## then is ##R## a relation between the sets ##A =\{1,2,3\}## and ##B=\{4\}##?

    It looks to me like your result of ##2^{mn}## would count ##R## as being among the relations "between" ##A## and ##B##.

    However, doesn't ##2^{mn}## also count the null set of ordered pairs as a relation? Are we going to count a null set of ordered pairs as a relation ? Is it a relation "between" ##A## and ##B## ?
     
  13. Jun 11, 2016 #12
    That means there is no relation between the sets A and B is also a relation! Because that is the meaning of null set being the sub set of AXB and defining a relation between them. Or is teh total number [{2^(nm)} -1]
     
  14. Jun 11, 2016 #13

    Stephen Tashi

    User Avatar
    Science Advisor

    Yes, if ##A=B##.
     
  15. Jun 11, 2016 #14
    Stephen Tashi, thanks for responding. What is the correct or appropriate statement of the following:
    1. The set A is related to set B.
    2.The set B is related to set A.
    3. There is a relation between the sets A and B.

    The definition given by Cruz Martinez favors the third option. There is a relation between A and B means A is related to B and B is related to A.
     
  16. Jun 11, 2016 #15

    Stephen Tashi

    User Avatar
    Science Advisor

    I don't know of any standard mathematical definition for a relation "between" sets.

    So let's look at your post #8 and consider what you want the statement "##R## is a relation between ##A## and ##B##" to mean.

    I think you want each element of ##A## to in at least one of the ordered pairs of ##R##.
    With that requirement, we would not consider ##R = \{(a1,b1), (a2,b4)\}## to be a relation between ##A## and ##B## because some of the elements of ##A## are missing in the first members of the ordered pairs of ##R##.

    Now lets consider ##R = \{ (a1,b1),(a1,b2), (a3,b4), (a4,b4) ,(a5,b4), (a6,b4)\}##. Do you want ##R## to be a relation between ##A## and ##B## or do you want to disqualify it because it contains both ##(a1,b1)## and ##(a1,b2)## ?
     
  17. Jun 11, 2016 #16
    I think Stephen Tashi is confusing between the definitions of function and relation, which I also did!
     
  18. Jun 11, 2016 #17
    I've seen it in some books, e.g. Lee, Topological Manifolds, Appendix A. The other definition I've seen for a relation is that R is a relation if whenever z ∈ R, z is an ordered pair.
     
  19. Jun 11, 2016 #18

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, you're right. But you and Stephen are talking about something else. You are talking about a relation with codomain and domain a set. In this case, two elements of the sets can be related. Stephen seems to be talking about the case where two sets themselves are related. Of course you can define such a relation, but there is no standard one like the OP thinks.
     
  20. Jun 13, 2016 #19
    Folks, here is the standard set theoretic definition of a relation:

    $$R~\text{ is a relation}~\Leftrightarrow~\forall r(r \in R~\rightarrow~\exists x \exists y(r~=~<x,y>)~)$$

    This definition leave open the possibility that some members of relation ##R## are not ordered pairs.

    However, the cross product, ##A~\times~B##, of two sets, ##A## and ##B##, is certainly a relation since it satisfies the definition given above.

    The minimum number of possible relations between sets ##A## and ##B## would then be the number of sets in the power set of ##A~\times~B##, but the maximum number of relations is infinite.
     
  21. Jun 13, 2016 #20

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Then it is not the standard definition.
     
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: How many possible relations between two sets?
Loading...