0
$\begingroup$

A more clear way of asking it I suppose would be. Supposing a finite set 'S' that is not empty, how would I be go about proving that the number of subsets of S if the total number of elements is odd, be the same as the number of subsets of S if the total number of elements is even?

I know that the total number of subsets in a finite set is 2^n, given that n is the number of elements. So how can an even sized set and an odd sized one have the same number of subsets?

$\endgroup$
  • $\begingroup$ Do you have any reason to believe it should be possible? Does it say so in a book or something? $\endgroup$ – Arthur Jan 26 '16 at 0:22
  • 1
    $\begingroup$ You have just proved that no two finite sets with different cardinality have the same number of subsets - by stating that a set of cardinality $ n $ has $ 2^n $ subsets (and $2^n \neq 2^m $ for $ n \neq m $) $\endgroup$ – Jytug Jan 26 '16 at 0:23
  • $\begingroup$ Arthur, the question is saying to show that they are the same. Perhaps I can just simply prove that it is impossible. I guess I'm just misinterpreting the question. $\endgroup$ – Peter Jan 26 '16 at 0:25
  • $\begingroup$ Jytug, that's what I thought, how can they be equal? Perhaps the question was worded poorly. Thank you. $\endgroup$ – Peter Jan 26 '16 at 0:26
  • $\begingroup$ The question is just plain wrong. Reread it. $\endgroup$ – fleablood Jan 26 '16 at 0:27
0
$\begingroup$

If a finite set has $n$ elements then there are $2^n$ possible subsets.

As $2^{odd} \ne 2^{even}$ this is impossible.

===

To determine that the number of subsets is $2^n$ consider that to create a subset you can go through each of the $n$ elements and make a choice either to include it in the subset or to omit it. Thus there are $2^n$ choices and $2^n$ subsets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.