Hypothesis: Let $B$ be a well-ordered boolean algebra and let $F \subseteq B$ be a filter on $B$.

Goal: Show that $F$ can be extended to an ultrafilter without the axiom of choice (or any equivalent notion thereof).

I only know how to do this in the case that $B$ is countable:

  1. Let $b_0, b_1, \ldots$ denote the countable elements of $B$.

  2. Let $0$ denote the minimal element of $B$.

  3. Then $0 \notin F$ and if $U$ is an ultrafilter on $B$ then $0 \notin U$.

  4. Now begin extending $F$ to $F_1, F_2, \ldots , F_k, \ldots$ by inducting on the members of $B = \{b_0, b_1, \ldots\}$ as follows:

    Inductive Step: Suppose $b_k \notin F_{k-1}$. If $b_k \cdot a = 0$ for any $a \in F_{k-1}$, then let $F_k = F_{k-1} \cup \{\bar{b_k}\}$. Otherwise, let $F_{k} = F_{k-1} \cup \{b_k\}$.

  5. Letting $U = \bigcup_{k = 1}^\infty F_k$ gives us an ultrafilter extension of $F$ s.t. $U \subseteq B$ as desired. Furthermore, we did not use the axiom of choice.

But what happens if $B$ is uncountable (but still well-ordered)? Evidently it's still possible to show.


The proof of the general case is similar, proceeding to define a filter by transfinite recursion rather than by recursion on $\mathbb{N}$. (I am using "recursion" to refer to a method of defining a sequence, and "induction" to refer to a method of proving that every element of the sequence has some desired property such as the finite intersection property.)

If $B$ is well-ordered then we can enumerate its elements as $B = \{b_\alpha : \alpha < \kappa\}$ for some ordinal $\kappa$. The successor step of the recursive definition is the same as in the countable case $\kappa = \omega$, although in any case I think you only want to put the new element $b_\alpha$ into $F_{\alpha+1}$ if $b_\alpha \cdot a_0 \cdots a_{n-1} \ne 0$ for every finite subset $\{a_0,\ldots,a_{n-1}\} \subset F_\alpha$, so as to preserve the finite intersection property.

The new ingredient in the proof is the limit step. If we want to define $F_\lambda$ where $\lambda < \kappa$ is a limit ordinal, then we may assume as our inductive hypothesis that we have defined $F_\alpha$ at all previous steps $\alpha < \lambda$ and that these $F_\alpha$'s form an increasing chain under inclusion. Then we simply set $F_\lambda = \bigcup_{\alpha < \lambda} F_\alpha$ and observe that the finite intersection property is preserved under unions of chains.

Remark: It might be possible to define the ultrafilter more directly from the well-ordering using some trick. For example, given a well-ordered vector space one can define a basis for that space simply by taking all vectors that are not in the span of the vectors preceding them in the well-ordering. I don't know if there is a similar trick that would work here, but in any case the advantage of transfinite recursion is that it provides straightforward solutions to a large variety of problems once you know the basics of the method.

  • $\begingroup$ I'm a bit confused with your notation. In particular, why is that we can write $B = \{b_\alpha : \alpha < \kappa\}$? What exactly does that mean? The way I'm reading is "$B$ has some cardinality" -- but I'm sure that's not what you're meaning here. $\endgroup$ – user1770201 Oct 26 '13 at 10:08
  • $\begingroup$ @user1770201 Given a cardinal (or just an ordinal) $\kappa$ and a bijection (or just a surjection) $f:\kappa \to B$, we can write $B = \{f(\alpha) : \alpha < \kappa\}$. Because $\alpha < \kappa$ means the same thing as $\alpha \in \kappa$, this just says that $B$ is the range of $f$. Finally, we can denote $f(\alpha)$ by the more suggestive notation $b_\alpha$. We can think of $\{b_\alpha : \alpha < \kappa\}$ as an enumeration of the elements of $B$ in $\kappa$ many steps. $\endgroup$ – Trevor Wilson Oct 26 '13 at 17:18
  • $\begingroup$ @user1770201 Probably the confusing part (except for set theorists) is that for ordinals $\alpha$ and $\beta$ the notation $\alpha < \beta$ means the same thing as the notation $\alpha \in \beta$. All of the instances of "$<$" in the answer could be changed to "$\in$" but I'm not sure whether this would make it clearer. $\endgroup$ – Trevor Wilson Oct 26 '13 at 17:21
  • $\begingroup$ You meant to write "for some ordinal $\kappa$". Otherwise, without axiom of choice, there might be many cardinals which are not represented by ordinals, in which case the convention that cardinals are just initial ordinals isn't all that great, and the notation $\alpha<\kappa$ doesn't even make sense. $\endgroup$ – tomasz Oct 26 '13 at 21:51
  • $\begingroup$ @tomasz By cardinal I always mean "initial ordinal," even though, as you say, it may not be a great convention. In any case $\kappa$ in this particular situation is the cardinalty of $B$, which is assumed to be well-ordered. $\endgroup$ – Trevor Wilson Oct 26 '13 at 21:56

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.