Diaconescu’s Theorem says that the Axiom of Choice (AOC) implies the Law of Excluded Middle (LEM), but what of the converse? Does the Law of Excluded Middle imply the Axiom of Choice? The answer is no.

Background Link to heading

I recently ran into a situation where I wanted to prove something was equivalent to the axiom of choice (Specifically the Law of Trichotomy). Remembering Diaconescu’s Theorem, I mistakenly thought for a moment that perhaps the converse holds, hence my proof would be as simple as proving that Law of Trichotomy implies the Law of Excluded Middle. Unfortunately for me however, upon remembering some basic independence results, it became obvious that this is not the case.

Why? Link to heading

Recall that the Axiom of Choice has been proven to be logically independent of Zermelo–Fraenkel set theory(ZF) by Godel and Cohen. This means there does not exist a proof of the AOC in ZF. Recall then, that ZF is typically taken to be a theory of (Classical) First Order Logic (FOL), which includes the LEM. Hence all theorems in FOL are theorems in ZF. Hence if we can not prove the AOC in ZF, who’s theorems are a superset of those in FOL (including the LEM), then it is impossible to use the law of excluded middle to imply the axiom of choice.