The axiom of choice and two-point sets in the plane

Arnold W. Miller ^{1}

Abstract

In this paper we prove that it consistent to have a two-point set in a model of ZF in which the real line cannot be well-ordered. We prove two results related to a construction of Chad of a two-point set inside the countable union of concentric circles. We show that if the reals are the countable union of countable sets, then every well-orderable set of reals is countable. However, it is consistent to have a model of ZF in which the reals are the ω_{1} increasing union of sets of size ω_{1} and ω_{2} can be embedded into the reals.

A two-point set is a subset of the plane which meets every line in exactly two points. It is an open question whether a two-point set can be Borel. In work on the two-point problem Chad [1] came up with the question of whether it might be possible to have a model of ZF in which the reals are the countable union of countable sets and there is an uncountable well-orderable set of reals.^{2} If this were possible, then Chad’s method of construction of two-point sets inside concentric circles could be used to construct a Borel example of a two-point set.

However, it is impossible:

Theorem 1 Suppose the reals are the countable union of countable sets. Then every well-orderable set of reals is countable.

Proof

Let p : ω × ω → ω be a fixed bijection. For each n ∈ ω define the map π_{n} : 2^{ω} → 2^{ω} by:

π_{n}(x) = y iff ∀m ∈ ω y(m) = x(p(n, m)).

1

Mathematics Subject Classification 2000: 03E25 03E15

Keywords: countable axiom of choice

2In the first draft of [1] it was stated that we had shown that in the Feferman-Levy model there is no uncountable well-orderable set of reals. But this is already known, see Cohen [2] page 146.

Suppose there exists (F_{n} : n ∈ ω) such that 2^{ω} = ⋃_{n∈ω} F_{n} and each F_{n} is countable. Define (H_{n} : n ∈ ω) by

H_{n} = π_{n}(F_{n}) = {π_{n}(x) : x ∈ F_{n}}.

Since the image of a countable set is countable each H_{n} is countable.

Suppose for contradiction that there exists (u_{α} : α ∈ ω_{1}) distinct elements of 2^{ω}. Then for all n there exists α ∈ ω_{1} such that u_{α} ∉ H_{n}. Define (α_{n} : n ∈ ω) by

α_{n} = the least α such that u_{α} ∉ H_{n}.

Let x ∈ 2^{ω} be the unique real such that

∀n π_{n}(x) = u_{α_{n}}.

But this is a contradiction since then x ∉ ⋃_{n∈ω} F_{n}. QED

The following answers a question raised by Chad.

Theorem 2 It is consistent to have a model of ZF in which ω_{2} embeds into the real line and the real line is the ω_{1} increasing union of sets of size ω_{1}.

Proof

Before doing this we prove the following lemma. Our model is analogous to the Feferman-Levy model (see Cohen [2] p.143, Jech [3] p.142) but one cardinal higher.

Lemma 3 There is a countable transitive model N of:

1. ZF + DC + CH (i.e, |2^{ω}| = ω_{1}, there is bijection between 2^{ω} and ω_{1}),

2. the power set of ω_{1} is the ω_{1}-union of sets of size ω_{1},

3. cof(ω_{2}) = ω_{1}, and

4. |[ω_{2}]^{ω}| = ω_{2}.

Proof Let be M be a countable transitive model of ZFC+GCH. Working in M let κ = (ℵ_{ω_{2}})^{M}. Define ℙ to be the standard Levy collapse of κ to ω_{1} using countable partial functions. This means p ∈ ℙ iff there is a countable F ⊆ ω_{1} × ω_{1}, such that p : F → κ and p(α, β) < ℵ_{α} for every (α, β) ∈ F. For G which is ℙ-generic over M define (g_{α} : α < ω_{1}) by g_{α}(β) = γ iff there exists p ∈ G such that p(α, β) = γ. Standard density arguments show that each g_{α} : ω_{1} → ℵ_{α} is onto.

Consider any permutation π̂ : ω_{1} × ω_{1} → ω_{1} × ω_{1} which fixes the first coordinate, i.e., π̂(α, β) = (α′, β′) implies α = α′. Such a permutation induces an automorphism π of ℙ by defining:

1. dom(π(p)) = π̂(dom(p)) and

2. π(p)(π̂(α, β)) = p(α, β)

Working in M, the group G of permutations are those π such that π̂ has countable support, i.e.,

supp(π̂) = {(α, β) : π̂(α, β) ≠ (α, β)}

is countable. Let {H_{α} : α < ω_{1}} generate the filter F of subgroups of G where

H_{α} = {π ∈ G : π̂ ↾ α × α is the identity }.

It is easily checked that F is normal. Let N be the symmetric model determined by G, F. The forcing is countably closed and the filter of subgroups is closed under countable intersections. It follows that [ω_{2}]^{ω} is the same in all the models M ⊆ N ⊆ M[G]. The rest of the arguments to prove the lemma are analogous to Feferman-Levy and left to the reader. QED

Working in the model N of the lemma consider the usual Cohen forcing order for adding ω_{2} subsets of ω:

