Can the set of positive reals be partitioned into two nonempty sets, both of which are closed under addition?

The set of positive reals can be partitioned into two nonempty sets, both of
which are closed under addition.

Let R+ denote the semigroup of positive reals under addition.

Consider the family F whose members are ordered pairs <A,B> of non-empty
disjoint subsemigroups of R+. Partially order F by :
     <A,B> < <C,D> iff A is a subset of C and B is a subset of D.
It is straightforward to check that F satisfies the hypothesis of Zorn's
lemma (that is, F is non-empty, and any linearly ordered subset of F
has an upper bound in F), hence F contains a maximal member <P,Q>.

Claim: P and Q are "divisible" ; that is, if x is in P and n is a
positive integer, then x/n is in P; similarly for Q.
For let P# = { t in R+ : nt is in P for some pos. integer n}.
Define Q# analogously.  Then P# and Q# are subsemigroups of R+ which
include P, Q respectively.
      Now note that P# and Q# are disjoint.  For if t were in their
intersection, so that mt .in. P and nt .in. Q for some integers m,n,
we would get mnt in both P and Q.  This is not possible, for P and
Q are disjoint.
      Therefore <P#,Q#> belongs to F. By maximality of <P,Q> in F,
we must have P# = P and Q# = Q.

Next, suppose that P .union. Q is not all of R+.  Choose c in R+ not belonging
to P or Q.  Let P* be the smallest semigroup containing
P and c; then
    P* = { nc + x : n = positive integer, x in P}.
Then, since P* properly includes P, maximality of the pair <P,Q> in F
implies that the intersection of P* and Q is non-empty.
Thus there exists a  positive integer n, and x in P, y in Q,
such that

        nc + x =  y

Dividing by n, and using the fact that x/n = X is in P, and y/n = Y is in Q,
we get

         c = Y - X,   where Y is some member of Q and X is some member of P.

Interchanging the roles of P and Q, we get by the same reasoning that

         c = X' - Y'   where X' is in P and Y' is in Q.

Thus Y - X = X' - Y', so that X + X' = Y + Y'.
But this is impossible, because P and Q are disjoint.

Conclusion:  P .union. Q = R+

Question:  Is there an "explicit" example of such a pair P, Q, or
is the use of some version of the Axiom of Choice necessary to
get existence?

-- Paul R. Chernoff <chernoff@cartan.berkeley.edu>

It depends on what is called easy.  If the sets are measurable, the answer is
false, as the sum of a set of positive measure and itself contains an interval,
so one of the sets must contain all sufficiently large reals.  However, given
any Hamel basis, there must be a coordinate which takes on both signs.  This
gives the desired decomposition.

-- Herman Rubin <hrubin@l.cc.purdue.edu>

I don't know if you consider Axiom of Choice to be easy; if so, then
the reals can be constructed as a vector space over the rationals;
choose a Hamel basis for the reals over the rationals.  Divide the
uncountable basis into two nonempty sets, let A be the rational span of
the first set, and B the span of the second set.  Every real x can be
written uniquely as a sum x = pa+qb with a in A and b in B and p, q
rational.  The reals divide into two sets Ra, Rb with a rule which puts
x in Ra if (p < q) or (p = q and a < b)
x in Rb if (p > q) or (p = q and a > b)
(a = b never happens)

Closure under addition inheres from the property of vector spaces.
When Ra, Rb are intersected with the positive reals, each is clearly
a cone (exercise for the reader) and so is closed under addition.

-- Kevin McCarty <Kevin_P_McCarty@cup.portal.com>

The proof given works very nicely.  If you take for granted that every
vector space has a basis--which is also just a Zorn's lemma argument (and
by the way is even equivalent to it, as was proved in the summer of 1983)--
then you can give a really quick proof that the partition exists:

      R  is a  c-dimensional vector space over the rational field  Q; let
B = {b_r | r  in  R}  be any basis (with elements indexed by real numbers).
Then each real number is uniquely expressible as  SUM [q_r b_r]  for cer-
                                                (r in R)
tain rationals  q_r, of which all but finitely many equal 0.  Then we let
P = {t > 0 | in the unique expression for  t,  q_0 >= 0}  and  Q = the
complement of  P  in  R+.  The uniqueness of the expressions in terms of
the fixed basis  B  and the simple additive way of getting the expression
of the sum of two reals then yield immediately that  P  and  Q  are each
closed under addition.

