Boolean prime ideal theorem
Encyclopedia
In mathematics
, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra
. A common example is the Boolean prime ideal theorem, which states that ideals
in a Boolean algebra can be extended to prime ideals
. A variation of this statement for filters
on sets is known as the ultrafilter lemma. Other theorems are obtained by considering different mathematical structures with appropriate notions of ideals, for example, rings
and prime ideal
s (of ring theory), or distributive lattice
s and maximal ideals (of order theory
). This article focuses on prime ideal theorems from order theory
.
Although the various prime ideal theorems may appear simple and intuitive, they cannot be derived in general from the axioms of Zermelo–Fraenkel set theory
(ZF). Instead, some of the statements turn out to be equivalent to the axiom of choice (AC), while others—the Boolean prime ideal theorem, for instance—represent a property that is strictly weaker than AC. It is due to this intermediate status between ZF and ZF + AC (ZFC) that the Boolean prime ideal theorem is often taken as an axiom of set theory. The abbreviations BPI or PIT (for Boolean algebras) are sometimes used to refer to this additional axiom.
is a (non-empty) directed
lower set. If the considered poset has binary suprema
(a.k.a. joins
), as do the posets within this article, then this is equivalently characterized as a lower set I which is closed for binary suprema (i.e. x, y in I imply x
y in I). An ideal I is prime if, whenever an infimum
x
y is in I, one also has x in I or y in I. Ideals are proper if they are not equal to the whole poset.
Historically, the first statement relating to later prime ideal theorems was in fact referring to filters—subsets that are ideals with respect to the dual
order. The ultrafilter lemma states that every filter on a set is contained within some maximal (proper) filter—an ultrafilter. Recall that filters on sets are proper filters of the Boolean algebra of its powerset. In this special case, maximal filters (i.e. filters that are not strict subsets of any proper filter) and prime filters (i.e. filters that with each union of subsets X and Y contain also X or Y) coincide. The dual of this statement thus assures that every ideal of a powerset is contained in a prime ideal.
The above statement led to various generalized prime ideal theorems, each of which exists in a weak and in a strong form. Weak prime ideal theorems state that every non-trivial algebra of a certain class has at least one prime ideal. In contrast, strong prime ideal theorems require that every ideal that is disjoint from a given filter can be extended to a prime ideal which is still disjoint from that filter. In the case of algebras that are not posets, one uses different substructures instead of filters. Many forms of these theorems are actually known to be equivalent, so that the assertion that "PIT" holds is usually taken as the assertion that the corresponding statement for Boolean algebras (BPI) is valid.
Another variation of similar theorems is obtained by replacing each occurrence of prime ideal by maximal ideal. The corresponding maximal ideal theorems (MIT) are often—though not always—stronger than their PIT equivalents.
The weak prime ideal theorem for Boolean algebras simply states:
We refer to these statements as the weak and strong BPI. The two are equivalent, as the strong BPI clearly implies the weak BPI, and the reverse implication can be achieved by using the weak BPI to find prime ideals in the appropriate quotient algebra.
The BPI can be expressed in various ways. For this purpose, recall the following theorem:
For any ideal I of a Boolean algebra B, the following are equivalent:
This theorem is a well-known fact for Boolean algebras. Its dual establishes the equivalence of prime filters and ultrafilters. Note that the last property is in fact self-dual—only the prior assumption that I is an ideal gives the full characterization. It is worth mentioning that all of the implications within this theorem can be proven in classical Zermelo-Fraenkel set theory.
Thus the following (strong) maximal ideal theorem (MIT) for Boolean algebras is equivalent to BPI:
Note that one requires "global" maximality, not just maximality with respect to being disjoint from F. Yet, this variation yields another equivalent characterization of BPI:
The fact that this statement is equivalent to BPI is easily established by noting the following theorem: For any distributive lattice
L, if an ideal I is maximal among all ideals of L that are disjoint to a given filter F, then I is a prime ideal. The proof for this statement (which can again be carried out in ZF set theory) is included in the article on ideals
. Since any Boolean algebra is a distributive lattice, this shows the desired implication.
All of the above statements are now easily seen to be equivalent. Going even further, one can exploit the fact the dual orders of Boolean algebras are exactly the Boolean algebras themselves. Hence, when taking the equivalent duals of all former statements, one ends up with a number of theorems that equally apply to Boolean algebras, but where every occurrence of ideal is replaced by filter. It is worth noting that for the special case where the Boolean algebra under consideration is a powerset with the subset
ordering, the "maximal filter theorem" is called the ultrafilter lemma.
Summing up, for Boolean algebras, the weak and strong MIT, the weak and strong PIT, and these statements with filters in place of ideals are all equivalent. It is known that all of these statements are consequences of the axiom of choice (the easy proof makes use of Zorn's lemma
), but cannot be proven in classical Zermelo-Fraenkel set theory. Yet, the BPI is strictly weaker than the axiom of choice, though the proof of this statement, due to J. D. Halpern and Azriel Levy
is rather non-trivial.
, such as distributive lattice
s or Heyting algebra
s. However, in these cases maximal ideals are different from prime ideals, and the relation between PITs and MITs is not obvious.
Indeed, it turns out that the MITs for distributive lattices and even for Heyting algebras are equivalent to the axiom of choice. On the other hand, it is known that the strong PIT for distributive lattices is equivalent to BPI (i.e. to the MIT and PIT for Boolean algebras). Hence this statement is strictly weaker than the axiom of choice. Furthermore, observe that Heyting algebras are not self dual, and thus using filters in place of ideals yields different theorems in this setting. Maybe surprisingly, the MIT for the duals of Heyting algebras is not stronger than BPI, which is in sharp contrast to the abovementioned MIT for Heyting algebras.
Finally, prime ideal theorems do also exist for other (not order-theoretical) abstract algebras. For example, the MIT for rings implies the axiom of choice. This situation requires to replace the order-theoretic term "filter" by other concepts—for rings a "multiplicatively closed subset" is appropriate.
on a set X is a collection of nonempty subsets of X that is closed under finite intersection and under superset. An ultrafilter is a maximal filter. The ultrafilter lemma states that every filter
on a set X is a subset of some ultrafilter
on X (a maximal filter of nonempty subsets of X). This lemma is most often used in the study of topology
. An ultrafilter that does not contain finite sets is called non-principal. The existence of non-principal ultrafilters is due to Tarski in 1930.
The ultrafilter lemma is equivalent to the Boolean prime ideal theorem, with the equivalence provable in ZF set theory without the axiom of choice. The idea behind the proof is that the subsets of any set form a Boolean algebra partially ordered by inclusion, and any Boolean algebra is representable as an algebra of sets by Stone's representation theorem.
, a special case of Stone duality
, in which one equips the set of all prime ideals with a certain topology
and can indeed regain the original Boolean algebra (up to
isomorphism
) from this data. Furthermore, it turns out that in applications one can freely choose either to work with prime ideals or with prime filters, because every ideal uniquely determines a filter: the set of all Boolean complements of its elements. Both approaches are found in the literature.
Many other theorems of general topology that are often said to rely on the axiom of choice are in fact equivalent to BPI. For example, the theorem that a product of compact Hausdorff spaces is compact is equivalent to it. If we leave out "Hausdorff" we get a theorem equivalent to the full axiom of choice.
A not too well known application of the Boolean prime ideal theorem is the existence of a non-measurable set
(the example usually given is the Vitali set
, which requires the Axiom of Choice). From this and the fact that the BPI is strictly weaker than the Axiom of Choice, it follows that the existence of non-measurable sets is strictly weaker than the axiom of choice.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra
Abstract algebra
Abstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
. A common example is the Boolean prime ideal theorem, which states that ideals
Ideal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
in a Boolean algebra can be extended to prime ideals
Ideal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
. A variation of this statement for filters
Filter (mathematics)
In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...
on sets is known as the ultrafilter lemma. Other theorems are obtained by considering different mathematical structures with appropriate notions of ideals, for example, rings
Ring (mathematics)
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
and prime ideal
Prime ideal
In algebra , a prime ideal is a subset of a ring which shares many important properties of a prime number in the ring of integers...
s (of ring theory), or distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
s and maximal ideals (of order theory
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
). This article focuses on prime ideal theorems from order theory
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
.
Although the various prime ideal theorems may appear simple and intuitive, they cannot be derived in general from the axioms of Zermelo–Fraenkel set theory
Zermelo–Fraenkel set theory
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...
(ZF). Instead, some of the statements turn out to be equivalent to the axiom of choice (AC), while others—the Boolean prime ideal theorem, for instance—represent a property that is strictly weaker than AC. It is due to this intermediate status between ZF and ZF + AC (ZFC) that the Boolean prime ideal theorem is often taken as an axiom of set theory. The abbreviations BPI or PIT (for Boolean algebras) are sometimes used to refer to this additional axiom.
Prime ideal theorems
Recall that an order idealIdeal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
is a (non-empty) directed
Directed set
In mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤...
lower set. If the considered poset has binary suprema
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
(a.k.a. joins
Join and meet
In mathematics, join and meet are dual binary operations on the elements of a partially ordered set. A join on a set is defined as the supremum with respect to a partial order on the set, provided a supremum exists...
), as do the posets within this article, then this is equivalently characterized as a lower set I which is closed for binary suprema (i.e. x, y in I imply x
y in I). An ideal I is prime if, whenever an infimumInfimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...
x
y is in I, one also has x in I or y in I. Ideals are proper if they are not equal to the whole poset.Historically, the first statement relating to later prime ideal theorems was in fact referring to filters—subsets that are ideals with respect to the dual
Duality (order theory)
In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the set with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P...
order. The ultrafilter lemma states that every filter on a set is contained within some maximal (proper) filter—an ultrafilter. Recall that filters on sets are proper filters of the Boolean algebra of its powerset. In this special case, maximal filters (i.e. filters that are not strict subsets of any proper filter) and prime filters (i.e. filters that with each union of subsets X and Y contain also X or Y) coincide. The dual of this statement thus assures that every ideal of a powerset is contained in a prime ideal.
The above statement led to various generalized prime ideal theorems, each of which exists in a weak and in a strong form. Weak prime ideal theorems state that every non-trivial algebra of a certain class has at least one prime ideal. In contrast, strong prime ideal theorems require that every ideal that is disjoint from a given filter can be extended to a prime ideal which is still disjoint from that filter. In the case of algebras that are not posets, one uses different substructures instead of filters. Many forms of these theorems are actually known to be equivalent, so that the assertion that "PIT" holds is usually taken as the assertion that the corresponding statement for Boolean algebras (BPI) is valid.
Another variation of similar theorems is obtained by replacing each occurrence of prime ideal by maximal ideal. The corresponding maximal ideal theorems (MIT) are often—though not always—stronger than their PIT equivalents.
Boolean prime ideal theorem
The Boolean prime ideal theorem is the strong prime ideal theorem for Boolean algebras. Thus the formal statement is:- Let B be a Boolean algebra, let I be an ideal and let F be a filter of B, such that I and F are disjoint. Then I is contained in some prime ideal of B that is disjoint from F.
The weak prime ideal theorem for Boolean algebras simply states:
- Every Boolean algebra contains a prime ideal.
We refer to these statements as the weak and strong BPI. The two are equivalent, as the strong BPI clearly implies the weak BPI, and the reverse implication can be achieved by using the weak BPI to find prime ideals in the appropriate quotient algebra.
The BPI can be expressed in various ways. For this purpose, recall the following theorem:
For any ideal I of a Boolean algebra B, the following are equivalent:
- I is a prime ideal.
- I is a maximal proper ideal, i.e. for any proper ideal J, if I is contained in J then I = J.
- For every element a of B, I contains exactly one of {a, ¬a}.
This theorem is a well-known fact for Boolean algebras. Its dual establishes the equivalence of prime filters and ultrafilters. Note that the last property is in fact self-dual—only the prior assumption that I is an ideal gives the full characterization. It is worth mentioning that all of the implications within this theorem can be proven in classical Zermelo-Fraenkel set theory.
Thus the following (strong) maximal ideal theorem (MIT) for Boolean algebras is equivalent to BPI:
- Let B be a Boolean algebra, let I be an ideal and let F be a filter of B, such that I and F are disjoint. Then I is contained in some maximal ideal of B that is disjoint from F.
Note that one requires "global" maximality, not just maximality with respect to being disjoint from F. Yet, this variation yields another equivalent characterization of BPI:
- Let B be a Boolean algebra, let I be an ideal and let F be a filter of B, such that I and F are disjoint. Then I is contained in some ideal of B that is maximal among all ideals disjoint from F.
The fact that this statement is equivalent to BPI is easily established by noting the following theorem: For any distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
L, if an ideal I is maximal among all ideals of L that are disjoint to a given filter F, then I is a prime ideal. The proof for this statement (which can again be carried out in ZF set theory) is included in the article on ideals
Ideal (order theory)
In mathematical order theory, an ideal is a special subset of a partially ordered set . Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion...
. Since any Boolean algebra is a distributive lattice, this shows the desired implication.
All of the above statements are now easily seen to be equivalent. Going even further, one can exploit the fact the dual orders of Boolean algebras are exactly the Boolean algebras themselves. Hence, when taking the equivalent duals of all former statements, one ends up with a number of theorems that equally apply to Boolean algebras, but where every occurrence of ideal is replaced by filter. It is worth noting that for the special case where the Boolean algebra under consideration is a powerset with the subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
ordering, the "maximal filter theorem" is called the ultrafilter lemma.
Summing up, for Boolean algebras, the weak and strong MIT, the weak and strong PIT, and these statements with filters in place of ideals are all equivalent. It is known that all of these statements are consequences of the axiom of choice (the easy proof makes use of Zorn's lemma
Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Suppose a partially ordered set P has the property that every chain has an upper bound in P...
), but cannot be proven in classical Zermelo-Fraenkel set theory. Yet, the BPI is strictly weaker than the axiom of choice, though the proof of this statement, due to J. D. Halpern and Azriel Levy
Azriel Levy
Azriel Levy is an Israeli mathematician, logician, and a professor emeritus at the Hebrew University of Jerusalem....
is rather non-trivial.
Further prime ideal theorems
The prototypical properties that were discussed for Boolean algebras in the above section can easily be modified to include more general latticesLattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...
, such as distributive lattice
Distributive lattice
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection...
s or Heyting algebra
Heyting algebra
In mathematics, a Heyting algebra, named after Arend Heyting, is a bounded lattice equipped with a binary operation a→b of implication such that ∧a ≤ b, and moreover a→b is the greatest such in the sense that if c∧a ≤ b then c ≤ a→b...
s. However, in these cases maximal ideals are different from prime ideals, and the relation between PITs and MITs is not obvious.
Indeed, it turns out that the MITs for distributive lattices and even for Heyting algebras are equivalent to the axiom of choice. On the other hand, it is known that the strong PIT for distributive lattices is equivalent to BPI (i.e. to the MIT and PIT for Boolean algebras). Hence this statement is strictly weaker than the axiom of choice. Furthermore, observe that Heyting algebras are not self dual, and thus using filters in place of ideals yields different theorems in this setting. Maybe surprisingly, the MIT for the duals of Heyting algebras is not stronger than BPI, which is in sharp contrast to the abovementioned MIT for Heyting algebras.
Finally, prime ideal theorems do also exist for other (not order-theoretical) abstract algebras. For example, the MIT for rings implies the axiom of choice. This situation requires to replace the order-theoretic term "filter" by other concepts—for rings a "multiplicatively closed subset" is appropriate.
The ultrafilter lemma
A filterFilter (mathematics)
In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...
on a set X is a collection of nonempty subsets of X that is closed under finite intersection and under superset. An ultrafilter is a maximal filter. The ultrafilter lemma states that every filter
Filter (mathematics)
In mathematics, a filter is a special subset of a partially ordered set. A frequently used special case is the situation that the ordered set under consideration is just the power set of some set, ordered by set inclusion. Filters appear in order and lattice theory, but can also be found in...
on a set X is a subset of some ultrafilter
Ultrafilter
In the mathematical field of set theory, an ultrafilter on a set X is a collection of subsets of X that is a filter, that cannot be enlarged . An ultrafilter may be considered as a finitely additive measure. Then every subset of X is either considered "almost everything" or "almost nothing"...
on X (a maximal filter of nonempty subsets of X). This lemma is most often used in the study of topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
. An ultrafilter that does not contain finite sets is called non-principal. The existence of non-principal ultrafilters is due to Tarski in 1930.
The ultrafilter lemma is equivalent to the Boolean prime ideal theorem, with the equivalence provable in ZF set theory without the axiom of choice. The idea behind the proof is that the subsets of any set form a Boolean algebra partially ordered by inclusion, and any Boolean algebra is representable as an algebra of sets by Stone's representation theorem.
Applications
Intuitively, the Boolean prime ideal theorem states that there are "enough" prime ideals in a Boolean algebra in the sense that we can extend every ideal to a maximal one. This is of practical importance for proving Stone's representation theorem for Boolean algebrasStone's representation theorem for Boolean algebras
In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...
, a special case of Stone duality
Stone duality
In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they form a natural generalization of Stone's representation...
, in which one equips the set of all prime ideals with a certain topology
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
and can indeed regain the original Boolean algebra (up to
Up to
In mathematics, the phrase "up to x" means "disregarding a possible difference in x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...
isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations. If there exists an isomorphism between two structures, the two structures are said to be isomorphic. In a certain sense, isomorphic structures are...
) from this data. Furthermore, it turns out that in applications one can freely choose either to work with prime ideals or with prime filters, because every ideal uniquely determines a filter: the set of all Boolean complements of its elements. Both approaches are found in the literature.
Many other theorems of general topology that are often said to rely on the axiom of choice are in fact equivalent to BPI. For example, the theorem that a product of compact Hausdorff spaces is compact is equivalent to it. If we leave out "Hausdorff" we get a theorem equivalent to the full axiom of choice.
A not too well known application of the Boolean prime ideal theorem is the existence of a non-measurable set
Non-measurable set
In mathematics, a non-measurable set is a set whose structure is so complicated that it cannot be assigned any meaningful measure. Such sets are constructed to shed light on the notions of length, area and volume in formal set theory....
(the example usually given is the Vitali set
Vitali set
In mathematics, a Vitali set is an elementary example of a set of real numbers that is not Lebesgue measurable, found by . The Vitali theorem is the existence theorem that there are such sets. There are uncountably many Vitali sets, and their existence is proven on the assumption of the axiom of...
, which requires the Axiom of Choice). From this and the fact that the BPI is strictly weaker than the Axiom of Choice, it follows that the existence of non-measurable sets is strictly weaker than the axiom of choice.