4
$\begingroup$

First, I would like to say that I asked this question (a more general one actually) on math.stackexchange.com.

Consider the set $\varPhi$ of statements in the language of ZF that are weaker than AC (assuming ZF). If we define $\varphi\preceq\psi$ by $\sf ZF\vdash\varphi\rightarrow\psi$ then $\preceq$ is a preorder on $\varPhi$. This induces a partial order $\leq$ on $\varPhi/\sim$, where $\sim$ is the equivalence relation defined by $\sf ZF\vdash\varphi\leftrightarrow\psi$. The theorems of ZF form a single class in this equivalence relation, and it is the greatest element $\gamma$ under this partial order. The class of statements equivalent to AC under ZF (let's call it $\lambda$) is the least element.

I would like to know if it's possible to prove that there are no finite maximal chains or finite maximal antichains (other then the trivial $\{\lambda\}$ and $\{\gamma\}$). More generally, what are the possible (finite) cardinalities of maximal chains and antichains?

If there are other non-trivial things that can be said about this order, I would appreciate those too.

Improve this question
$\endgroup$
2
  • $\begingroup$ A terminological remark: you are describing the Lindenbaum-Tarski algebra of ZF and you are in particular looking at everything above $AC$ in this algebra. $\endgroup$
    – Andrej Bauer
    Dec 29, 2015 at 12:59
  • $\begingroup$ Hello @Andrej, thank you. Yes, Joel has explained it to me in his answer. At first I got the above and below the wrong way round, but it's clear to me now. $\endgroup$
    – Bartek
    Dec 29, 2015 at 20:19

2 Answers 2

Reset to default
6
$\begingroup$

It is not possible to prove there are no finite maximal antichains, because there are.

Paul Howard proved that Łoś's theorem and the Boolean Prime Ideal theorem imply in conjunction the Axiom of Choice. However there is a model in which every ultrafilter is principal, so Łoś's theorem holds trivially and therefore does not imply the Boolean Prime Ideal theorem; and there are models of the Boolean Prime Ideal theorem where Łoś's theorem fails (since the axiom of choice fails there).

Bell and Fremlin proved all sort of similar conjunctions related to Hahn-Banach, Krein-Milman, and other geometric theorems about Banach spaces, where the conjunction of two imply the axiom of choice. These constitute of finite maximal antichains as well.

And there are probably others, which are "less interesting", like "Every set can be injected into $\Bbb R\times\alpha$ for some ordinal $\alpha$" and "The real numbers can be well-ordered", which in conjunction imply the axiom of choice, but can hold separately without it.

Note that all the suggestions here are of size $2$. This is because any finite antichain can be reduced to one of size $2$; but we can always break principles up. We can replace "$\Bbb R$" by some other set which is the product of several distinct sets and then argue that only one of them can be well-ordered each time.

Edit: Note that the above treats "antichain" in the Boolean algebraic sense. It is certainly not the case that any choice principle either implies/follows from Łoś's theorem or from the Boolean Prime Ideal theorem. If we are interested in comparability rather than compatibility, then the answer is that every maximal antichain is either trivial or [countably] infinite, as remarked by Emil below Joel's answer.

As for finite maximal chains, the situation here is a bit less interesting and a bit more strained. For a finite antichain to be maximal it means that given any cardinality $X$, $\sf AC_X$, must be compatible with one of the principles in the chain, or imply the axiom of choice in conjunction. And that means that somehow we are in a situation where you already have quite a lot of choice, and any amount of choice above a specific set will readily imply the axiom. Similarly for comparing cardinalities of sets and $\aleph$ numbers.

Edit: As the algebra is in fact atomless, it follows that it is dense, so every finite chain can be extended by at least one more element which lies between two successive elements of the chain. Therefore every maximal chain must be infinite.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Asaf, just to be clear, you are also referring to the "incompatible" notion of antichain, rather than "incomparable", right? $\endgroup$
    – Joel David Hamkins
    Dec 28, 2015 at 12:31
  • $\begingroup$ Joel, yes, I noticed this earlier today, but I won't have time to edit my answer until later this evening. I was hoping no one will notice until then! ;-) $\endgroup$
    – Asaf Karagila ♦
    Dec 28, 2015 at 13:04
  • 1
    $\begingroup$ It is interesting to me how set theorists perceive the term "antichain" as in the context of forcing and Boolean algebras immediately, whereas most of other people think about the "usual", comparability related definition. $\endgroup$
    – Asaf Karagila ♦
    Dec 28, 2015 at 20:15
  • $\begingroup$ I agree. But in a Boolean algebra, the usual disjointness version of antichain is a far more useful and informative notion. If one thinks that all one has is a partial order, then the other notion may seem natural (even though we set theorists are instinctively completing our partial orders to complete Boolean algebras). $\endgroup$
    – Joel David Hamkins
    Dec 28, 2015 at 22:18
  • $\begingroup$ Which is why trees are fun, there the two notions join! :-) $\endgroup$
    – Asaf Karagila ♦
    Dec 28, 2015 at 22:21