Chernoff wanted to know whether an "explicit" example exists.  Alas, there
is no such animal (which might make this problem not really suitable for
high school students, though it is stimulating to think about).  Here is
the reason, assuming a knowledge of the basics of Lebesgue measure:  since
P .union. Q  is all of  R+, they can't both have measure 0.  Thus  P  (say)
either has positive measure or is non-measurable.  Assume it has positive
measure.  There's a standard result, proved using the Lebesgue density
theorem, saying that if  m(A) > 0  then  A + A = {a + a' | a,a' in  A} must
contain some nonempty interval.  Hence  P + P, which is a subset of  P,
must contain some interval  I;  P  therefore contains all the intervals
2I, 3I, 4I, ...  (where  nI = {i_1 + ... + i_n | all i_j  in  I}).  It's an
easy exercise to show that eventually these intervals overlap and that  P
contains ALL sufficiently large reals.  This is impossible since  Q, which
is  P's  complement, must also be unbounded.  The conclusion is that  P
must be non-measurable after all.  But by famous model-theoretic results of
Solovay and Shelah, you can't prove the existence of a non-measurable set
in ZF alone:  some amount of choice in necessary.

[ Editor: unsigned in the collected material; David Libert's article
below credits these points to Richard Duffy, article <9429@eddie.MIT.EDU>. ]

  In article  <795@l.cc.purdue.edu>  Herman Rubin  noted such sets can be
easily constructed from a Hamel basis but also that any P and Q as desired
must be non-Lebesgue measurable. (A Hamel basis is a basis for the reals R
considered as a vector space over the rationals Q as the field of scalars.)

  In article  <9429@eddie.MIT.EDU>  Richard Duffy  noted these last two facts
and also observed that theorems of Solovay and Shelah show that ZF does not
prove the existence of a non-Lebesgue measurable set and hence does not settle
the partition question.

  I will discuss another proof which gets this same independence result from
weaker premises. I will also discuss other independence results related to the
details of the Hamel basis proof. I won't attempt to write the details of the
proofs but will give some indication of the techniques used. I will defer this
discussion until after all results have been stated.

  The Solovay and Shelah work involves inaccessible cardinals which are higher
infinities than those of conventional mathematics and cannot be proven to
exist or to even be consistent using only ZFC unless ZFC is inconsistent. See
Frank Drake _Set Theory: An Introduction to Large Cardinals_.

   For  I       -  there exists an inaccessible cardinal
        LM      -  every set of reals is Lebesgue measurable
        AC-C    -  countable axiom of choice: allows countably many choices
        T |- A  -  the theory T proves the statement A
        Con (T) -  theory T is consistent

the Solovay and Shelah theorems together show:

  ZFC |-  [ Con(ZFC + I)  <->  Con(ZF + AC-C + LM) ].
             ( ->  Solovay ,  <-  Shelah)

(In fact the full statement of each of the theorems involves further
technicalities but the displayed equivalence is a consequence of the
theorems.)

  The Solovay -> proof together with Richard Duffy's article shows

  for    P   -   there is a partitioning of the positive reals R+ into two
                 sets P1 and P2 each closed under +

  (*)    ZFC |-  [ Con(ZFC + I) -> Con(ZF + ~P) ].

  By a different method

  (**)   ZFC |-  [ Con(ZFC) -> Con(ZF + ~P) ].

  The previously cited proof of (*) got ~P by getting AC-C + LM. If such a
proof were possible for (**) then

  ZFC |-  [ Con(ZFC) ->  Con(ZF + AC-C + LM) ].

Then by Shelah's <- cited above

  ZFC |-  [ Con(ZFC) ->  Con(ZFC + I) ].

But ZFC + I |-  Con(ZFC). From these two facts and Godel's second
incompleteness theorem applied to ZFC + Con(ZFC) it would follow that
ZFC + Con(ZFC) is inconsistent. So (**) is significantly stronger than (*) and
requires a different method of proof.

  The cited proofs of P from a Hamel basis used the Hamel basis to induce a
Q-linear map  f: R -> Q which is nontrivial in the sense that its kernel is
neither {0} nor R. (R is the set of all real numbers and Q is the set of all
rational numbers, here both considered as Q-vector spaces.) More generally
given any similarly nontrivial Q-linear map g: R -> R we can induce a P
partition by taking the g pre-images of the non-negative and negative reals
respectively.

  A Hamel basis may be produced by a Zorn's lemma argument. To make a finer
