Results 1 to 4 of 4

Math Help - Total relations between sets proof

  1. #1
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    1

    Total relations between sets proof

    Question: Suppose a set A has n elements and a set B has m elements. Prove that there are 2^m*n different relations from A to B

    Now i see how this works with the product rule with AXB with m*n elements. and there are two sets so thats where 2 is involved. So i guess all the pieces are there but i don't know what to do with them.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,639
    Thanks
    1592
    Awards
    1

    Re: Total relations between sets proof

    Quote Originally Posted by Aquameatwad View Post
    Question: Suppose a set A has n elements and a set B has m elements. Prove that there are 2^m*n different relations from A to B
    I use \|A\| as the notation for the number of elements is a set A.

    Then \|A\times B\|=\|A\|\cdot\|B\|

    Any subset of A\times B is a relation A\to B.

    So the answer to this question is 2^{\|A\|\cdot\|B\|}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Sep 2010
    Posts
    151
    Thanks
    1

    Re: Total relations between sets proof

    How do you get to the point where you come to the conclusion where you use '2' to get '2^||A||*||B||' ? I'm confused on that jump.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,639
    Thanks
    1592
    Awards
    1

    Re: Total relations between sets proof

    Quote Originally Posted by Aquameatwad View Post
    How do you get to the point where you come to the conclusion where you use '2' to get '2^||A||*||B||' ? I'm confused on that jump.
    If S is a set, the number of subsets of S is 2^{\|S\|}.

    Here is a brief outline of a proof.
    If we form the set of bit-strings, strings of 0's & 1's, of length n, then that set has 2^n elements.
    If S=\{a,b,c,d\} then the string 0,1,1,0 represents the subset \{b,c\}. So every 4-bit-string represents a subset of S so there are 2^4 subsets of S.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Total no. of reflexive relations on a set of n elements
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 29th 2011, 01:24 AM
  2. Relations of sets (again)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2010, 10:04 PM
  3. Relations of sets
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 8th 2010, 02:49 PM
  4. Sets and relations
    Posted in the Calculus Forum
    Replies: 1
    Last Post: November 4th 2008, 07:38 AM
  5. sets and relations
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 28th 2008, 10:43 PM

Search Tags


/mathhelpforum @mathhelpforum