6
$\begingroup$

The partial order of statements weaker than the axiom of choice is simply the upper-cone above AC in the Lindenbaum algebra of ZF statements. That is, it is a quotient of the Lindenbaum algebra by the principal ideal generated by the statement AC. In particular, it is a Boolean algebra, where in this case, the equivalence class of AC is $0$. With this perspective, one quickly realizes that every nontrivial statement $\varphi$ strictly weaker than AC, and therefore strictly above AC in the Lindenbaum algebra, forms a maximal antichain with its relative complement $\text{AC}\vee\neg\varphi$. So of course, every nontrivial statement is part of a finite maximal antichain. (Asaf had noted a few instances of this in his answer.)

Meanwhile, on the other side of the question, let me mention that since it is known, assuming the consistency of ZF, that there are infinitely many inequivalent statements weaker than AC (such as choice for families of various-sized finite sets, or DC for increasingly long transfinite sequences), it follows that the Boolean algebra is infinite. From this, it follows that there must be infinite antichains, simply because every infinite Boolean algebra has an infinite antichain.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ @KeithKearnes I was thinking of the sense of antichain in a Boolean algebra that is commonly used, where one refers to pairwise incompatible (disjoint) elements rather than merely incomparable elements (that is, they pairwise meet to $0$). In this case, any element and its complement do form a maximal antichain, and there needn't be atoms. But perhaps the OP intends to refer to antichain in the "incomparable" sense, in which case I would agree with you. $\endgroup$
    – Joel David Hamkins
    Dec 28, 2015 at 4:34
  • 1
    $\begingroup$ @Bartek, Given that you're basically talking about the Lindenbaum algebra, which tells the whole story about your order, I would think the natural questions here are about the structure of it as a Boolean algebra, rather than specifically about maximal pairwise incomparable sets. You should want to know if there are atoms, and how many, whether it is an atomic Boolean algebra. Since it is countable and infinite, it cannot be complete. Does it have the Cohen algebra as a subalgebra? $\endgroup$
    – Joel David Hamkins
    Dec 28, 2015 at 12:37
  • 5
    $\begingroup$ The Lindenbaum-Tarski algebra of any countable theory interpreting a modicum of arithmetic is the unique countable atomless Boolean algebra. This follows from the incompleteness theorem. $\endgroup$
    – Emil Jeřábek
    Dec 28, 2015 at 12:43
  • 1
    $\begingroup$ @Emil: that answers every order-theoretic question here. How about a specific countable sequence of sentences representing free generators? $\endgroup$
    – Keith Kearnes
    Dec 28, 2015 at 15:09
  • 2
    $\begingroup$ @EmilJeřábek Ah, of course, that's great! I'd suggest that you post an answer will a fuller explanation. I had been thinking there might be atoms, but we know in fact it is dense. $\endgroup$
    – Joel David Hamkins
    Dec 28, 2015 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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