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?


1 Answer 1


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$$



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!

  • $\begingroup$ 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? $\endgroup$ Nov 8, 2022 at 18:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ingix
    Nov 9, 2022 at 8:41

You must log in to answer this question.

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