10
$\begingroup$

This interesting question asks the minimum number of quantifiers required to state the Axiom of Choice, and recalls that any sentence having three or fewer quantifiers is already decided by ZF. This apparently implies that it is known that there are 4-quantifier sentences that are not decided by ZF.

Is this correct? Are there natural examples of such sentences?

Improve this question
$\endgroup$
5
  • 8
    $\begingroup$ Back in 2003, Harvey Friedman wrote on the FOM list, "I conjecture that every 4 quantifier sentence is decided in a somewhat weak fragment of ZF (it has to include the power set axiom)." So apparently the question was open back then. Admittedly, that was a rather long time ago, and for example it (just barely) predates the work of Kurt Maes showing that AC can be expressed using 5 quantifiers. $\endgroup$
    – Timothy Chow
    Commented Dec 2 at 13:35
  • $\begingroup$ Total number of quantifiers, or quantifier alternations? $\endgroup$
    – Christopher King
    Commented Dec 2 at 16:41
  • $\begingroup$ In addition to Christopher's question, are we counting bounded quantifiers as quantifiers? $\endgroup$
    – James E Hanson
    Commented Dec 2 at 19:07
  • 2
    $\begingroup$ I believe it is total quantifiers, including bounded. (I believe things are referring back to Harvey Friedman's FOM post linked by Timothy Chow above. In the original question, the linked question "This interesting question" cites the paper by Kurt Maes, which cites the post "196:Quantifier complexity in set theory" by Harvey Friedman, but the link provided in the paper for Friedman's post seems to be in error, as it goes to something else.) $\endgroup$
    – Farmer S
    Commented Dec 3 at 0:19
  • 1
    $\begingroup$ @ChristopherKing Farmer is correct, I meant the total count of quantifiers (bounded or otherwise). $\endgroup$
    – Pedro Sánchez Terraf
    Commented Dec 3 at 11:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .