Axiom of Choice Implies Law of Excluded Middle

From ProofWiki
Jump to: navigation, search


The axiom of choice implies the law of excluded middle.


Let $\mathbb B = \left\{ {0, 1}\right\}$.

Let $p$ be a proposition.

Let the following two sets be defined:

$A = \left\{ {x \in \mathbb B: x = 0 \lor p}\right\}$
$B = \left\{ {x \in \mathbb B: x = 1 \lor p}\right\}$

where $\lor$ denotes the disjunction operator.

We have that:

$0 \in A$


$1 \in B$

so both $A$ and $B$ are non-empty

Then the set:

$X = \left\{ {A, B}\right\}$

is a (finite) set of non-empty sets:

By the axiom of choice, there exists a choice function:

$f: X \to \mathbb B$

since $\displaystyle \bigcup X = \mathbb B$.

There are four cases:

$(1): \quad f \left({A}\right) = f \left({B}\right) = 0$

This means that $0 \in B$.

But for that to happen, $\left({0 = 1}\right) \vee p$ must be true.

So by Disjunctive Syllogism, $p$ is true.

$(2): \quad f \left({A}\right) = f \left({B}\right) = 1$

This means that $1 \in A$.

Arguing similarly to case $(1)$, it follows that $p$ is true in this case also.

$(3): \quad f \left({A}\right) = 1 \ne f \left({B}\right) = 0$

This means that $A \ne B$ (or otherwise f would pick the same element).

But if $p$ is true, that means:

$A = B = \mathbb B$

which is a contradiction.

Therefore in this case:

$\neg p$

$(4): \quad f \left({A}\right) = 0 \ne f \left({B}\right) = 1$

Using the same reasoning as in case $(3)$, it is seen that in this case:

$\neg p$

So by Proof by Cases:

$\left({p \vee \neg p}\right)$

That is the Law of Excluded Middle.