analysis we can alternatively use Zorn's lemma to produce a well-ordering of
R. The well-ordering allows construction of a Hamel basis by a transfinite
recursion in length the well-ordering using the well-ordering to make choices
along the way.

  It follows that for
        AC    -          axiom of choice
        WO(R) -   there is a well-ordering of R
        HB    -          there exists a Hamel basis of R over Q
        MQ    -          there is a nontrivial (as above) Q-linear map R -> Q
        MR    -          there is a nontrivial Q-linear map R -> R

  ZF proves the chain of implications  AC -> WO(R) -> HB -> MQ -> MR -> P.

  If ZF is consistent then none of the implications in the chain can be
reversed in ZF. More exactly,

    (***)  if A and B are two statements in the above chain such that B
           occurs strictly to the right of A then

                ZFC |-  [ Con(ZFC) -> Con(ZF + B + ~A) ].

  If A', A and B are three distinct statements appearing in that order in the
chain then if ZF |- (B -> A') then since ZF |- (A' -> A) we would have ZF |-
(B -> A). Taking contrapositives if ZF does not prove (B -> A) then ZF does
not prove (B -> A'). Therefore it suffices to prove (***) for the five cases
of A immediately left of B in the chain.

  All the proofs use  Paul J Cohen's method of symmetric inner models of
forcing extensions of models of ZFC. Some of the proofs also use iterated
forcing. Symmetric models are described in
    Paul Cohen _Set Theory and the Continuum Hypothesis_,
    Thomas Jech  _The Axiom of Choice_    and in   Jech   _Set Theory_.
Iterated forcing is described in  Jech _Set Theory_.

  The proofs of (**) and the P + ~MR case of (***) also depend on a ZF
provable structure theorem characterizing {P1, P2} partitions witnessing P as
uniquely arising from a generalized form of the g construction in MR -> P
above. That g construction is literally a special case of the new
construction and produces a subset of the partitions. The P + ~MR consistency
occurs in models having instances of the general construction but none of the
special g case.

  Cohen's symmetric model method begins with a starting countable ground model
M of ZFC and extends this to N a new model of ZFC by Cohen's method of
forcing. The desired ZF + ~AC model is S which is a submodel intermediate
between M and N. This submodel consists of all sets of N which are suitably
invariant with respect to a group acting on part of the forcing construction
that was used to produce N. Properties of S are determined by the way the
group action and the invariance notion interact with the forcing construction.

  The WO(R) + ~AC result is the easiest. Given a countable model M of ZFC we
can use Cohen methods to produce N a model of ZF + ~AC such that the R and the
power set of the reals P(R) are the same in the two models. (P(R) is the set
of all subsets of R). Since M satisfied AC it satisfies WO(R). Since WO(R)
only refers to R and P(R) it must hold in N. The distinction here between what
is preserved and what is changed depends on cardinality and as such is crude.

  The proofs of (**) and of the remaining four cases of (***) depend on a more
careful analysis of the statements. Each statement in the chain asserts the
existence of a particular structure, in the case of P I use those appearing in
the structure theorem instead of the original partition. Each of the five
desired models is produced by choosing the group action so that invariant
structures of the desired statement exist but all structures witnessing the
statement to be negated are not invariant. The invariance notion I use the
simplest one for such arguments: finite support. The forcings used always add
Cohen reals in various combinations of finite support countable product and
finite support countable iteration. In some cases redundancies are introduced
in the forcing which have no effect on the largest model N but which make the
forcing more homogeneous to allow the group action. The key to the proofs is
analyzing the structures in the respective statements and making a group
action with the desired effect. The forcing is chosen to allow defining such a
suitable group action.

-- David Libert <libert@math.berkeley.edu>

This is pretty trivial if you apply the Axiom of Choice correctly.  I know
of no Choice-free proof.

Proof:

Let R be the set of real numbers, let R+ be the set of positive reals, and let
Q be the field of rationals.  Consider R as a vector space over Q in the
natural way (vector addition and scalar multiplication are regular addition and
multiplication of reals, respectively).  It is a consequence of the Axiom of
Choice that every vector space has a basis.  Let B be a basis of R over Q.
Each real number r can be uniquely expressed as a finite linear combination of
members of B with rational coefficients.  If b is any basis element, the coef-
ficient of b in the expansion of r is called the "b'th coordinate of r."

Fix a basis element b in B.  Let

        A  =  { r in R+ | the b'th coordinate of r is positive },

and let

        B  =  { r in R+ | the b'th coordinate of r is zero or negative }.

A and B clearly partition R+, and are nonempty, since given any q in Q, we can
find a positive number with b'th coordinate q by adding to qb any appropriately
large multiple of another (linearly independent) basis element in B.

A and B are also both closed under addition, since addition is coordinatewise.

                                                                          QED

One can extend this result and partition R+ into any cardinality (up to |R|)
of nonempty, addition-closed sets by taking several basis vectors into account
at once, setting different sign constraints on their coefficients.

I'll leave this as an exercise (you don't need the Continuum Hypothesis).

-- Steve Fenner <steve@gargoyle.uchicago.edu>

One cannot prove without the Axiom of Choice that the positive real
numbers can be partitioned into two nonempty sets A and B each of
which is closed under addition.  To see this, we will show that,
in any such partition, the sets A and B cannot be Lebesgue
measurable and cannot have the property of Baire (i.e., differ from
some open set by a set of first category); since there are models
of ZF (set theory without the Axiom of Choice) in which all sets
of reals are Lebesgue measurable and have the property of Baire,
one must use the Axiom of Choice to get such a partition.

So suppose we have such a partition into Lebesgue measurable sets
A and B (the proof for the property of Baire is similar).  At least
one of the sets (we may assume A) must have positive measure.  Then
there must be an interval I such that more than 3/4 of I is in A.
Let x be the center of I, and let J be the interval of the same
length with center 2x.  For any y in J, the intervals I and y-I
overlap in an interval of length at least half that of I; the sets
(I intersect A) and y-(I intersect A) each contain more than half
of this overlap interval, so they must have a point z in common.
Then z and y-z are in A, so y is in A.

Now, since J is contained in A, the intervals 2J, 3J, ... are all
contained in A.  For sufficiently large n, nJ and (n+1)J overlap,
so A contains all sufficiently large real numbers.  Since B is
closed under addition, A is closed under division by 2, so A
contains all positive real numbers, contradiction.

Similarly, one cannot get partitions as above into 3, 4, ..., or
countably infinitely many pieces without using the Axiom of Choice.
By a somewhat more involved proof, one can show the following:
in the models of set theory mentioned above, if S is a partition
of the positive reals into nonempty disjoint sets each of which is
closed under addition, then either S has cardinality 1 (the trivial
partition into 1 piece) or S cannot be linearly ordered.  This
includes the preceding result and also rules out the possibility
of S having the same cardinality as R.  (Of course, one can always
partition the positive reals by putting x and y in the same set
if and only if x/y is rational, and the resulting sets will all
be closed under addition; the preceding result says that, without
the Axiom of Choice, one cannot show that the number of sets one
ends up with is |R|.  In fact, in the models mentioned above,
the number of sets in this partition is actually greater than |R|!
This shows how strange cardinal arithmetic can be without the
Axiom of Choice.)

-- Randall Dougherty <rand@lanl.gov>

[ Editor: Timothy Chow's proposed construction and David Libert's
analysis of it. ]

Let P be the proposition: there is a partitioning of the positive reals
R+ into two nonempty sets A and B each closed under +.

In article <2095@pt.cs.cmu.edu>, tycchow@vi (Timothy Chow) writes:
>
>OK, I think I've got it now.
>
>"The set of positive reals can be partitioned into two
>sets, each of which is closed under addition."
>
>My last attempt was
>
>A = {rationals} U {numbers of form a+bx}
>B = {positive numbers of form a-bx}
>
>which, as has been pointed out, is wrong.  But how about this?
>
>1. Forget the restriction "positive" for the moment.
>2. Define the "positive span" of an irrational number x as the
>set of all numbers of the form a+bx and define the "negative
>span" of x as the set of all numbers of the form a-bx (where
>a,b are rational and b>0).  Define the span of x as the union
>of its positive and negative spans (which are clearly disjoint).
>3. Given two irrationals x and y, exactly one of the following
>holds:
>   a. Their spans are disjoint.
>   b. The positive span of x equals the positive span of y and
>      the negative span of x equals the negative span of y.
>   c. The positive span of x equals the negative span of y and
>      vice versa.
>4. So we can partition the irrationals into disjoint spans.
>   For each span we choose exactly one member to be the
>   "representative."
>5. For each representative, we put its positive span into set
>   A and its negative span into set B.
>6. Now we delete all negative numbers.
>7. Throw the positive rationals into one of the sets.
>8. Construction complete: A and B are the required sets.
>
>T. Chow

  There are many ways to produce sets A and B in agreement with the
preceding description, according to the various choices made in the
construction. I will prove that some of these instances satisfy P and
others do not. The not P examples show that the claim that A, B
produced above satisfy P has not been proven. My examples in which the
construction above produces P require extra work.

  I will also give an example of an A, B satisfying P which cannot be
produced by any instance of the above construction. This has no bearing
on the correctness of the above proof, but it gives further information
on the relation of the construction above to P.

  All three of my examples are constructed using AC (the axiom of
choice).  Since T. Chow's construction uses the AC to pick
representatives it is reasonable that I also need it to give examples
of the construction.  Also my last example implies P. In article
<10981@agate.BERKELEY.EDU> Partitioning the semigroup R+ I noted that if
ZF is consistent then ZF does not prove P.  Therefore it is reasonable
that I assume the AC in constructing this example.

  Note that in discussing T. Chow's proof I am myself proving P,
assuming AC.  Articles proving AC -> P were previously posted by Paul
Chernoff, Herman Rubin, Richard Duffy and myself:
<10634@agate.BERKELEY.EDU> <795@l.cc.purdue.edu> <9429@eddie.MIT.EDU>
and <10981@agate.BERKELEY.EDU>.

  A Hamel basis is a basis of the reals viewed as a vector space over
the rationals Q as field of scalars. We can use AC in a Zorn's lemma
argument to construct H a Hamel basis consisting entirely of positive
real numbers and containing as element the real number 1. Let h1 and h2
be two distinct elements of H both != 1. Let a be a rational number >
h1 + h2. Then h1, h2 and a - (h1 + h2) are each positive, irrational and
have pairwise disjoint spans.  (The proofs of the last two of these
claims use that 1, h1 and h2 are distinct elements of H and the
uniqueness of basis representation). Do T. Chow's construction above
subject only to the restriction that h1, h2 and a - (h1 + h2) are
chosen as the respective representatives of their spans.  So h1 and h2
are both in A. But h1 + h2 = (-a) - (a - (h1 + h2)) is in B.  So the A
produced by this instance of the construction is not closed under +.

[ Editor: h1 + h2 = a - (a - (h1 + h2)); as written, (-a) - (a - (h1 +
h2)) = h1 + h2 - 2a.  Either way h1 + h2 lies in the negative span of
a - (h1 + h2), so the conclusion stands. ]

  Next an example of the construction which does give P. Take H as
above. For r a real number let q(r) be the coefficient of the basis
element 1 in the unique Q-linear combination of H equal to r. Note that
q(-r) = -q(r). So if we define h(r) = r - q(r) then h(-r) = -h(r). Also
q(r) is always rational (since it comes from the field of scalars) so
if r is irrational then h(r) != 0.  Given any span containing some
irrational element r, the span also contains -r. If h(r) is not
positive then h(-r) is positive by the preceding remarks.  Hence any
span containing irrational elements contains elements making h
positive. So do T. Chow's construction subject only to the constraint
that each irrational span representative is chosen to make h positive.
Then I claim the resulting A and B satisfy P. To see this note that q
is Q-linear (coefficient of sum is sum of coefficients etc). So h is
Q-linear. Also h is 0 on rational numbers. So if a + b*r is in the span
of r (a, b both rational) then h(a + b*r) = b*h(r). We chose
representatives r so that h(r) is positive. So h is positive on all
positive spans of irrationals and negative on all the negative spans.
So for r irrational r in A <-> h(r) > 0 and r in B <-> h(r) < 0. So no
counterexample of the + closure of A or B is possible using two
irrational numbers adding to an irrational. Also if two irrational
numbers add to a rational one they are in opposite sides of the same
span, hence one is in A and the other in B so again no counterexample
is possible. Addition of a rational number to an irrational stays on
the same side of the span by definition of span, so this can also make
no counterexamples. Two rational numbers adding cannot make a
counterexample because all rationals were thrown into A or B together
in step 7 of T. Chow's construction. This covers all cases so P is
satisfied.

  Finally an example of an A and B satisfying P which cannot be
produced by any instance of T. Chow's construction. Let H and q be as
above Let A = {r | q(r) >= 0}, B = {r | q(r) < 0}. By the Q-linearity
of q this satisfies P.  (This is essentially the example first written
by Herman Rubin and Richard Duffy). Then for h1 in H and != 1 and for b
a rational number > 1/h1 we have 1 + b*h1 and -1 + b*h1 are both
positive and are in A and B respectively. But these two numbers are
irrational and their difference is 2 a rational number.  T. Chow's
construction always assigns such pairs to the same partition set.

-- David Libert <libert@math.berkeley.edu>