Axiom of choice: Encyclopedia II - Axiom of choice - Results requiring choice in intuitionistic logic though not classically

Axiom of choice - Results requiring choice in intuitionistic logic though not classically

Interestingly, in various varieties of constructive logic (in particular, intuitionistic logic) in which the law of excluded middle is not assumed, the assumption of the axiom of choice is sufficient to obtain the law of excluded middle as a theorem. To see this, for any proposition let be the set and let be the set (see Set-builder notation). By the axiom of choice, there will exist a choice function for the set (note that, although the axiom of choice isn't classically required in order to obtain choice functions for finite sets, it is necessary here in intuitionistic logic). Since and , this implies , which implies . Since implies , it must be that implies , so would imply . As this could be done for any proposition , this completes the proof that the axiom of choice implies the law of the excluded middle.

The above proof is not valid in all intuitionistic deductive systems. For example, in the intuitionistic type theory of Per Martin-Löf, the axiom of choice is a theorem, yet excluded middle is not.

Adapted from the Wikipedia article "Results requiring choice in intuitionistic logic though not classically", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki