Does the canonical bijection between $\mathcal P(S)$ and $2^S$ use the axiom of choice or the law of excluded middle

169 Views Asked by At

Let $\mathcal{P}(S)= \{X \ | X \subseteq S\}$ and $2^S = \{g \ | \ g: S \rightarrow \{0,1\}\}$ and consider the bijection

$$f : \mathcal{P}(S) \rightarrow 2^S$$

Defined for all $X \in \mathcal{P}(S)$ and all $s \in S$ by $$ f(X)(s) = \left\{ \begin{array}{ll} 1 \ \ \Leftrightarrow \ \ s \in X\\ 0 \ \ \Leftrightarrow \ \ s \notin X\\ \end{array} \right. $$

In other words, every subset of $S$ is mapped by $f$ to its characteristic function, and every function $g$ on $S$ is mapped by $f^{-1}$ to the set $\{ s: g(s)=1 \} $.

Does this bijection use the axiom of choice or unbounded law of the excluded middle?

1

There are 1 best solutions below

2
On BEST ANSWER

This bijection definitely uses the law of excluded middle, but absolutely no axiom of choice.

As Asaf points out in the comments, why would it use the axiom of choice ? Have you "made a choice" at any point ?

As for the law of excluded middle, it is used in defining the characteristic function of a subset : if $X\subset S$, your function $f(X)$ is defined on $\{x\in S \mid x\in X\lor x\notin X\}$, and without the law of excluded middle, this may happen not to be $S$. What happens is that in some "intuitionistic universes", $2$ is replaced by a set $\Omega$ of "truth values", and so $f(X)(s)$ is "the truth value of "$x\in X$".

Of course, classically, there are only two truth values (true or false), hence the $2$, but without the law of excluded middle there can be more, and so you get a larger $\Omega$; and you have a bijection $\mathcal{P}(X)\simeq \Omega^X$.