31
$\begingroup$

Let $A$ be a non-empty set and $n$ be the number of elements in $A$, i.e. $n:=|A|$.

I know that the number of elements of the power set of $A$ is $2^n$, i.e. $|\mathcal{P}(A)|=2^n$.

I came across the fact that exactly half of the elements of $\mathcal{P}(A)$ contain an odd number of elements, and half of them an even number of elements.

Can someone prove this? Or hint at a proof?

$\endgroup$
3
  • 13
    $\begingroup$ A nice proof goes by using the binomial theorem: $(x+y)^n=\sum_k \binom{n}k x^k y^{n-k}$. Here, $\binom{n}{k}$ is the number of $k$-sized subsets of a set of size $n$. Your result corresponds to the fact that $0=(1-1)^n$. Expanding, the binomial theorem gives us that the sum of the $\binom{n}{k}$ with $k$ odd equals the sum of the $\binom{n}{k}$ with $k$ even. The first is precisely the number of odd-sized subsets, and the second is the number of even-sized subsets. $\endgroup$ Commented Nov 30, 2012 at 20:14
  • 1
    $\begingroup$ I'm amazed at the fact that you guys answer so quickly! Thanks and wow! $\endgroup$
    – gbag
    Commented Nov 30, 2012 at 20:18
  • $\begingroup$ I'm amazed that so many people bothered to write answers, and that there are some good answers, but there is only one upvote to the question. $\endgroup$
    – Asaf Karagila
    Commented Nov 30, 2012 at 20:29

8 Answers 8

40
$\begingroup$

Fix an element $a\in A$ (this is the point where $A\ne\emptyset$ is needed). Then $$S\mapsto S\operatorname{\Delta}\{a\}$$ (symmetric difference) is a bijection from the set of odd subsets to the set of even subsets.

$\endgroup$
4
  • 3
    $\begingroup$ Very nice! ${}{}{}$ $\endgroup$
    – Asaf Karagila
    Commented Nov 30, 2012 at 20:29
  • 2
    $\begingroup$ Indeed, really cute! $\endgroup$ Commented Nov 30, 2012 at 20:51
  • $\begingroup$ Addition: suppose $f(S_1)=f(S_2)$ then we know that either $a$ was in both sets, or $a$ was in neither. After removing or adding, the sets are equal, hence they were the same to start with $S_1 = S_2$ and $f$ is injective. Suppose we have some even set $B$ which does not contain $a$. We now consider $f(B \cup \{ a\})=B$, which must be a possible subset (which is odd). Similarly whenever we have some even subset B which does contain $a$, we have that $f(B - \{a\})=B$. The desired function therefore outputs any even subset. This function is injective + surjective thus it is bijective. $\square$ $\endgroup$
    – user459879
    Commented Nov 23, 2018 at 12:38
  • $\begingroup$ For those who did not understood this , look here : math.stackexchange.com/a/483537/131949 $\endgroup$
    – Number945
    Commented Apr 21, 2019 at 23:40
14
$\begingroup$

