FOM: Podnieks on AC, Platonism, and Intuition
jshipman@bloomberg.net
jshipman at bloomberg.net
Tue Dec 23 13:11:24 EST 1997
I'm not sure what kind of analogy is intended when Podnieks talks about a
"finite version" of AC. The P=NP question can be viewed as a "choice" problem
if you regard it as a question about the essential nature of exhaustive ("brute
force") search -- a P-time algorithm for finding a satisfying assignment if one
exists is analogous to a definable choice function, while exhaustive search is
analogous to the situation where no definable choice function exists (this is
why some mathematicians rejected AC, they could not imagine exhaustively
seaching an infinite set). See my 12/22 remarks to Davis.
(Aside: there is some interesting work by Conway and Gauntt on implications
between the "finite choice axioms" AC(n) [AC(2) says any collection of 2-element
sets has a choice function, etc.] having various degrees of effectiveness,
which are nice applications of number theory and finite group theory to logic.)
I have read Podnieks's referenced paper and recommend it to FOMers as having
some very interesting ideas relevant to a number of topics discussed on FOM.
--Joe Shipman (Ph.D. Brandeis '92; programmer for Bloomberg Financial Markets)
More information about the FOM
mailing list