Fn(ω_{2}, 2) = {p : dom(p) ∈ [ω_{2}]^{<ω} and range(p) = {0, 1}

Since Fn(ω_{2}, 2) just consists of finite sequences of ordinals, it is clear that it can be well-ordered in type ω_{2} in any model of ZF (without using the axiom of choice).

The set of canonical names, CN(Fn(ω_{2}, 2)), for subsets of ω is defined to be the set of all countable τ such that τ is a subset of

τ ⊆ Fn(ω_{2}, 2) × {n^{∘} : n ∈ ω}

This set need not be well-orderable in a model of ZF. However, it is easy to see that it always has the same cardinality as the set [ω_{2}]^{ω}.

If we now take N[G] for G which is (Fn(ω_{2}, 2))^{N}-generic over N, then N is the model we want and Theorem 2 is proved. QED

Remark 4 Note that in the model for Theorem 2 DC (Dependent Choice) holds and there is a bijection between ω_{2} and the real line. So in fact, the usual inductive construction of a two-point set could be done.

In response to a question of Chad we show:

Theorem 5 It is consistent to have a model of ZF in which there is a twopoint set but the real line cannot be well-ordered.

Proof

Here is a sketch of the proof. Start with M a countable transitive model of ZF such that there exists an infinite Dedekind-finite set of reals and ω_{1} is regular. For example, the standard Cohen model see Jech [3] page 61. Working in M let Fn(ω_{1}, 2) be the usual poset for adding ω_{1} Cohen reals, i.e. p in Fn(ω_{1}, 2) is a finite partial function from ω_{1} to 2. The model we want is M[G] for any G which is Fn(ω_{1}, 2)-generic over M.

Since Fn(ω_{1}, 2) can be well-ordered in M it is not hard to see that forcing with Fn(ω_{1}, 2) will preserve Dedekind finite sets (Lemma 7). Hence the reals of M[G] cannot be well-ordered. Also since ω_{1} is regular in M for x a real in M[G] there exists an α < ω_{1} such that x is in M[G_{α}] (Lemma 8).

Then using the α^{th} Cohen real to determine the radius of a circle centered at the origin we can inductively construct a 2-point set in M[G].

We give this last argument in more detail:

Suppose N is a countable transitive model of ZF. Suppose that X ∈ N is a partial two-point set, i.e., X is a subset of the plane which does not contain three collinear points.

Fix n ∈ ω.

Working in N define L_{n} to be the set of all lines which meet the circle of radius n + 1 centered at the origin.

Suppose that x ∈ 2^{ω} is 2^{<ω}-generic over N and define

r(n, x) = (n + 1) + ∑_{k<ω} x(k)2^{−k−1}.

Let C be the circle of radius r(n, x) centered at the origin. For each line L in L_{n} since the radius of C is greater than n + 1, the line L will meet it in two distinct points. Let L ∩ C = {p^{L}, q^{L}} where p^{L} is lexicographically less than q^{L}. Define F (L) as follows:

F (L) = \{ \begin{matrix}∅ & if |L ∩ X| = 2 \\ \{p^{L}\} & if |L ∩ X| = 1 \\ \{p^{L}, q^{L}\} & if |L ∩ X| = 0 \end{matrix}

Define

Y = X ∪ ⋃{F (L) : L ∈ L_{n}}.

It is easy to see by the genericity of its radius that the circle C cannot contain any point of N. It follows that for any L ∈ L_{n} that |L ∩ Y | = 2.

Now we verify that Y does not contain three distinct collinear points. Suppose a, b, c ∈ Y are collinear. It cannot be that all three are from X since the set X is a partial two-point set. It cannot be that all three are new, i.e., from Y \ X since all of these points are on the same circle, C. It cannot be that two are old and one is new, say a, b ∈ X and c ∈ Y \ X. This means that c ∈ F (L) for some L ∈ L_{n}. But by the definition of F (L) it cannot be that L is the line L′ containing a and b. But then L′ and L are distinct lines in N meeting at the point c, which contradicts the fact that the radius C is not in N.

So finally we are left with the case of one old and two new points, i.e., a ∈ X and b, c ∈ Y \ X. Say b ∈ F (L) and c ∈ F (L′). It is impossible that L = L′ by the way we defined F. According to Lemma 4.1 of [1] for distinct lines L, L′ and point a there are at most 22 radii r > 0 such that if C_{r} is the circle of radius r centered at the origin, then there exists b ∈ C_{r} ∩ L and c ∈ C_{r} ∩ L′ such that a, b, c are collinear. These radii are the solutions of polynomial equations and hence would lie in N. Again by genericity this cannot happen.

This is the construction at each step. We now describe the transfinite construction.

Definition 6 For any ordinal α define

Fn(α, 2) = {p : D → 2 : D ∈ [α]^{<ω}}

ordered in the usual way by inclusion, p ≤ q iff p ⊇ q. For any G_{α} which is a Fn(α, 2)-filter and β < α define

G_{β} = G_{α} ∩ Fn(β, 2)

and define x_{β} ∈ 2^{ω} by

x_{β}(n) = i iff ∃q ∈ G_{α} q(β + n) = i.

Standard iteration arguments show that for limit ordinals β < α in a countable transitive model M of ZF if G_{α} is ℙ_{α} generic over M, then G_{β} is ℙ_{β}-generic over M and x_{β} is 2^{<ω} generic over M[G_{β}].

For each β < ω_{1}^{M} if β = λ + n where λ is a limit ordinal, let C_{β} be the circle of radius r(n, x_{β}) centered at the origin. Note that the sequence (x_{β} : β < ω_{1}^{M}) is in the model M[G_{ω_{1}^{M}}]. Hence working in this model we may construct inductively without using choice an increasing sequence of partial two-point sets (X_{β} : β < ω_{1}^{M}) using the argument we described above at each successor step. Since every line will appear at some countable stage (by Lemma 8) the set X = ⋃_{α<ω_{1}^{M}} X_{α} will be a two-point set in M[G_{ω_{1}^{M}}]. Since our forcing can be well-ordered the Dedekind finite set in the ground model M is preserved (by Lemma 7) and hence Theorem 5 is proved. QED

Lemma 7 Suppose that M is a countable transitive model of ZF. Suppose that ℙ is a partially ordered set in M such that

M ⊧ ℙ can be well-ordered.

Suppose that D ∈ M satisfies

M ⊧ D ⊆ 2^{ω} is an infinite Dedekind finite set.

Then for any G which ℙ-generic over M:

M[G] ⊧ D is a Dedekind finite set.

Proof Suppose not. Working in M take p ∈ G and f^{∘} a ℙ-name such that

p ⊩ f^{∘}: ω → D is one-one.

For each n < ω let

E_{n} = {q ∈ ℙ : q ≤ p and ∃d ∈ D q ⊩ f^{∘} (n) = ď}.

Define g_{n} : E_{n} → D by g_{n}(q) = d iff q ⊩ f^{∘} (n) = ď. Since E_{n} can be wellordered and D is Dedekind finite, the range R_{n} of the map g_{n} is finite. But since 2^{ω} is a linearly ordered set, it follows that ⋃_{n<ω} R_{n} is a finite set.

But this is contradiction since in M[G] the range of f is a subset of ⋃_{n<ω} R_{n}. QED

Lemma 8 Suppose that M is a countable transitive model of ZF such that

M ⊧ ω_{1} is regular.

Then for any G which is Fn(ω_{1}^{M}, 2)-generic over M

M[G] ∩ 2^{ω} = ⋃_{α<ω_{1}^{M}}(M[G_{α}] ∩ 2^{ω}).

Proof Suppose x ∈ M[G] ∩ 2^{ω}. Working in M let x^{∘} be a name for x and take p ∈ G so that

p ⊩ x^{∘}∈ 2^{ω}.

For each n < ω let

E_{n} = {q ∈ ℙ_{ω_{1}^{M}} : q ≤ p and ∃i ∈ {0, 1} q ⊩ x^{∘} (n) = i}.

Since ℙ_{ω_{1}^{M}} can be well-ordered and the sequence (E_{n} : n < ω) is in M we can (without using choice) find (A_{n} ⊆ E_{n} : n < ω) in M so that each A_{n} is a maximal antichain beneath p. One needs to check that

M ⊧ antichains in Fn(ω_{1}, 2) are countable.

This is true because in M there is bijection between ω_{1}^{M} and Fn(ω_{1}^{M}, 2) and since ω_{1}^{M} is regular in M the countable union of countable subsets of Fn(ω_{1}^{M}, 2) is countable.

Hence there exists α < ω_{1}^{M} such that ⋃_{n<ω} A_{n} ⊆ ℙ_{α}. It follows by standard canonical name arguments that x ∈ M[G_{α}]. QED

Remark 9 The method of proof of Theorem 5 also yields models of ZFC in which the continuum is arbitrarily large and there is a two-point set which is included in the union of ω_{1} circles.

References

[1] Chad, Ben; Knight, Robin; Suabedissen, Rolf; Set-theoretic constructions of two-point sets, eprint aug08

[2] Cohen, Paul J.; Set theory and the continuum hypothesis. W. A. Benjamin, Inc., New York-Amsterdam 1966 vi+154 pp.

[3] Jech, Thomas J.; The axiom of choice. Studies in Logic and the Foundations of Mathematics, Vol. 75. North-Holland Publishing Co., Amsterdam-London; Amercan Elsevier Publishing Co., Inc., New York, 1973. xi+202 pp.

[4] Miller, Arnold W.; Long Borel hierarchies, Math Logic Quarterly, 54(2008), 301-316.

[5] Miller, Arnold W.; A Dedekind finite Borel set, eprint jun08.

Arnold W. Miller miller@math.wisc.edu http://www.math.wisc.edu/∼miller University of Wisconsin-Madison Department of Mathematics, Van Vleck Hall 480 Lincoln Drive Madison, Wisconsin 53706-1388