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

I Sets, Subsets, Possible Relations

  1. Feb 23, 2017 #1
    Given a set, there are subsets and possible relations between those arbitrary subsets. For a given example set, the possible relation between the subsets of the example set will narrow down to the "true" possible relations between those subsets.

    a) {1}
    Number of Subsets: ##2^1 = 2## (∅, {1}) where the power means how many elements

    Number of Possible Relations (suppose those two subsets A and B are arbitrary): ##2^2 = 4## (A⊆A, A⊆B, B⊆B, B⊆A) where the base is 2 since there are two subsets and the power is 2 since there are two possible ways to relate each pair.

    Number of "True" Possible Relations: 3 (∅⊆∅, ∅⊆{1}, {1}⊆{1})

    b) {1,2}
    Number of Subsets: ##2^2 = 4##

    Number of Possible Relations (suppose those two subsets A and B are arbitrary): ##4^2 = 16##

    Number of "True" Possible Relations: 9

    c) {1,2,3}
    Number of Subsets: ##2^3 = 8##

    Number of Possible Relations (suppose those two subsets A and B are arbitrary): ##8^2 = 64##

    Number of "True" Possible Relations: 27

    d) {1,2,3, ..., n}
    Number of Subsets: ##2^n##

    Number of Possible Relations (suppose those two subsets A and B are arbitrary): ##(2^n)^2 = 2^{2n}##

    Number of "True" Possible Relations: ##3^n##

    Part d) is guesswork. So is part d) correct by the pattern that is given in part a)-c)? I know that I need to do induction in order to formally say that IT is correct but the question is if I can guess by the pattern.
     
  2. jcsd
  3. Feb 23, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    For a set with n elements, you have
    - 1 subset with 0 elements, leading to 2n true possible relations
    - n subsets with 1 element, leading to n*2n-1 true possible relations
    - ...
    - 1 subset with n elements, leading to 1 possible relation.

    This is the binomial expansion of (2+1)n. No need to use induction.
     
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: Sets, Subsets, Possible Relations
  1. Subsets and Power Set (Replies: 3)

  2. Empty set as a subset? (Replies: 12)

  3. Set Theory: subsets (Replies: 2)

Loading...