# How do I apply the Boolean Prime Ideal Theorem?

I have become aware of an amazing phenomenon from a myriad of questions and answers here on MathOverflow: many of the results that I would typically prove using the Axiom of Choice can actually be proved using the logically weaker Boolean Prime Ideal Theorem. Apparently, the following can be proved using the BPI theorem:

I tempted to believe that almost every application of the Axiom of Choice that I would use in my everyday work actually follows from the Boolean Prime Ideal Theorem (except for those obviously equivalent to the Axiom of Choice, such as: every epimorphism in the category of sets is split).

Thus I wish to ask: Given that I know how to prove many "everyday" mathematical statements using the Axiom of Choice, how can I learn to prove them with the weaker Boolean Prime Ideal Theorem?

To make the question more precise, let's suppose that I know how to prove a result using Zorn's Lemma. Is there some standard method that I can use to put in just a bit more work and extract the same theorem using the BPI theorem?

The best I can think to do would be to use the restatement of the BPI theorem as the existence of ultrafilters. I have only ever seen this stated as being equivalent to the existence of an ultrafilter on every set. So first I should probably ask: does the BPI theorem that every filter on a ("nice enough") poset is contained in an ultrafilter?

If I have a poset $\mathcal{P}$ satisfying the usual Zorn property, the nice thing about Zorn's lemma is that it gives me an actual maximal element of the poset $\mathcal{P}$. The problem I see with existence of ultrafilters in $\mathcal{P}$ is that I do not obtain an actual element of $\mathcal{P}$, but a (rather large) subset. Is there a standard way that I can translate this back into an element of my poset $\mathcal{P}$? (For instance, should I pass to a least upper bound, because the posets that usually arise in Zorn applications are upper-complete?)

For instance, let's consider the first of the examples on the list above. Say $R$ is a commutative unital ring, and let $I \subsetneq R$ be a proper ideal of $R$. How can I prove using the BPI theorem that there is a prime ideal of $R$ containing $I$? I would typically consider the poset $\mathcal{P}$ of proper ideals of $R$ containing $I$, use Zorn's lemma to produce a maximal element $M$ of $\mathcal{P}$ (which will actually be a maximal ideal), and then prove that $M$ is prime. Supposing that the BPI theorem really gives me existence of ultrafilters in $\mathcal{P}$, I would probably start by considering the filter $\mathcal{F}$ of ideals containing $I$, and then pass to an ultrafilter containing this. Is there some way for me to obtain a prime ideal from such an ultrafilter? (And as I asked above, do I really obtain such an ultrafilter from the BPI theorem?)

I have included the "reference-request" tag because I would be satisfied with a reference to a survey paper that would teach me how to effectively apply the BPI theorem in a number of instances (including the ones above). While I would certainly be interested in references that show how to prove the above results (and any others!) using the BPI theorem, this would not be the kind of answer that I seek.

• The easiest way to learn how to do these proofs, is to read the papers. To find the papers, simply open Google Scholar or MathSciNet and try and search for keywords like "Hahn-Banach Prime Ideal" etc. Apr 9, 2015 at 16:14
• The point I didn't make in my previous comment is that these proofs are often very different from one another. They might appeal to various different equivalents of $\sf BPI$ (e.g. the compactness theorem of first-order logic; or the Tychonoff theorem for Hausdorff spaces). Apr 9, 2015 at 16:20
• Asaf, thanks for the tip. I can easily understand that the various applications of BPI in the literature are rather different. But I have seen proofs of all the facts listed above that make rather similar appeals to Zorn's Lemma; the "magic" typically lies in isolating the correct partially ordered set. So I'm wondering whether I can use the intuition that I've already built for this type of problem to similarly prove them using BPI. This is what prompted my question. Apr 9, 2015 at 16:26
• I’m not sure about Hahn–Banach, but the other three results mentioned have quite similar proofs: using the compactness theorem, embed the structure in a larger one realizing whatever extra stuff I need, and through away unwanted junk. Apr 9, 2015 at 17:38
• Or, to make the proofs look even more similar (though this is a kind of a brute-force method): (1) Prove the result in ZF for finitely generated (hence well-orderable) structures. (2) Using (1) and the compacteness theorem, embed (elementarily) a given structure into one for which the result holds. (3) Throw away unwanted junk. Apr 9, 2015 at 18:09