Hint: One can prove this by induction on the size of $A$. Assume it was true for sets of size $n$ and let $A=\{a_1,\ldots,a_{n+1}\}$. Then every subset of $A$ is either a subset of $\{a_1,\ldots,a_n\}$ or it is a copy of such subset with the addition of $\{a_{n+1}\}$. Use the induction hypothesis to conclude that the sets which do not contain $a_{n+1}$ have this property (with respect to $\{a_1,\ldots,a_n\}$, by adding $a_{n+1}$ you send exactly the same number of odd sets to even size sets, and vice versa; therefore the ratio remains true for $A$.

$\endgroup$
6
$\begingroup$

For $n\in\Bbb Z^+$ let $[n]=\{1,2,\dots,n\}$. Clearly $[1]$ has one even subset and one odd subset. Suppose that $[n]$ has equal numbers of odd and even subsets for some $n\in\Bbb Z^+$. The even subsets of $[n+1]$ are of two types:

  • the even subsets of $[n]$; and
  • the sets of the form $A\cup\{n+1\}$, where $A$ is an odd subset of $[n]$.

By the induction hypotheses there are the same number of sets of the second type as there are of the first, so $[n+1]$ has twice as many even subsets as $[n]$. But $[n+1]$ also has twice as many subsets altogether as $[n]$, so it must have twice as many odd subsets as well, which clearly implies that it has equal numbers of odd and even subsets.

$\endgroup$
1
  • 3
    $\begingroup$ +1 but you do not even need the induction hypothesis, as you have shown that the number of even subsets of $[n+1]$ is equal to the number of subsets of $[n]$ and a very similar argument would show the number of odd subsets of $[n+1]$ is the same. $\endgroup$
    – Henry
    Commented Dec 1, 2012 at 2:53
2
$\begingroup$

When $n$ is odd, look at each set and its complement: one will have even number of elements and the other, odd (because odd number can only be written as a sum of an odd and an even number).

When $n$ is even, remove an element to obtain a set with odd number of elements. By the first part, half of its subsets have even cardinality and half odd. Now to form the full $\mathcal P(A)$, we need to join the remainin element to each of the previous subsets: those with odd cardinality with become even, and viceversa.

$\endgroup$
1
  • $\begingroup$ So easy and natural when $n$ is odd. So futile trying to define a 'semi-complement' function. sigh... $\endgroup$ Commented Dec 10, 2017 at 23:47
2
$\begingroup$

Number the members of the set $1,2,3,4,\ldots,n$.

For every subset with an even number of elements, there is a corresponding set with an odd number of elements, that corresponds in this way:

  • If $1$ is a member of the set with an even number of elements, then delete $1$ from the set to get a set with an odd number of elements.
  • If $1$ is not a member of the set with an even number of elements, then add $1$ to the set to get a set with an odd number of elements.

For example, suppose the set is $\{1,2,3,4\}$. Then we have this correspondence between sets with an even number of elements and sets with an odd number of elements: $$ \begin{array}{rcl} \text{even} & & \text{odd} \\ \hline \varnothing & \leftrightarrow & \{1\} \\ \{1,2\} & \leftrightarrow & \{2\} \\ \{1,3\} & \leftrightarrow & \{3\} \\ \{1,4\} & \leftrightarrow & \{4\} \\ \{2,3\} & \leftrightarrow & \{1,2,3\} \\ \{2,4\} & \leftrightarrow & \{1,2,4\} \\ \{3,4\} & \leftrightarrow & \{1,3,4\} \\ \{1,2,3,4\} & \leftrightarrow & \{2,3,4\} \end{array} $$

This won't work with the empty set because we don't have an element to which we can assign the number $1$.

$\endgroup$
1
$\begingroup$

Suppose $n=|A|$. Then there are $$\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}\binom{n}{2k}=2^{n-1}$$ sets with even cardinality. Thus, there are exactly half of the sets with an even number of elements.

$\endgroup$
2
  • $\begingroup$ For me, it's not obvious why this identity holds. Could you maybe elaborate? $\endgroup$
    – gbag
    Commented Nov 30, 2012 at 20:23
  • 1
    $\begingroup$ It's easiest to prove by induction. If n=1, then there is exactly 1 set with an even number of elements: the set with no elements (the empty set). Suppose it's true for some positive integer k. Then k+1 is either odd or even. If it's odd, then the floor of (k+1)/2=k/2, in which case we're done. If it is even, then break up the sum and binomial coefficient, combine, and you get the desired result. $\endgroup$
    – Clayton
    Commented Nov 30, 2012 at 20:44
1
$\begingroup$

You can use proprieties of the binomial coefficients.

Denote $\mathcal{P}_k(A)$ the family of subsets of $A$ containing $k$ elements and observe $|\mathcal{P}_k(A)| = {n \choose k}$ .

Now by a propriety of binomial coefficients $\sum_{k=0}^{n/2} {n \choose 2k} =\sum_{k=0}^{n/2} ({n-1 \choose 2k-1} + {n-1 \choose 2k}) = \sum_{k=0}^{n-1} {n-1 \choose k}$ and similarly $\sum_{k=0}^{n/2-1} {n \choose 2k+1} =\sum_{k=0}^{n/2-1} ({n-1 \choose 2k} + {n-1 \choose 2k+1}) = \sum_{k=0}^{n-1} {n-1 \choose k}$ .

This shows that $\sum_{k=0}^{n/2}|\mathcal{P}_{2k}(A)| = \sum_{k=0}^{n/2-1}|\mathcal{P}_{2k+1}(A)|$ .

$\endgroup$
1
$\begingroup$

Denote $X$ the number of sets with even cardinality, $Y$ the number of sets with odd cardinality, $n$ the cardinality of the power set. $$ X=\sum_{i=0,2,4,...}{n\choose i}, Y=\sum_{i=1,3,5,7,...} {n\choose i}\\\Rightarrow X-Y=\sum_{i=1}^{n}{n\choose i}(-1)^i(+1)^{n-i}=(-1+1)^n=0\\ \Rightarrow X=Y$$

Because $X+Y=n$, it is obvious that $X=n/2$, that is the half of the power set.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .