4
$\begingroup$

Let $AC$ denote any fixed statement of the Axiom of Choice in $ZF$.

Consider the set of statements $\phi$ in the language of $ZF$ such that either $ZF+\phi$ proves $AC$ or $ZF+AC$ proves $\phi$. The relation "is proved by under $ZF$" is a preorder on this set. Quotient this set by the relation "proves and is proved by under $ZF$". The resulting quotient is then partially ordered.

What can we say about this order? It's certainly not linear, not finite. Can we say anything nontrivial about it? About cardinalities of maximal chains, antichains? Are there any foundational issues with even talking about cardinalities here? Is it a lattice or a semilattice?

I'm sorry, I know this is a "tell me things about" question. If it's not liked I will try to change it.

$\endgroup$
1
  • $\begingroup$ One subset here is a filter $\mathscr{F}_{AC}$ of statement equivalences implied by $AC$, the other an ideal $\mathscr{I}_{AC}$ of statement equivalences that imply $AC$. $\endgroup$ – hardmath Dec 25 '14 at 13:46
7
$\begingroup$

First let's give a better definition of this preorder: $\sf ZF\vdash\varphi\rightarrow\psi$. Then the equivalence relation is $\sf ZF\vdash\varphi\leftrightarrow\psi$.

There are infinite chains, that much is easy to prove. First note that if we allow parameters, like $\kappa$ and $\lambda$, then $\sf DC_\kappa$ implies $\sf DC_\lambda$ if $\lambda\leq\kappa$. Since we don't allow parameters here, we have to reduce to definable $\aleph$'s, like $\aleph_0,\aleph_1,\ldots,\aleph_n$ and so on. This already gives you at least one chain whose length is infinite. One interesting question is to ask what is its length, but this seems to me equivalent (or at least closely related) to asking what is the proof theoretic ordinal of $\sf ZF$, and the answer I suspect is unknown.

Finite maximal chains are tricky objects, and I suspect they do not exist. The reason is that if $\varphi$ is neither provable from $\sf ZF$ nor it proves $\sf AC$, then it is usually the case that we can extend it "a little", by adding some of the missing choice to a small family of objects. For example, choice from families of finite sets doesn't imply the axiom of choice in full. We can, however, extend it a little bit by requiring choice from countable families of infinite sets; then from families of size $\aleph_1$ and so on. Maximal finite chain would have to be some sort of particular principle that extending it even a little will necessarily prove the axiom of choice. I can't think of one.

As for antichains, those are harder to investigate because to show that $\varphi$ and $\psi$ are incomparable you need to show that one principle doesn't imply the other and vice versa. Something inherently more difficult. But you can still cook an infinite antichain just by considering choice from finite families. In Jech "The Axiom of Choice" the last part of Chapter 7 deals with these situation and gives a condition from which we can at least show immediately that given $p,q$ prime numbers $C_p,C_q$ are comparable if and only if $p=q$ (where $C_n$ is the axiom of choice choice from families of sets of exactly $n$ members).

There are harder things to ask, about $\sf BPI$ or about the intricate structure of the real line, or questions about regulartiy of successor cardinals, and so on and so forth. The axiom of choice can be formulated in a zillion ways, and each way can be tweaked to be weakened in a gazillion different ways. So this partial order is indeed extremely complicated (even if it's just countable).

$\endgroup$
13
  • $\begingroup$ I can improve, and I can remove. But not without understanding my mistake. Dear downvoter, please explain what's wrong with my answer. $\endgroup$ – Asaf Karagila Dec 25 '14 at 14:32
  • $\begingroup$ Would it be possible to say if there are any finite maximal chains? $\endgroup$ – Bartek Dec 25 '14 at 14:38
  • $\begingroup$ Oh, I didn't downvote :) upvoting now :D $\endgroup$ – Bartek Dec 25 '14 at 14:39
  • $\begingroup$ Bartek, of course. For example if the conjunction of two statements imply the axiom of choice then they form a maximal antichain. There are plenty of examples like that. I'll add. $\endgroup$ – Asaf Karagila Dec 25 '14 at 14:41
  • $\begingroup$ I've added to my answer, by the way. $\endgroup$ – Asaf Karagila Dec 25 '14 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.