Suppose that a set has an odd number of elements. Explain why half of the subsets will have an odd number of elements .

Now assuming set A is the set with an odd number of integer elements{1,2,3,4,5}

Subset b ={1,2}

subset c={3}

Subset d={4,5}

Now there are two subsets with even number of elements and one subset with an odd number of elements.It seems to contradict the earlier theorem that i have to prove.I think that i am missing something.

  • 1
    $\begingroup$ There are $32=2^5$ possible subsets of $A$ since each of the elements is either included in the subset or not. Your subsets $b, c, d$ are three of these, but you need to include them all for the theorem to apply. $\endgroup$ – Mark Bennet Dec 30 '12 at 17:52
  • 1
    $\begingroup$ I find working through several examples helps me with this kind of thing. You've started with one example but as Mark says you have not found all of the subsets of your set. You might have to go back through your book or the Internet to refresh your set theory. Note that even the set $\{1\}$ has two subsets, and that there is one subset (with an even number of elements) that is a subset of every set. Also every set is a subset of itself. $\endgroup$ – Todd Wilcox Dec 30 '12 at 18:00
  • 1
    $\begingroup$ I think the downvoting here is rather hash. Is it just because the OP lacks understanding of hist own question? That's what asking is for! The question itself is perfectly good: It is plain and clear what the question is, and the OP shows enough work of his that we can see what the problem is. More questions should be like this! $\endgroup$ – Henning Makholm Dec 30 '12 at 18:49

Hint: try pairing each subset with its complement ...

  • 2
    $\begingroup$ Yes, that must be the source of the strange assumption that the original set has an odd number of elements. But actually the conclusion will hold for every non-empty set. $\endgroup$ – Henning Makholm Dec 30 '12 at 18:07
  • $\begingroup$ @HenningMakholm Indeed. Suppose the set is non-empty and has an even number of elements. Select an element $a$. The sets which don't contain $a$ form pairs - they are matched even and odd. And you get the sets which do contain $a$ by adding $a$ to one of the sets in each pair - two options, with opposite parity. Alternatively the binomial expansion of $(1-1)^n$ gives a proof for all $n$. $\endgroup$ – Mark Bennet Dec 30 '12 at 18:23
  • 3
    $\begingroup$ The classical connection is even simpler and doesn't care whether the original set is odd or even: Every subset that doesn't contain $a$ is paired to itself with $a$ added, and vice versa. Each of these pairs contains one odd and one even subset, though the one that contains $a$ may be the even one or the odd one. $\endgroup$ – Henning Makholm Dec 30 '12 at 18:46
  • $\begingroup$ @HenningMakholm Brain drift - it must be Christmas $\endgroup$ – Mark Bennet Dec 30 '12 at 18:48

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.