In mathematics, the Hausdorff maximal principle is an alternate and earlier formulation of Zorn's lemma proved by Felix Hausdorff in 1914 (Moore 1982:168). It states that in any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset, where "maximal" is with respect to set inclusion.
In a partially ordered set, a totally ordered subset is also called a chain. Thus, the maximal principle says every chain in the set extends to a maximal chain.
The Hausdorff maximal principle is one of many statements equivalent to the axiom of choice over ZF (Zermelo–Fraenkel set theory without the axiom of choice). The principle is also called the Hausdorff maximality theorem or the Kuratowski lemma (Kelley 1955:33).
The Hausdorff maximal principle states that, in any partially ordered set , every chain (i.e., a totally ordered subset) is contained in a maximal chain (i.e., a chain that is not contained in a strictly larger chain in ). In general, there may be several maximal chains containing a given chain.
An equivalent form of the Hausdorff maximal principle is that in every partially ordered set, there exists a maximal chain. (Note if the set is empty, the empty subset is a maximal chain.)
This form follows from the original form since the empty set is a chain. Conversely, to deduce the original form from this form, consider the set of all chains in containing a given chain in . Then is partially ordered by set inclusion. Thus, by the maximal principle in the above form, contains a maximal chain . Let be the union of , which is a chain in since a union of a totally ordered set of chains is a chain. Since contains , it is an element of . Also, since any chain containing is contained in as is a union, is in fact a maximal element of ; i.e., a maximal chain in .
The proof that the Hausdorff maximal principle is equivalent to Zorn's lemma is somehow similar to this proof. Indeed, first assume Zorn's lemma. Since a union of a totally ordered set of chains is a chain, the hypothesis of Zorn's lemma (every chain has an upper bound) is satisfied for and thus contains a maximal element or a maximal chain in .
Conversely, if the maximal principle holds, then contains a maximal chain . By the hypothesis of Zorn's lemma, has an upper bound in . If , then is a chain containing and so by maximality, ; i.e., and so .
If A is any collection of sets, the relation "is a proper subset of" is a strict partial order on A. Suppose that A is the collection of all circular regions (interiors of circles) in the plane. One maximal totally ordered sub-collection of A consists of all circular regions with centers at the origin. Another maximal totally ordered sub-collection consists of all circular regions bounded by circles tangent from the right to the y-axis at the origin.
If (x0, y0) and (x1, y1) are two points of the plane , define (x0, y0) < (x1, y1) if y0 = y1 and x0 < x1. This is a partial ordering of under which two points are comparable only if they lie on the same horizontal line. The maximal totally ordered sets are horizontal lines in .
By the Hausdorff maximal principle, we can show every Hilbert space contains a maximal orthonormal subset as follows. [1] (This fact can be stated as saying that as Hilbert spaces.)
Let be the set of all orthonormal subsets of the given Hilbert space , which is partially ordered by set inclusion. It is nonempty as it contains the empty set and thus by the maximal principle, it contains a maximal chain . Let be the union of . We shall show it is a maximal orthonormal subset. First, if are in , then either or . That is, any given two distinct elements in are contained in some in and so they are orthogonal to each other (and of course, is a subset of the unit sphere in ). Second, if for some in , then cannot be in and so is a chain strictly larger than , a contradiction.
For the purpose of comparison, here is a proof of the same fact by Zorn's lemma. As above, let be the set of all orthonormal subsets of . If is a chain in , then the union of is also orthonormal by the same argument as above and so is an upper bound of . Thus, by Zorn's lemma, contains a maximal element . (So, the difference is that the maximal principle gives a maximal chain while Zorn's lemma gives a maximal element directly.)
The idea of the proof is essentially due to Zermelo and is to prove the following weak form of Zorn's lemma, from the axiom of choice. [2] [3]
(Zorn's lemma itself also follows from this weak form.) The maximal principle follows from the above since the set of all chains in satisfies the above conditions.
By the axiom of choice, we have a function such that for the power set of .
For each , let be the set of all such that is in . If , then let . Otherwise, let
Note is a maximal element if and only if . Thus, we are done if we can find a such that .
Fix a in . We call a subset a tower (over ) if
There exists at least one tower; indeed, the set of all sets in containing is a tower. Let be the intersection of all towers, which is again a tower.
Now, we shall show is totally ordered. We say a set is comparable in if for each in , either or . Let be the set of all sets in that are comparable in . We claim is a tower. The conditions 1. and 2. are straightforward to check. For 3., let in be given and then let be the set of all in such that either or .
We claim is a tower. The conditions 1. and 2. are again straightforward to check. For 3., let be in . If , then since is comparable in , either or . In the first case, is in . In the second case, we have , which implies either or . (This is the moment we needed to collapse a set to an element by the axiom of choice to define .) Either way, we have is in . Similarly, if , we see is in . Hence, is a tower. Now, since and is the intersection of all towers, , which implies is comparable in ; i.e., is in . This completes the proof of the claim that is a tower.
Finally, since is a tower contained in , we have , which means is totally ordered.
Let be the union of . By 2., is in and then by 3., is in . Since is the union of , and thus .
This section needs expansion. You can help by adding to it. (November 2024) |
The Bourbaki–Witt theorem can also be used to prove the Hausdorff maximal principle:
In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory equivalent to the statement that a Cartesian product of a collection of non-empty sets is non-empty. Informally put, the axiom of choice says that given any collection of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family of nonempty sets, there exists an indexed set such that for every . The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem. The axiom of choice is equivalent to the statement that every partition has a transversal.
In topology and related branches of mathematics, a connected space is a topological space that cannot be represented as the union of two or more disjoint non-empty open subsets. Connectedness is one of the principal topological properties that are used to distinguish topological spaces.
The Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a vector subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear functionals defined on every normed vector space to make the study of the dual space "interesting". Another version of the Hahn–Banach theorem is known as the Hahn–Banach separation theorem or the hyperplane separation theorem, and has numerous uses in convex geometry.
In the mathematical field of order theory, an ultrafilter on a given partially ordered set is a certain subset of namely a maximal filter on that is, a proper filter on that cannot be enlarged to a bigger proper filter on
In mathematics, the well-ordering theorem, also known as Zermelo's theorem, states that every set can be well-ordered. A set X is well-ordered by a strict total order if every non-empty subset of X has a least element under the ordering. The well-ordering theorem together with Zorn's lemma are the most important mathematical statements that are equivalent to the axiom of choice. Ernst Zermelo introduced the axiom of choice as an "unobjectionable logical principle" to prove the well-ordering theorem. One can conclude from the well-ordering theorem that every set is susceptible to transfinite induction, which is considered by mathematicians to be a powerful technique. One famous consequence of the theorem is the Banach–Tarski paradox.
In commutative algebra, the prime spectrum of a commutative ring is the set of all prime ideals of , and is usually denoted by ; in algebraic geometry it is simultaneously a topological space equipped with the sheaf of rings .
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain necessarily contains at least one maximal element.
In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geometric topology, and algebraic topology.
In mathematics, especially in order theory, a maximal element of a subset of some preordered set is an element of that is not smaller than any other element in . A minimal element of a subset of some preordered set is defined dually as an element of that is not greater than any other element in .
In mathematics, the Boolean prime ideal theorem 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 ideals, or distributive lattices and maximal ideals. This article focuses on prime ideal theorems from order theory.
In abstract algebra, a valuation ring is an integral domain D such that for every non-zero element x of its field of fractions F, at least one of x or x−1 belongs to D.
In mathematics, the Bourbaki–Witt theorem in order theory, named after Nicolas Bourbaki and Ernst Witt, is a basic fixed-point theorem for partially ordered sets. It states that if X is a non-empty chain complete poset, and such that for all then f has a fixed point. Such a function f is called inflationary or progressive.
In mathematics, a differentiable manifold is a type of manifold that is locally similar enough to a vector space to allow one to apply calculus. Any manifold can be described by a collection of charts (atlas). One may then apply ideas from calculus while working within the individual charts, since each chart lies within a vector space to which the usual rules of calculus apply. If the charts are suitably compatible, then computations done in one chart are valid in any other differentiable chart.
In mathematics, a family of sets is of finite character if for each , belongs to if and only if every finite subset of belongs to . That is,
In the mathematical discipline of functional analysis, the concept of a compact operator on Hilbert space is an extension of the concept of a matrix acting on a finite-dimensional vector space; in Hilbert space, compact operators are precisely the closure of finite-rank operators in the topology induced by the operator norm. As such, results from matrix theory can sometimes be extended to compact operators using similar arguments. By contrast, the study of general operators on infinite-dimensional spaces often requires a genuinely different approach.
In mathematics, the Teichmüller–Tukey lemma, named after John Tukey and Oswald Teichmüller, is a lemma that states that every nonempty collection of finite character has a maximal element with respect to inclusion. Over Zermelo–Fraenkel set theory, the Teichmüller–Tukey lemma is equivalent to the axiom of choice, and therefore to the well-ordering theorem, Zorn's lemma, and the Hausdorff maximal principle.
In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.
In order theory, the Szpilrajn extension theorem, proved by Edward Szpilrajn in 1930, states that every partial order is contained in a total order. Intuitively, the theorem says that any method of comparing elements that leaves some pairs incomparable can be extended in such a way that every pair becomes comparable. The theorem is one of many examples of the use of the axiom of choice in the form of Zorn's lemma to find a maximal set with certain properties.
In algebra, Zariski's lemma, proved by Oscar Zariski, states that, if a field K is finitely generated as an associative algebra over another field k, then K is a finite field extension of k.
This is a glossary of terms and definitions related to the topic of set theory.