3 ms·
My favorite application of the Axiom of Choice, which Computer Scientists will appreciate: Theorem ("Konig's Lemma"): If a tree has infinitely many nodes, and
by xamuel 9y ago
My favorite application of the Axiom of Choice, which Computer Scientists will appreciate:
Theorem ("Konig's Lemma"): If a tree has infinitely many nodes, and every node has only finitely many children, then the tree must have an infinite branch.
Proof: The tree's root, X1, has infinitely many descendants. Since the root has only finitely many children, some child, X2, of the root, must have infinitely many descendants. Since X2 has only finitely many children, some child, X3, of X2, must have infinitely many descendants. This process repeats forever, producing a sequence X1, X2, X3, ... which is an infinite branch through the tree.
- mrmyers 9y agoYou don't need the axiom of choice for the countable case, which is all that's required for computer science.
- cuspycode 9y agoWhy is the AC necessary for this recursive tree traversal?
- xamuel 9y agoThe AC is necessary[1] because at each of the infinitely many steps, you have to choose which of possibly several candidates to use. [1] As mrmyers points out, you actually only need a weaker version of AC, called Countable Choice.