When I attempt to prove a result using BPI, my first attempt is usually to translate the problem into a satisfiability problem in propositional logic and use the Compactness Theorem (which is equivalent to BPI).

For example, to prove that every commutative ring $R$ has a prime ideal, consider the theory with one proposition $P_a$ for every $a \in R$ and the axioms: $$P_0, \lnot P_1, P_a \land P_b \to P_{a+b},P_a \to P_{ab}, P_{ab} \to P_a \lor P_b.$$ It's not difficult to show that this theory is finitely satisfiable. By the Compactness Theorem, the theory is satisfiable and, given a truth assignment that satisfies this theory, the set of all $a \in R$ such that $P_a$ is true forms a prime ideal of $R$.

Other examples of this trick can be found in my answers here and here.

This is not similar to Zorn's Lemma but I would contend that almost all similar maximality principles tend to give more than BPI would. The Consequences of the Axiom of Choice Project lists a great deal of equivalent statements to BPI (Form #14), very few bear much resemblance to Zorn's Lemma. Also note that all of them have some form of "finiteness" aspect to them which can be difficult to incorporate into maximality principles.

• It seems that I was half a minute faster... Apr 9, 2015 at 18:10
• @QiaochuYuan: The key issue with maximality is that it can't be formulated using a bunch of finitary requirements. Formulas in the first-order language of rings are finitary requirements but this is not always the best way to formulate them. Apr 9, 2015 at 18:50
• @MannyReyes I believe that $(\neg P_a) \implies \exists_b P_{ab-1}$ is a first order statement which expresses that $\{ x : P_x \}$ is a maximal ideal (in the presence of axioms saying that $\{ x : P_x \}$ is an ideal). I assume that finitary means something stronger than first order, and that this axiom is not finitary. Apr 9, 2015 at 19:48
• @DavidSpeyer: If $P(x)$ is thought as a first-order predicate rather than a bunch of propositional variables things trivialize since the theory I wrote down becomes finite. (Moreover, first-order logic doesn't allow us to control the objects of our structure: a model of the theory of rings and the first-order versions of the axioms I wrote is some ring with a prime ideal rather than a prime ideal on the given ring $R$.) Using propositions as in my answer, your "$\exists_b P_{ab-1}$" is really a disjunction $\bigvee_{b \in R} P_{ab-1}$, which doesn't work unless $R$ is finite. Apr 9, 2015 at 20:07
• You can take it as a first-order theory, include in it the diagram of $R$ to ensure that a model of the theory is an extension of $R$, and then intersect the ideal obtained with $R$. This works for prime ideals, and is IMHO more natural than encoding it in propositional logic. It does not work for maximal ideals, as the restriction of a maximal ideal to a subring needn't be maximal. Apr 9, 2015 at 23:00

I think that there is no general method to extract a "BPI" argument from a "Zorn" argument. But I think that in many cases it is easiest to phrase the BPI argument in terms of propositional logic, as follows:

Start with a list of yes/no questions that the desired object (the prime ideal $M$ of your ring, the linear order of your field, etc) should answer:

• Is $x$ in $M$? Is $y$ in $M$? (for all ring elements)
• Is $x \le y$? Is $p \le q$? (for all field elements. Of course you could be more economical and only ask questions of the form "Is $x\ge 0$?")
• etc.

Associate each question with a propositional variable, or in algebraic terms: with a generator of a free Boolean algebra.

Now write a wishlist of relations between the answers to these questions. If $\bar x$ is the variable/generator corresponding to the question "Is $x\in M$?", for any $x$ in the ring, then you want $\bar x \wedge \bar y \to \overline {x-y}$. (In the algebraic formulation, this is an element of the free algebra. "$\wedge$" and "$\to$" are the obvious binary operations on Boolean algebras, "$-$" is ring subtraction.)

The characteristic property of primeness is represented by the Boolean term $\overline{xy} \to (\bar x \vee \bar y)$. The characteristic property for linearity is represented by $\hat x \vee \widehat{-x}$, if $\hat x$ is the generator for the question "$x\ge 0$".

Collect your wishlist in a filter, and find an ultrafilter extending this filter. All generators/questions in the ultrafilter will get the answer "true"/"yes", hence also all formulas on your wishlist will get the value "true".

It seems to me that this method also works for Hahn-Banach. Your questions about the desired function $f$ (bounded by $\varphi$) will be of the form "Is $f(x) \le r$" for all vectors $x$ and all real numbers $r$. Your wishlist includes statements of the form $\overline{f(x) \le r}$ whenever $r=\varphi(x)$, or $\overline{f(x)\le r} \to \overline{f(y) \le s}$ whenever $y=\lambda x$, $\lambda>0$, $s=\lambda r$.

This proof (which was worked out in discussions with Alok Maharana) of the equivalence of the ultrafilter principle and the existence of a prime ideal uses as much commutative algebra as possible and as little order theory as possible.

Perhaps it will be illuminating for some people.

We use the facts that:

• a finitely generated commutative ring (a quotient of the polynomial ring $$\mathbb{Z}[x_1,\dots,x_n]$$) is Noetherian.
• such a ring, if non-trivial (i.e. $$1\neq 0$$), has a prime ideal by using the Noetherian property.

One can also directly prove that such a ring has a prime ideal. (Here is a neat proof by Todd Trimble that uses only induction.)

We begin with all that we need from order theory.

### Ultrafilter principle

A filter sub-base on a set $$X$$ is a collection $$\mathcal{S}$$ of subsets of $$X$$ which satisfies the finite intersection property (given $$C_1,\dots, C_k$$ in $$\mathcal{S}$$, the intersection $$C_1\cap\cdots\cap C_k$$ is non-empty).

The associated filter $$\mathcal{F}$$ consists of sets $$C$$ that contain some finite intersection of elements of $$\mathcal{S}$$.

One checks that it satisfies the property of a filter:

• $$\emptyset$$ is not contained in $$\mathcal{F}$$.
• If $$C$$ and $$D$$ are in $$\mathcal{G}$$, then $$C\cap D$$ is in $$\mathcal{F}$$.
• If $$C$$ is in $$\mathcal{F}$$ and $$C\subset D$$, then $$D$$ is in $$\mathcal{F}$$.

The ultrafilter principle says that $$\mathcal{F}$$ is contained in a filter $$\mathcal{U}$$ such that for every set $$C\subset X$$, either $$C$$ or $$C^{c}$$ is in $$\mathcal{U}$$.

Note that this means that given $$C$$, $$D$$ subsets of $$X$$ such that $$C\cap D$$ is empty and $$C\cup D$$ lies in $$\mathcal{U}$$, exactly one of $$C$$ and $$D$$ belongs to $$\mathcal{U}$$.

We wish to prove that this principle implies the existence of a prime ideal in a non-trivial commutative ring $$A$$.

### The set $$X$$ and a filter sub-base $$\mathcal{S}$$ on it

Each finitely generated subring $$R$$ of $$A$$ is non-trivial. Since $$R$$ is Noetherian it has a prime ideal $$P$$. For each such prime ideal $$P$$, we define a map $$h_P:R\to \{0,1\}$$ by $$h_P(a) = \begin{cases} 0 & a\in P \\ 1 & a\not\in P \end{cases}$$ We define $$H_R$$ as the subset of $$\mathrm{Map}(R,\{0,1\})$$ that consists of such maps $$h_P$$ for a fixed finitely generated subring $$R$$ of $$A$$. This is a non-empty set.

We define $$X$$ to be the disjoint union of $$H_R$$ as $$R$$ varies. Thus, an element of $$X$$ is $$h_P$$ for some prime ideal $$P$$ in some finitely generated subring $$R$$ of $$A$$.

For a finite subset $$K$$ of $$A$$, we define $$S_K$$ to be the subset of $$X$$ consisting of $$h_P$$ where $$R$$ contains $$K$$. By taking the ring $$R$$ to be the one generated by $$K$$, we see that $$H_R\subset S_K$$ so that $$S_K$$ is non-empty for every finite set $$K$$.

If $$K$$ and $$L$$ are finite sets, then $$S_K\cap S_L=S_{K\cup L}$$ is a non-empty set.

We put $$\mathcal{S}$$ as the collection of $$S_K$$'s as it satisfies the finite intersection property.

By the ultrafilter principle, we have an ultrafilter $$\mathcal{U}$$ that contains $$\mathcal{S}$$.

### The Prime ideal

Given an element $$x$$ in $$A$$, we consider the set $$S_{\{x\}}$$ and write it as the disjoint union of $$O_{x}$$ which consists of $$h$$ such that $$h(x)=0$$ and $$U_{x}$$ which consists of $$h$$ such that $$h(x)=1$$.

For every $$x$$ in $$X$$, the set $$S_{\{x\}}$$ is in $$\mathcal{U}$$. Thus, exactly one of $$O_x$$ and $$U_x$$ is in $$\mathcal{U}$$.

Define $$\mathcal{P}=\{x\in A: O_{x}\in\mathcal{U}\}$$. We claim that this is a prime ideal in $$A$$.

Given $$a,b\in \mathcal{P}$$ note that $$O_{a}\cap O_{b}=\{h\in S_{\{a,b\}}: h(a)=0=h(b)\}$$ is an element of $$\mathcal{U}$$. Further note that $$O_{a+b} \supset O_{a}\cap O_{b}$$ is then also an element of $$\mathcal{U}$$. It follows that $$a+b$$ lies in $$\mathcal{P}$$.

Given $$a\in \mathcal{P}$$ and $$b\in A$$, note that $$O_{ab}\supset O_{a}$$ is an element of $$\mathcal{U}$$. It follows that $$ab$$ lies in $$\mathcal{P}$$.

Given $$a\not\in \mathcal{P}$$ and $$b\not\in \mathcal{P}$$, note that $$U_{a}\cap U_{b} = \{h\in S_{\{a,b\}}: h(a)=1=h(b)\}$$ lies in $$\mathcal{U}$$. Further note that $$U_{ab} \supset U_{a}\cap U_{b}$$ is then also an element of $$\mathcal{U}$$. It follows that $$ab$$ does not lie in $$\mathcal{P}$$.

This proves that $$\mathcal{P}$$ is a prime ideal in $$A$$.

### Converse

A Boolean ring is a commutative ring of characteristic 2 such that every element is idempotent. It follows that all prime ideals are maximal and the quotient by a maximal ideal is $$\mathbb{F}_2$$.

The power set $$P(X)$$ is a Boolean ring with the usual operations: addition is symmetric difference and multiplication is intersection.

One shows that a filter $$\mathcal{F}$$ in $$P(X)$$ is a multiplicatively closed set in $$P(X)$$.

Thus, the ring $$B=\mathcal{F}^{-1}P(X)$$ is also a Boolean ring. So its prime ideals are maximal and are kernels of homomorphisms $$h:B\to\mathbb{F}_2$$.

Assume that $$B$$ has a prime/maximal ideal $$M$$ and let $$\tilde{h}:P(X)\to\mathbb{F}_2$$ be the composite of $$P(X)\to B$$ with $$h:B\to\mathbb{F}_2=B/M$$.

One shows that the collection of elements $$A$$ of $$P(X)$$ such that $$\tilde{h}(A)=1$$ is an ultrafilter $$\mathcal{U}$$ containing $$\mathcal{F}$$.

Thus, the existence of a prime ideal in $$B$$ implies the existence of an ultrafilter $$\mathcal{U}$$ containing $$\mathcal{F}$$.