# Number of even and odd sized subsets of a given set $X$ are equal.

Let $$\mathcal{E}$$ be the set containing even subsets of $$X$$ and $$\mathcal{O}$$ be the one containing odd ones.
Let $$S \in \mathcal{E}$$ or $$S \in \mathcal{O}$$
Let there exists $$a \in X$$ and define a function :

$$f_a : \mathcal{E} \rightarrow \mathcal{O}$$ To be : $$f(Y) = Y \triangle \{a\}$$ Then : $$\forall S : (f_a(f_a(S))) = S$$ $$\implies f^{-1}_a = f_a$$ Hence $$f_a$$ is a bijection $$\implies \mathcal{|E|} = \mathcal{|O|} \:\square$$ $$---------------------$$
Is the proof correct?
$$---------------------$$

P.S There are different answers to this question(mostly combinatorial) few of them I am listing below :

Combinatorial proof that the number of even cardinality subsets is equal to the number of odd cardinality subsets

Prove that every $n$-element set has the same number of subsets with even and odd cardinality without creating a bijection

How to prove the cardinality of set of even and odd integers are equal?

There is something missing.

In general, a bijection between $$2$$ sets $$A$$ and $$B$$ is a function $$f:A \to B$$ with $$2$$ properties:

$$f(x)=f(y)\Rightarrow x=y$$

and

$$f(A)=B.$$

You showed the first condition, but not the second!

The second condition is to show that that every element of B is an image of some element of A under that function.

You concluded that $$f_a^{-1}=f_a$$, which formally doesn't make sense, as they are defined on different sets ($$f_a$$ is defined on $$\mathcal E$$, while $$f_a^{-1}$$ is defined on $$\mathcal O$$.

In your case, what you missed to show is the fact that $$f_a(\mathcal{E})=\mathcal O$$. That's important because your line of reasoning, without considerig which values are actually obtained by the function, also works to show that $$\mathbb Z$$ and $$\mathbb R$$ have the same cardinality. After all $$f: \mathbb Z \to \mathbb R$$, via $$f(x)=x$$ has the same property.

The inverse of that $$f$$ is simply a function $$f^{-1}: \mathbb Z \to \mathbb Z$$, it is not a function from $$\mathbb R \to \mathbb Z$$!

Adding this detail isn't hard here, you need to show that for every $$C \in \mathcal O$$ there is a $$B \in \mathcal E$$ such that $$f_a(B)=C$$. $$B=C\triangle \{a\}$$ works, you just need to show it is in $$\mathcal E$$.

Also, can you find where your proof breaks down for $$X=\emptyset$$? Because for that $$X$$, the proposition isn't true!

• So as I have showed for $f_a : \mathcal{E} \rightarrow \mathcal{O}$, in the same manner I have to show for $f_a : \mathcal{O} \rightarrow \mathcal{E}$? And I did not get the point about the cardinality of reals and the integers being same? Nov 8, 2022 at 18:19
• I added a bit to the answer to clarify what is missing. It can be done in several ways. Your proposal would be one way. Nov 9, 2022 at 8:41