Comment.Math.Univ.Carolin. 56,4 (2015) 543–546 543
A proof of the independence of the Axiom of Choice from the Boolean Prime Ideal Theorem
Miroslav Repick´y
Abstract. We present a proof of the Boolean Prime Ideal Theorem in a transitive model of ZF in which the Axiom of Choice does not hold. We omit the argument based on the full Halpern-L¨auchli partition theorem and instead we reduce the proof to its elementary case.
Keywords: Boolean Prime Ideal Theorem; the Axiom of Choice Classification: Primary 03E35, Secondary 03E25, 03E40, 03E45
Let us recall the following result.
Theorem 1 (Halpern and L´evy [2]). There is a transitive model of ZF in which the Boolean Prime Ideal Theorem holds and the Axiom of Choice fails.
In the paper, we assume V ZFC and we consider the following transitive model M (see [3, pp. 184–187] or [4, pp. 221–223]). Let P be the set of finite functionspsuch that dom(p)⊆ω×ωand rng(p)⊆ {0,1}. LetG⊆P be a generic set of conditions. Fori∈ω let
ai(n) =
(1, if (∃p∈G)p(i, n) = 1, 0, otherwise,
A={ai:i∈ω}, M = HODV[G](A).
ThenM is a transitive model of ZF andA∈M. The Axiom of Choice does not hold inM because the setAis infinite and has no countable subset inM (see [3]).
We prove the Boolean Prime Ideal Theorem inM = HODV[G](A). The present proof uses the same ideas as the proof in [2] but its exposition relies on [3]. We also omit the argument from [2] based on the full Halpern-L¨auchli partition theorem [1]
and instead we reduce the proof to its elementary case substantiated in [2].
Recall that [u] ={x∈ω2 :u⊆x}for any finite functionusuch that dom(u)⊆ ω and rng(u) ∈ {0,1}. For t∈ m(ω2) andk ∈ω, [t↾↾k] =Q
i<m[t(i)↾k] denotes a basic clopen set inm(ω2).
DOI 10.14712/1213-7243.2015.138
The author was supported by grants VEGA 1/0002/12 and APVV-0269-11.
544 Repick´y M.
Lemma 2(Schema of continuity). Letϕ(x1, . . . , xn, s, A)be a formula of ZF with no free variables other thanx1, . . . ,xn,s,A. Ifx1, . . . , xn∈V,m∈ω,s∈mAis a sequence of distinct members ofA, andϕ(x1, . . . , xn, s, A)holds inV[G], then there is a basic clopen setU ⊆m(ω2)with pairwise disjoint projections inω2such thats∈U andϕ(x1, . . . , xn, t, A)holds inV[G]for everyt∈U ∩mA.
Proof: Let W be the set of all one-to-one functions in mω. For h ∈ W let h∗∈mAbe defined byh∗(i) =ah(i). Forh∈W let
b(h) =kϕ(x1, . . . , xn,h˙∗,A)k,˙ c(h) =W
k∈ω
V
z∈W − kz˙∗∈[ ˙h∗↾↾k]k ∨ kϕ(x1, . . . , xn,z˙∗,A)k˙
=k(∃k∈ω)(∀z∈W) ˙z∗∈[ ˙h∗↾↾k]→ϕ(x1, . . . , xn,z˙∗,A)k˙
where ˙h∗, ˙z∗, and ˙A denote the canonical names for h∗, z∗, and A constructed by means of the canonical names ˙ai fori∈ω. The inequality b(h)≤c(h) means that ifϕ(x1, . . . , xn, s, A) holds in V[G] fors=h∗, then there isk∈ω such that the conclusion of the lemma holds for the clopen setU = [s↾↾k]. Then, sincesis one-to-one, the projections ofU are pairwise disjoint if kis sufficiently large. We proveb(h)≤c(h) for allh∈W.
Letp′ ∈P satisfyp′ ≤b(h) and we findp≤p′ such that p≤c(h). Extendp′ to a conditionp⊇p′ so that dom(p) =k×kfor somek∈ω, rng(h)⊆k, and for alli < j < k there isl < k such thatp(i, l)6=p(j, l). For every q∈P letqi be defined byqi(j) = q(i, j). Then pi ∈k2 fori < k are pairwise incompatible and p[ ˙h∗↾↾k] =Q
i<m[ph(i)]. We prove that p≤c(h).
To get a contradiction assume that for some z ∈ W there is r ≤ p such that r z˙∗ ∈ [ ˙h∗↾↾k] and r ¬ϕ(x1, . . . , xn,z˙∗,A); the former assumption is˙ equivalent to saying that rz(i)↾k = ph(i) for all i < m. If z(i) 6= h(i), then z(i)> h(i) because pj forj < k are pairwise incompatible. Letπbe the permu- tation ofω that interchangesh(i) andz(i) for alli < mandπ(j) =j otherwise.
The permutationπinduces an automorphism ofP and an automorphism ofVP, i.e., for p, q ∈ P, q = π(p) if q(π(i), j) = p(i, j). By the symmetry lemma π(r) ¬ϕ(x1, . . . , xn, π( ˙z∗), π( ˙A)) which is impossible because π(r) and p are compatible,π( ˙z∗) = ˙h∗,π( ˙A) = ˙A, andpϕ(x1, . . . , xn,h˙∗,A). This contradic-˙ tion proves that there is no suchrand hencep≤c(h).
LetF ∈[A]m. We say that a sequencehUi :i < miof pairwise disjoint basic open sets inω2 distinguishesF, if|F∩Ui|= 1 for alli < m.
Corollary 3. Letϕ(x1, . . . , xn, F)be a formula of ZF with no free variables other than x1, . . . , xn, F. Ifs ∈ <ωA, x1, . . . , xn ∈ ODV[G][A, s], F′ ⊆A\rng(s) is a finite set,m=|F′|, andϕ(x1, . . . , xn, F′)holds inV[G], then there is a sequence of basic open sets hUi : i < mi in ω2 disjoint from rng(s) and distinguishing members ofF′ such thatϕ(x1, . . . , xn, F)holds inV[G]for everyF∈[A]msuch that |F∩Ui|= 1for alli < m.
A proof of the independence of the Axiom of Choice 545 Proof: Assume |s| = k and let t′ : m → F′ be any one-to-one enumeration.
There is a formulaψ such that for some ordinalsα1, . . . ,αr,
V[G](∀t)ψ(α1, . . . , αr, s⌢t, A)→ϕ(x1, . . . , xn,rng(t)), and V[G]ψ(α1, . . . , αr, s⌢t′, A).
By Lemma 2 there is a disjoint sequence of basic open sets hVi : i < k+mi inω2 such thats⌢t′ ∈Q
i<k+mViandψ(α1, . . . , αr, t, A) holds inV[G] for every t∈Q
i<k+mVi. TakeUi=Vk+i fori < m.
Now we prove the Boolean Prime Ideal Theorem inM = HODV[G](A).
Let (B,∨,∧,−,0,1) be a Boolean algebra in M. Then there is f ∈ <ωA such thatB∈ODV[G][A, f]. The class ODV[G][A, f] has a well-ordering ordinal- definable fromAandf. Using this well-ordering by transfinite recursion we can define a proper idealI⊆B maximal ordinal-definable fromAandf. Hence, for everyx ∈ B which is ordinal-definable from A and f, either x∈ I or −x∈ I.
ClearlyI∈M becauseI⊆B ⊆M. We prove thatI is a prime ideal ofB inM. Suppose thatI is not prime and letk ∈ω be the least natural number such that for someh′ ∈k+1Athere is anx∈ODV[G][A, f⌢h′] such thatx∈B\Iand
−x∈ B\I. Let a′ = h′(k) and h= h′↾k. Then B ∈ODV[G][A, f⌢h] and by minimality ofk it is obvious thata′ ∈/ rng(f)∪rng(h) andI is a maximal ideal of B in ODV[G][A, f⌢h] because I is a prime ideal there. There is a formula ϕ such that
x={u∈V[G] :V[G]ϕ(u, α1, . . . , αn, f⌢h, a′, A)}
for some ordinalsα1, . . . , αn. Sincef⌢h, α1, . . . , αn are fixed throughout the proof we shall denote
d(a) ={u∈V[G] :V[G]ϕ(u, α1, . . . , αn, f⌢h, a, A)}.
Henced(a′)∈B\I and−d(a′)∈B\I. By Corollary 3 there is a basic open set U ⊆ω2 such thata′∈U,U∩rng(f⌢h) =∅, and
(∀a∈U ∩A)−d(a)∈B\I and d(a)∈B\I.
(1)
The ideal ofB generated byI∪ {d(a) :a∈U∩A} is in ODV[G][A, f⌢h] and it coincides withB by maximality ofI. Therefore for some finite setF1′ ⊆U∩Awe haveV
a∈F1′−d(a)∈I. Similarly, if we consider the ideal generated byI∪{−d(a) : a∈U∩A}we obtain a finite set F2′ ⊆U∩Asuch that V
a∈F2′d(a)∈I. Denote F′=F1′∪F2′ andm=|F′|. Then
V
a∈F′−d(a)∈I and V
a∈F′d(a)∈I.
By Corollary 3, there is a sequence of basic open sets hUi : i < midistinguish- ingF′, such that each setUi is a subset ofU (this is possible becauseF′ ⊆U),
546 Repick´y M.
hence disjoint from rng(f⌢h), and for every F ∈ [A]m such that (∀i < m) F∩Ui 6=∅,
V
a∈F−d(a)∈I and V
a∈Fd(a)∈I.
(2)
For everyi < m, (1) holds withU replaced with Ui becauseUi⊆U. Replacing U with Ui in the argument that leads to (2) we obtain a sequence of pairwise disjoint basic open setshUi,j:j < miiwhich are subsets ofUisuch that for every i < m, and for everyF⊆A∩U with (∀j < mi)F∩Ui,j6=∅, we have
V
a∈F−d(a)∈I and V
a∈Fd(a)∈I.
(3)
The systemS={Ui,j:i < mand j < mi} is a pairwise disjoint system of basic clopen sets inω2 andA is a dense subset ofω2. Lety⊆A∩U be a finite set of the size|S|such that (∀V ∈S)|y∩V|= 1. Then for everyz⊆y,
V
a∈zd(a)∧V
a∈y\z−d(a)∈I.
(4)
To prove this let us consider these two possibilities.
(i) For everyi < m,z∩Ui6=∅. Then by (2),V
a∈zd(a)∈Iand hence (4) holds.
(ii) There is i < m such thatz∩Ui =∅. Then (∀j < mi) (y\z)∩Ui,j 6=∅, and by (3),V
a∈y\z−d(a)∈I, and hence (4) holds.
Using (4) we obtain a contradiction as follows: 1 = V
a∈y(d(a)∨ −d(a)) = W
z⊆y[V
a∈zd(a)∧V
a∈y\z−d(a)]∈I. This contradiction proves thatI is prime inM.
References
[1] Halpern J.D., L¨auchli H.,A partition theorem, Trans. Amer. Math. Soc.124(1966), 360–
367.
[2] Halpern J.D., L´evy A., The Boolean Prime Ideal Theorem does not imply the Axiom of Choice, In: Axiomatic Set Theory, Proceedings of Symposia in Pure Mathematics, vol. XIII, Part I, pp. 83–134, AMS, Providence, 1971.
[3] Jech T.,Set Theory, Academic Press, New York-London, 1978.
[4] Jech T.,Set Theory, the third millennium edition, revised and expanded, Springer Mono- graphs in Mathematics, Springer, Berlin, 2003.
Mathematical Institute, Slovak Academy of Sciences, Greˇs´akova 6, 040 01 Koˇsice, Slovak Republic
E-mail: [email protected]
(Received December 3, 2014, revised April 16, 2015)
