## Are there any non-linear solutions of Cauchy’s equation ($f(x+y)=f(x)+f(y)$) without assuming the Axiom of Choice?

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be s.t. $f(x+y) = f(x) + f(y), \ \forall x, y$

It is quite obvious that this implies $f(cx)=cx$ for all $c \in \mathbb{Z}$ and even further: $\forall c \in \mathbb{Q}$

It is also known that using an infinite dimensional basis for $\mathbb{R}$ over $\mathbb{Q}$, it is possible using the Axiom of Choice to construct a function which is not linear.

My question is whether there exists a known solution not invoking the Axiom of Choice?

Edit: My questions are:

1. Is it not possible to find an explicit expression for a non-linear solution? Why?

2. Can existence of non-linear solutions be proven from ZF alone?

Reference: Cauchy's functional equation

-
All Lebesgue measurable solutions are linear, so there are no nonlinear solutions if you assume the Axiom of Determinacy (en.wikipedia.org/wiki/Axiom_of_determinacy). – George Lowther Mar 5 2011 at 1:53
Ignas- This question isn't well-defined; are you asking if you can prove the existence of such solutions just ZF? (George shows the answer is no). If you want to edit the question to be clearer, and try posting on meta, you might convince people to reopen it. – Ben Webster Mar 5 2011 at 4:03
Thank you for the comments. Yes, I probably should have been more clear, I actually wanted to ask whether: 1) it is possible to find an explicit expression for such a non-linear function (obvious answer: no, but I was interested in how to prove it isn't possible); 2) existence of solutions in ZF. – Ignas Mar 5 2011 at 18:58
@Ignas: Your edited version is interesting! I have voted to re-open. – Andres Caicedo Mar 5 2011 at 22:34

Ignas:

It is not possible to provide an explicit expression for a non-linear solution. The reason is that (it is a folklore result that) an additive $f:{\mathbb R}\to{\mathbb R}$ is linear iff it is measurable.

(This result can be found in a variety of places, it is a standard exercise in measure theory books. As of this writing, there is a short proof here.)

The point is that it is consistent that every set of reals is measurable, and therefore every function $f:{\mathbb R}\to{\mathbb R}$ is measurable.

The first to realize that it is possible using choice to construct a non-linear additive function was Hamel in 1905 ("Eine Basis aller Zahlen und die unstetigen Losungen der Functionalgleichung: $f(x+y)=f(x)+f(y)$", Math Ann 60 459-462); indeed, a Hamel basis of ${\mathbb R}$ over ${\mathbb Q}$ allows us to provide examples. Note that with a Hamel basis it is straightforward to build Vitali's standard example of a non-measurable set.

Solovay ("A model of set-theory in which every set of reals is Lebesgue measurable", Annals of Mathematics. Second Series (1970) 92 1–56) proved that, relative to the consistency of an inaccessible cardinal, via forcing we can prove that it is consistent with ZF + DC that all sets of reals are Lebesgue measurable (DC is the axiom of dependent choice, a weak version of the axiom of choice useful to develop the basic theory of analysis). It follows that, in Solovay's model, all additive functions are linear and therefore no "explicit" example is possible.

The other standard approach to models where all sets of reals are measurable is via determinacy. However, this requires a stronger commitment in terms of consistency strength (using $\omega$ Woodin cardinals we can force an inner model of determinacy). The two approaches are closely related: Assuming enough large cardinals, the inner model $L({\mathbb R})$ consisting of all sets constructible from reals is a model of determinacy, and a Solovay model. Note that this is a theorem (from enough large cardinals) rather than a consistency result, i.e., $L({\mathbb R})$ is a model of these statements, without needing to pass to a forcing extension.

Solovay's result does require an inaccessible cardinal, this is a result of Shelah ("Can you take Solovay's inaccessible away?", Israel Journal of Mathematics (1984) 48 1–47). This leaves the question of whether (the consistency of) ZF suffices to produce a model where all additive maps are linear. But this is now easily solved: In the same paper, Shelah proved that it is relatively consistent with ZF that all sets of reals have the property of Baire. The standard proofs that additivity and measurability give linearity work with "Baire measurability" instead of Lebesgue measurability.

Let me close, however, by pointing out that, in appropriate models of set theory, we can "explicitly" build additive, non-linear maps. More precisely, in nice inner models, we have explicitly definable well-orderings of the reals, from which such maps can be built. For example, in Gödel's inner model L of constructible sets, there is an easily definable Hamel basis (see this MO question), from which we can easily define such a function. "Easily" is formalized in terms of the projective hierarchy. The Hamel basis we obtain is $\Pi^1_1$ and the function is $\Sigma^1_2$.

(By the way, the statement "there is a discontinuous additive function" is form 366 in Howard-Rubin "Consequences of the axiom of choice". The highly recommended companion website does not reveal any additional choice-like implications regarding this form. In particular, it only mentions Solovay's model for its negation, but not Shelah's.)

-
(The existence of a Hamel basis is not exactly what's needed to construct the Vitali set.) – François G. Dorais Mar 6 2011 at 12:16
@François: Thanks. I edited the line in question. – Andres Caicedo Mar 6 2011 at 16:26
wow, thank you for a long and detailed answer, now I feel it was much worth it to request a re-open! – Ignas Mar 6 2011 at 20:35