1. Limited time only! Sign up for a free 30min personal 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!

Set theory question

  1. Nov 12, 2007 #1
    1. The problem statement, all variables and given/known data

    Prove that, for all n, for all m with 0 <= m <= n, the number of subsets of {1, . . . , n} of size m is the same as the number of subsets of {1, . . . , n} of size n − m.

    2. Relevant equations

    3. The attempt at a solution
    My problem is that I don't know where to begin. I have a vague notion that I should somehow find the powerset of all the sets of size m and n - m and compare their sizes. But I don't really know where to start.
  2. jcsd
  3. Nov 12, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

  4. Nov 12, 2007 #3
    C(n,m)=C(n,n-m) since order of elements in a set is not important.
  5. Nov 12, 2007 #4
    I am not familiar with combinations... what are they?

    A google search doesn't net me any useful results.
    Last edited: Nov 12, 2007
  6. Nov 13, 2007 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I want to choose m things. Therefore, I don't choose how many things?
  7. Nov 13, 2007 #6


    User Avatar
    Science Advisor

    If A is a subset of S= {1, 2,... n} with m members, how many members does S\A have? Do you see an obvious one-to-one correspondence?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - theory question Date
Simple set theory question Sep 11, 2017
Set theory question Sep 7, 2017
Some true or false Field extension theory questions Dec 4, 2016
Galois Theory questions Dec 4, 2016
Set Theory Question Oct 11, 2016