Diaconescu's theorem

1. Proposition

The Axiom of choice implies the Law of the excluded middle

2. Proof

Let \(\mathcal{B} = \{0,1\}\) and \(p\) a <proposition> Let further

\begin{align*} A =& \{x \in \mathcal{B} : x = 0 \lor p\} \subseteq \mathcal{B} \\ B =& \{x \in \mathcal{B} : x = 1 \lor p\} \subseteq \mathcal{B} \end{align*}

Then \(0 \in A, 1 \in B\), hence \(A,B\) are nonempty and \(X = \{A,B\}\) By the axiom of choice, there exists a choice function

\begin{align*} f: X \rightarrow \mathcal{B} \end{align*}

By definition of a function, there exist 4 Possibilities

2.1. \(f(A) = 0, f(B) = 0\)

By Assumption, \(0 \in B\), hence \(p\) is true

2.2. \(f(A) = 1, f(B) = 1\)

By Assumption, \(1 \in A\), hence \(p\) is true

2.3. \(f(A) = 0, f(B) = 1\)

Suppose \(p\) is true. Then \(A = B = \{0,1\}\), but this is a contradiction to \(f\) being a welldefined function. Hence \(p\) is false.

2.4. \(f(A) = 1, f(B) = 0\)

By Assumption, \(1 \in A\), hence \(p\) is true.

Therefore \(p\) is either true or false

Note that \(\{A,B\}\) is only kuratowski finite, but (in general) not finite