The Independence of the Axiom of Choice from the Ultrafilter
Theorem
Jared Holshouser
February 27, 2014
It is known that the axiom of choice (AC) and the prime ideal theorem (PIT) are equivalent to many
important theorems. Halpern and Levy [2] showed in 1971 that PIT does not imply AC. We will prove the
same result here, but modify the techniques and language so as to be readily understood by a reader with a
basic knowledge of forcing. The form of PIT we will use here is as follows: every filter can be extended to
an ultrafilter. The paper has essentially three parts. We will 1. create an inner model of a generic extension
which fails choice, 2. use properties of the inner model to create a potential ultrafilter, and 3. use the
Halpern-Lauchli theorem to verify that it truly is an ultrafilter.
1
Forcing Preliminaries
Let P = F N (ω × ω, 2) and let G be L-generic for P .
Definition 1. G is a total function from ω × ω → 2. For each n ∈ ω, set xn = G(n, ·). Set A = {x1 , xn , · · ·}.
Proposition 1. A and the xn have canonical names.
o
n
(m,ˆ n), p : p(m, n) = 1 . Set A˙ = {(x˙n , 1P ) : n ∈ ω}.
Proof. For each n, m, set x˙n (m) =
Proposition 2. The xn are distinct.
Proof. By way of contradiction, suppose that p x˙i = x˙j . Let m be large enough so that (j, m), (i, m) ∈
/
dom(p). Let p ⊆ q be so that q(i, m) = 1 and q(j, m) = 0. Then q x˙ i (m)
ˆ = 1 and q x˙ j (m)
ˆ = 1. So
q x˙i 6= x˙j . This is a contradiction as q ≤ p.
2
Some Information About our Inner Model
We will work in L(A ∪ {A}). Recall the following:
Definition 2. We define L(A ∪ {A}) as follows:
• L0 (A ∪ {A}) = tr(A ∪ {A}), the transitive closure of A ∪ {A}.
• Lα+1 (A ∪ {A}) = D (Lα (A ∪ {A})).
• If β is a limit, then Lβ (A ∪ {A}) =
S
L(A ∪ {A}) = α∈On Lα (A ∪ {A}).
S
α<β
Lα (A ∪ {A}).
Theorem 1. L(A ∪ {A}) is a transitive model of ZF and L ⊆ L(A ∪ {A}) ⊆ L[G].
Proposition 3. Let X ∈ L(A ∪ {A}). Then X is definable from finitely many ordinals α1 , · · · , αm , finitely
many x1 , · · · , xn and A. We will usually write x ∈ X iff ϕ (x1 , · · · , xn , x) and suppress the ordinals and A.
1
Theorem 2. A is not well-orderable in L(A ∪ {A}). Fix x1 , · · · , xn ∈ A. Let X be the class of elements in
L(A ∪ {A}) which are definable from x1 , · · · , xn . Then X is well-ordered.
Proof. By way of contradiction suppose that there is a bijection f : ω → A in L(A ∪ {A}). Say that f (k) = y
iff ϕ (x1 , · · · , xn , y, k). Suppose that p ”f is a bijection”. Let i > n be so that (i, m) ∈
/ dom(p) for all
m. Then there is a q ≤ p and a k so that q ϕ (x˙ 1 , · · · , x˙ n , x˙ i , k). Let j > i be so that (j, m) ∈
/ dom(q)
for all m. Let π be a permutation of ω which fixes 1, · · · , n and takes i to j. Then π extends to an
automorphism of P which fixes x1 , · · · , xn and A and take xi to xj . Then π(q) and q are compatible, but
π(q) ϕ (x˙ 1 , · · · , x˙ n , x˙ j , k). This is a contradiction.
The rest of the proof follows analgously to the proof that L is well-ordered.
Proposition 4. Suppose that ψ (x1 , · · · , xn , y) is true in L(A ∪ {A}) where x1 , · · · , xn , y ∈ A. Then there
is an initial segment of y, q, so that if y 0 extends q (q y 0 ), then ψ (x1 , · · · , xn , y 0 ).
Proof. Suppose that p ψ L(A∪{A}) (x˙1 , · · · , x˙n , y).
˙ Say that y = xk for some k > n. Let p0 ≥ p be so
(i, j) ∈ dom(p0 ) ⇐⇒ (i, j) ∈ dom(p) ∧ i ∈ {1, · · · , n, k}
It suffices to show that p0 ψ L(A∪{A}) (x˙1 , · · · , x˙n , y).
˙ By way of contradiction. suppose that there is a
q ≤ p0 so that q ¬ψ (x˙1 , · · · , x˙n , y).
˙ Let π be a permutation of ω which fixes 1, · · · , n, k and moves the
parts of q which make it incompatible with p. Then π(q) ¬ψ (x˙1 , · · · , x˙n , y)
˙ and π(q) is compatible with
p. This is a contradiction.
3
The Basic Setup
Henceforth our calculations take place in L(A ∪ {A}) unless otherwise stated. The main result is as follows:
Theorem 3. Let X be a set and F be a filter on X which is definable from x1 , · · · , xn . Then there is an
ultrafilter U on X which is definable from x1 , · · · , xn .
We first create the largest filter possible using only x1 , · · · , xn .
Definition 3. Recall that the class of elements definable from x1 , · · · , xn is well-orderable. Let U extending
F be the maximal proper filter extending F which is definable from x1 , · · · , xn .
We claim that U is in fact an ultrafilter on X and proceed by way of contradiction. Suppose that there
is a B ⊆ X so that B and X r B are not in U. B is definable from x1 , · · · , xn , y1 , · · · , yk for some k and
some y1 , · · · , yk ∈ A r {x1 , · · · , xn }.
4
The Simple Case
We proceed first with k = 1. Say that B is defined from x1 , · · · , xn , y 0 by ϕ. For y ∈ A set
x ∈ By ⇐⇒ ϕ(x1 , · · · , xn , y, x)
Lemma 1. There is a q ∈ F N (ω, 2) so that if y ∈ A with q y, then By and X r By are not in U.
Proof. This follows from proposition 4.
Fix a q as in lemma 1. Let V be the filter generated by U and {By : q y ∧ y ∈ A}.
Lemma 2. V is definable from x1 , · · · , xn and thus V = P(X).
Proof. This follows by the maximality of U.
2
Proposition 5. We can find y1 , · · · , y` in A with q yi so that
(X r By1 ) ∪ · · · ∪ (X r By` ) ∈ U
Proof. Since V = P(X) we can find y1 , · · · , y` in A with q yi and a U ∈ U so that
(By1 ) ∩ · · · ∩ (By` ) ∩ U = ∅
So
X ⊆ (X r By1 ) ∪ · · · ∪ (X r By` ) ∪ (X r U )
and thus
U ⊆ (X r By1 ) ∪ · · · ∪ (X r By` )
Nothing about what we just did depended on us choosing to use By instead of X \ By . So we could run
all of the same proofs, and we get the following:
Proposition 6. We can find y1 , · · · , y` in A with q yi so that
(X r By1 ) ∪ · · · ∪ (X r By` ) , By1 ∪ · · · ∪ By` ∈ U
We now apply proposition 4 again.
Proposition 7. We can find q1 , · · · , q` ≤ q so that if ∀i(yi ∈ A ∧ qi yi ), then
(X r By1 ) ∪ · · · ∪ (X r By` ) , By1 ∪ · · · ∪ By` ∈ U
Set Q1 = {q1 , · · · , q` }. For each i we can run the above argument on qi exactly as we ran the argument
for q. So we get qij ≤ qi so that if yij ∈ A with qij yij for all j ≤ `i , then
[
[
X r Byj , Byj ∈ U
i
i
j
j
n o
Set Q2 = qij
i,j≤`i
n o
Lemma 3. Let yij ∈ A be so that qij yij for all i, j. Let h : yij
→ 2. Then
i,j
o
o
[n
[n
Byj : h yij = 1 ∈ U or
X r Byj : h yij = 0 ∈ U
i
i
Proof. If there is an i so that h is constant on the yij , then we are done by the comments preceding
this
lemma. So assume that for all i, h is not constant on yij . Then we can choose ji for each i so that h yiji = 1.
Then by the preceding proposition we are done as qi yiji .
n o
We claim that this is a contradiction. Fix yij ∈ A so that qij yij for all i, j. For h : yij
i,j
(
g(h, i, j) =
Byj
i
X r Byj
if h yij = 1
else
i
n o
Note that for each h : yij
→ 2 we have that
i,j
∅=
[
S
i,j
g(h, i, j) ∈ U. Thus
\[
Byj ∩ (X r Byj ) =
g(h, i, j) ∈ U
i
i
i,j
h i,j
Therefore ∅ ∈ U. This contradicts the properness of U.
3
→ 2, set
5
The Halpern-Lauchli Theorem
Definition 4. A tree is finitistic if T 6= ∅, each node of T has finite order, and each level of T is finite.
Definition 5. Let T be a finitistic tree. M ⊆ T is said to be (m, 1)-dense if there is a t ∈ T with |t| = m
so that whenever t < s and |s| = m + 1, there is a u ∈ M with s < u.
If T1 , · · · , Tk are finitistic trees and Mi ⊆ Ti is (m, 1)-dense for each i, we call M1 × · · · × Mk an (m, 1)matrix.
Theorem 4. Suppose that T1 , · · · , Tk are finitistic trees with no maximal nodes. Then there is an n so that
if f : T1 n × · · · × Tk n → 2, then we can find an m < n and an (m, 1)-matrix M1 × · · · × Mk ⊆ T1 n
× · · · × Tk n which is homogeneous for f .
Proof. This was originally proved via metamathematical means. A direct proof was given by Argyros,
Felouzis and Kanellopoulos in 2002[1].
6
The General Case
We now suppose that the set B is defined by ϕ (x1 , · · · , xn , y10 , · · · , yk0 , x). We will define k-sequences
Qn for all n. First we find qi so that if yi ∈ A and qi yi for all i and By1 ,··· ,yk is defined by
ϕ (x1 , · · · , xn , y1 , · · · yk , x), then By1 ,··· ,yk and x r By1 ,··· ,yk are not in U. Set Q0 = ({q1 } , · · · , {qn }).
Proposition 8. We can create k-sequences Qn for n ≥ 1 so that
1. If q ∈ Qn (i), then there is an r ∈ Qn−1 (i) so that q ≤ r.
2. If r ∈ Qn−1 (i), then there are q, q 0 ≤ r so that q 6= q 0 and q, q 0 ∈ Qn (i).
3. If q, r ∈ Qn (i), then q ⊥ r or q = r.
4. Let qi ∈ Qn−1 (i) for each i and suppose that Y ⊆ Ak is so that whenever we have ri ∈ Qn (i) with
ri ≤ qi for all i, there is a unique (y1 , · · · , yk ) ∈ Y with qi yi for all i. Then
[
{By1 ,··· ,yk : (y1 , · · · , yk ) ∈ Y } ∈ U
[
{X r By1 ,··· ,yk : (y1 , · · · , yk ) ∈ Y } ∈ U
Proof. The method
Q of construction is recursive. We simply apply the analysis of the simple case to each
(q1 , · · · , qk ) ∈ i Qn−1 (i) and let Qn (i) be the compilation of the resulting qij . (Qn (i) is built from all
sequences (q1 , · · · , qk ))
S
Definition 6. For 1 ≤ i ≤ k, set Ti = n∈ω Qn (i). q ≤i r iff r ≤ q. Set T = T1 × · · · × Tk .
Note that the nth level of T is Qn (1) × · · · × Qn (k) and that T satisfies the conditions of the HalpernLauchli theorem.
S
Let n be as guaranteed by Halpern-Lauchli. Let W = i<k,m≤n Qm (i) and let H : W → A be so that
hS
i
for all q ∈ W , q H(q). Finally let Yi = H
.
m≤n Qm (i)
4
Proposition 9. For all h : Y1 × · · · × Yk → 2,
[
{By1 ,··· ,yk : h (y1 , · · · , yk ) = 1} ∈ U
or
[
{X r By1 ,··· ,yk : h (y1 , · · · , yk ) = 0} ∈ U
Proof. Define f : T1 n × · · · × Tk n → 2 by
f (q1 , · · · , qn ) = h (H (q1 ) , · · · , H (qk ))
Let M = M1 × · · · × Mk be an (m, 1)-matrix and homogeneous for f . Suppose that f [M ] = 1. Then
h [(H[M1 ] × · · · × H[Mk ])] = 1
We can find qi ∈ Qm (i) so that for all r ∈ Qm+1 (i) if r ≤ qi , then there is a p ∈ Mi so that p ≤ r. Define
g : Qm+1 → A as follows: If there is an i so that r ≤ qi , let g(r) = H(p), where p ≤ r is in Mi . Otherwise
let g(r) be some y so that r y.
Note that r g(r) for all r. Thus from property 4
[
{By1 ,··· ,yk : qi yi ∧ ∃r (yi = g(r))} ∈ U
Now, if for all i, qi yi and there is an r so that yi = g(r), then r ≤ qi , and so yi = H(p) for some p ∈ Mi .
So by homogeneity,
H (y1 , · · · , yk ) = 1
If f [M ] = 0, consider fˆ = |1 − f |. Then fˆ[M ] = 1 and we apply the above proof.
This is a contradiction just as in the simple case. For h : Y1 ×· · ·×Yk → 2, and (y1 , · · · , yk ) ∈ Y1 ×· · ·×Yk ,
By1 ,··· ,yk
if h (y1 , · · · , yk ) = 1
g (h, y1 , · · · , yk ) =
X r By1 ,··· ,yk
else
S
Note that for each h : Y1 × · · · × Yk → 2 we have that y1 ,··· ,yk g (h, y1 , · · · , yk ) ∈ U. Thus
set
[
∅=
(By1 ,··· ,yk ∩ X r By1 ,··· ,yk ) =
y1 ,··· ,yk
\
[
g (h, y1 , · · · , yk ) ∈ U
h y1 ,··· ,yk
Therefore ∅ ∈ U.
7
References
References
[1] Argyros, S.A., V. Felouzis, and V. Kanellopoulos. ”A proof of Halpern-Lauchli partition theorem.” European Journal of Combinatorics 23.1 (2002): 1-10. Print.
[2] Halpern, J.D., and A. Levy. ”THE BOOLEAN PRIME IDEAL THEOREM DOES NOT IMPLY THE
AXIOM OF CHOICE.” Axiomatic Set Theory 13 (1971): 83-134. Print.
[3] Jech, Thomas J.. The axiom of choice. Dover ed. Mineola, N.Y.: Dover Publications, 2008. Print.
[4] Kunen, Kenneth. Set theory: an introduction to independence proofs. Amsterdam: North-Holland Pub.
Co. ;, 1980. Print.
5
© Copyright 2024 ExpyDoc
