Consider a set $ \ A \ $ with $ \ n>0 \ $elements , $ \ \mathcal{O}=\{B \subset A: \ |B| \ \ is \ \ odd \} \ $

Question

Consider a set $ \ A \ $ with $ \ n>0 \ $elements , $ \ \mathcal{O}=\{B \subset A: \ |B| \ \ is \ \ odd \} \ $ , $ \ \large \large \epsilon=\{B \subset A: \ |B| \ \ is \ \ even \} \ $.

Then which is true?

(i) $ \ |\mathcal{O}|< |\large \epsilon | \ $

(ii) $ \ |\mathcal{O} |=|\large \epsilon| \ $

(iii) $ \ | \mathcal{O} |>|\large \epsilon | \ $

Answer:

Let $ \ |A|=n \ $

Let $ P(A) \ $ denote the power set of $ \ A \ $, then

$ | P(A) |=2^n-1 \ $

Thus , we have

$ |\mathcal{O}|=\frac{2^n-2}{2} = $ collection of subsets of $ \ A \ $ with odd number of elements

$ |\mathcal{\large \epsilon}|=\frac{2^n-2}{2} = $ collection of subsets of $ \ A \ $ with even number of elements

Thus ,we see that

$ |\mathcal{O}|=\frac{2^n-2}{2} =|\large \epsilon | \ $

Am I right ?

Answer 1

It is true that both sets have the same number of elements, but your argument is wrong, since $\bigl|\mathcal{P}(A)\bigr|=2^n$.

You can prove that $|\mathcal{O}|=|\varepsilon|$ by induction on $n$. If it is true for a cetain set $A$ and then you add a new element $k$ to $A$, let $\mathcal{O}'$ be the set of subsets of $A\cup\{k\}$ with an odd number of elements and let $\varepsilon'$ be the set of subsets of $A\cup\{k\}$ with an even number of elements. Then the elements of $\mathcal{O}'$ are the elements of $\mathcal{O}$ together with the elements of $\varepsilon$ after adding the element $k$ to each one of them. Therefore, $|\mathcal{O}'|=|\mathcal{O}|+|\varepsilon|$. By the same argument, $|\varepsilon'|=|\mathcal{O}|+|\varepsilon|$ too.

Answer 2

That is not correct for several reasons.

1. $|P(A)|=2^n\neq 2^n-1$

2. $\dfrac{2^n-2}{2}+\dfrac{2^n-2}{2}=2^n-2$ so even if you were correct about the cardinality of the power set, you are saying that 1 set has a cardinality that is neither even nor odd?

How many subsets does the set have that have even cardinality? That would be:

$$\sum_{k=0}^{\lfloor \tfrac{n}{2} \rfloor} \dbinom{n}{2k}$$

How many have odd cardinality?

$$\sum_{k=0}^{\lfloor \tfrac{n-1}{2} \rfloor} \dbinom{n}{2k+1}$$

You are trying to show those are equal. Not hard, but not trivial either.

Answer 3

As others have noted, $|P(A)|$ = $2^n$, not $2^{n-1}$. Now, if the size of $A$ is odd, we have the following bijection

$$ \Lambda:\mathcal{O} \longrightarrow \mathcal{E} \\ B \longmapsto B^c $$

with it's inverse being

$$ \Gamma:\mathcal{E} \longrightarrow \mathcal{O} \\ B \longmapsto B^c $$ You can check that in effect, if $B$ has an odd amount of elements, $B^c$ will have an even amount, and viceversa. If that's not clear enough, recall that since we're assuming $|A|$ odd,

$$ |B| + |B^c| = |A| \equiv 1 \pmod{2} $$

so these two must have different parity. Since we've constructed a bijection from $\mathcal{O}$ to $\mathcal{E}$, they have the same size (again, for $|A|$ odd). So what if $|A|$ is even? Well, let's pick an arbitrary $a \in A$ and define

$$ \mathcal{O}_a = \{B \in \mathcal{O} : a \in B\} \\ \mathcal{O}_n = \{B \in \mathcal{O} : a \not \in B\} \\ \mathcal{E}_a = \{B \in \mathcal{E} : a \in B\} \\ \mathcal{E}_n = \{B \in \mathcal{E} : a \not \in B\} \\ $$

Since $\mathcal{O} = \mathcal{O}_a \sqcup \mathcal{O}_n$ and $\mathcal{E} = \mathcal{E}_a \sqcup \mathcal{E}_n$, it will suffice to see that $|\mathcal{O}_a| = |\mathcal{E}_a|$ and $|\mathcal{O}_n| = |\mathcal{E}_n|$. The latter is immediate since $\mathcal{O}_n$ and $\mathcal{E}_n$ are the sets of odd and even subsets of $A \setminus \{a\}$ which has now odd size. As for $|\mathcal{O}_a| = |\mathcal{E}_a|$, this is because

$$ |\mathcal{O}_a| = |\mathcal{E}_n| = |\mathcal{O}_n| = |\mathcal{E}_a| $$

via the bijections

$$ \alpha : \mathcal{O}_a \longrightarrow \mathcal{E}_n \\ \quad \quad B \mapsto B\setminus \{a\} $$

and

$$ \beta : \mathcal{E}_a \longrightarrow \mathcal{O}_n \\ \quad \quad B \mapsto B\setminus \{a\} $$