Functional equations | Absolutely useless

Posted tagged ‘Functional equations’

Cauchy’s functional equation II

December 21, 2010

In this post I will finish what I began in my previous post. I have collected the two posts in a pdf-file, which might be a bit easier to read. Again you are welcome to comment on both math and language.

4: More wild facts about non-linear solutions

A function could have a graph that is dense in the plane, but still be ‘nice’ on a large part of the domain. E.g. there exist functions that are $0$ on all irrational numbers, but still have a graph that is dense in the plane. Inspired by this, here is a list of things that would make a function wild even in a measure theory sense. Again, the list is ordered, and again all these statements are true for any non-linear solution to Cauchy’s functional equation.

$f$ is not measurable. (When I write measurable function and measurable set, I always mean Borel-measurable.)
$|f|$ is not dominated by any measurable function.
If $A$ is measurable set such that $f$ is bounded above on $A$ , then $A$ has measure $0$ .
If $A$ is measurable set such that $f$ is bounded above on $A$ , then $A$ has measure $0$ .
If $B\subset \mathbb{R}$ is open and non-empty and $A\subset \mathbb{R}$ is measurable and $f(A)\cap B= \emptyset$ , then $A$ have measure zero.

I will prove that last one.

Proof: Assume for contradiction that there is a non-linear function $f$ satisfying Cauchy’s functional equation and a non-empty open set $B\subset \mathbb{R}$ and a measurable set $A\subset \mathbb{R}$ with positive measure, and $f(A)\cap B=\emptyset$ . Any open set contains an open interval, so without loss of generality, we can assume that $B$ is an open interval. We assumed that $m(A)>0$ , where $m(X)$ denotes the measure of a set $X\subset \mathbb{R}$ , and since measures are countably additive, there must be an interval of length $1$ with $m(A\cap I)>0$ , so without loss of generality, we assume that $A$ is contained in an interval of length $1$ . To reach a contradiction, I will show that under these assumptions, there exist two sequences of sets, $A_n$ and $B_n$ of subsets of $\mathbb{R}$ satisfying:

Each $A_n$ is a subset of a interval of length $1$ .
$m(A_n)\geq m(A)>0$ for each $n$ .
Each $B_n$ is a open interval.
The length of $B_n$ tends to infinity as $n\to\infty$ .
$f(A_n)\cap B_n=\emptyset$ .

Since $f(A)\cap B = \emptyset$ and $f(nx)=nf(x)$ for $n\in\mathbb{N}$ we have $f(nA)\cap nB = \emptyset$ for $n\in\mathbb{N}$ . We assumed that $A$ is contained in an interval of length $1$ , so $nA$ is contained in an interval of length $n$ . Furthermore, $m(nA)=n\cdot m(A)$ so using the pigeonhole principle we can find an interval $I_n$ of length $1$ such that $m(nA\cap I_n)\geq m(A)$ . We see that $f(nA\cap I_n)\cap nB =\emptyset$ so I choose $A_n=nA\cap I_n$ and $B_n=nB$ .

I will now use the existence of $A_n$ and $B_n$ to reach a contradiction. For each $n$ let $a_n$ be a number such that $A_n\subset [a_n,a_n+1]$ and let $b_n$ and $c_n$ be numbers such that $B_n=(b_n,c_n)$ . We know that the graph of $f$ is dense in the plane, so we can find some $x_n\in (a_n-1,a_n)$ with $\frac{3b_n+c_n}{4}<\frac{b_n+3c_n}{4}$ . Now the sequences $C_n=A_n-x_n$ and $D_n=B_n-f_n$ satisfy the above five requirements for $A_n$ and $B_n$ , and furthermore $C_n\subset [0,2]$ and the lower and upper bound of $D_n$ will tend to minus infinity resp. plus infinity. Now for all $x\in \mathbb{R}$ there is some $N\in \mathbb{N}$ such that $x\in D_n$ for all $n\geq N$ . But $f(C_n)\cap D_n=\emptyset$ , so the sequence of indicator functions $1_{C_n}$ converge pointwise to the $0$ -function. It is dominated by $1_{[0,2]}$ which have integral $2$ , so the dominated convergence theorem tells us that $\int 1_{C_n}=m(C_m)$ tends to $0$ as $n\to\infty$ . But this contradicts $m(C_n)\geq m(A)>0$ . QED.

Assuming the axiom of choice we can find a discontinuous solution to Cauchy’s functional equation, and if we let $B$ in the above be the set of positive real numbers, we see that any measurable set $A$ with

$A\subset \{x|f(x)\leq 0\}$

must have measure $0$ . But similarly, any measurable set $A$ with

$A\subset \mathbb{R}\setminus \{x|f(x)\leq 0\}=\{x|f(x)> 0\}\subset \{x|f(x)\geq 0\}$

must also have measure $0$ . Thus we have found a set, such that neither the set nor its complement contains a set with positive measure.

5: Extra wild functions

We have seen that the graph of a non-linear solution is in many ways ‘spread out all over the plane’. But there are some ways to interpret ‘spread out all over the plane’ for which this is not true for all solutions. E.g. let $(x_i)_{i\in I}, x_i\in \mathbb{R}$ be a Hamel basis. Now the function

$f\left(\sum_{i\in I}q_ix_i\right)=\sum_{i\in I}q_i, \quad q_i\in \mathbb{Q}, |\{i\in I|q_i\neq 0\}|<\infty$

is a solution to Cauchy’s functional equation, but $f(x)$ is always rational. However, there exist surjective solutions, so in some ways, some solution functions are `wilder’ than others. As usual, I will give a list of wild properties a function can have, and as usual the list is ordered such that any of the properties imply the one above. Unlike for the other lists, there are some solution functions that do not satisfy any of the properties and some that satisfy all of them. Moreover, for any two properties on the list, there exist solutions, that satisfy the upper of the two, but not the lower one.

$f$ is surjective.
The graph of $f$ intersects any line in the plane.
For any continuous function $c:\mathbb{R}\to \mathbb{R}$ there is a $x\in \mathbb{R}$ with $f(x)=c(x)$ .
For any continuous function $c:\mathbb{R}\to \mathbb{R}$ the set $\{x\in\mathbb{R}|f(x)=c(x)\}$ is dense in $\mathbb{R}$ .
any continuous function $c:\mathbb{R}\to \mathbb{R}$ , any measurable set $A\subset \mathbb{R}$ with $\{x\in A|f(x)= c(x)\}=\emptyset$ have measure $0$ .

First I will prove that there is a solution $f$ satisfying the third property. The proof of the existence of solutions satisfying the two last properties are similar, and I will sketch those proofs afterwards.

Proof: We begin by choosing a Hamel basis $(x_i)_{i\in I}$ and well-order $I$ . That is, we find an ordering on $I$ such that any subset of $I$ has a least element. The existence of such an ordering (on any set) is equivalent to the axiom of choice. The set $\{x_i|i\in I\}$ is a subset of $\mathbb{R}$ , so the cardinality of this set is not greater than the cardinality of $\mathbb{R}$ . Since $x_i\neq x_j$ for $i\neq j$ we get that $|I|\leq |\mathbb{R}|$ . Assume for contradiction that $|I|<|\mathbb{R}|$ . Using the rules for calculations with cardinality we know that $|I\times \mathbb{Q}|=\max(|I|,|Q|)$ and more generally $|(I\times \mathbb{Q})^n|=\max(|I|,|\mathbb{Q}|,|I|,\dots,|\mathbb{Q}|)=\max(|I|,|\mathbb{Q}|)$ . Since any element in $\mathbb{R}$ is a linear combination of the $x_i$ ‘s over $\mathbb{Q}$ so for any real number $y$ here is a $n\in \mathbb{N}$ and $((i_1),(q_1),\dots, (i_n,q_n)), i_k\in I,q_k\in\mathbb{Q}$ such that

$y=\sum_{k=1}^nq_kx_{i_k}$

Hence

$|\mathbb{R}|\leq \left|\bigcup_{n=1}^{\infty}(I\times \mathbb{Q})^n\right|=|\mathbb{N}|\cdot |\max(|I|,|\mathbb{Q}|)|=\max(|\mathbb{N}|,|I|,|\mathbb{Q}|)<|\mathbb{R}|$

To reach this contradiction, we assumed that $|I|<|\mathbb{R}|$ , so $|I|=|\mathbb{R}|$ .

Now, let’s see how many continuous functions $c:\mathbb{R}\to\mathbb{R}$ there is. A continuous function is uniquely determined by its value on the rational numbers, so $|C|\leq |\mathbb{R}^{\mathbb{Q}}|=|\mathbb{R}|$ , where $|C|$ is the set of continuous functions. On the other hand, the constant functions are continuous, and there are $\mathbb{R}$ of them, so $|C|\geq |\mathbb{R}|$ . Hence $|C|=|\mathbb{R}|=|I|$ , so we can index the set of continuous functions with the set $I$ , so that $C=\{c_i|i\in I\}$ . We can now define $f(x_i)=\lambda_i=c_i(x_i)$ to make sure that the equation $f(x)=c_i(x)$ have a solution. Now $f$ is given by

$f\left(\sum_{i\in I}q_ix_i\right)=\sum_{i\in I}q_i\lambda_i \quad q_i\in \mathbb{Q}, |\{i\in I|q_i\neq 0\}|<\infty.$

QED.

If we want the set of solutions to $f(x)=c(x)$ to be dense in $\mathbb{R}$ , it is a bit more complicated. The idea is, that instead using the set $I$ to index the set of continuous functions, we use it to index the set of continuous functions times the set of open intervals. Unfortunately we cannot be sure that $x_i$ is in the open interval corresponding to $i$ . Instead we start by defining $f(1)=0$ . Now we know that for each $i$ there is a $q_i\in\mathbb{Q}$ such that $q+x_i$ is in the open interval corresponding to $i$ , and we define $f(x_i)=c_i(q_i+x_i)$ .

If we want to show that there exist solution functions with the last property, it is much more complicated: Here we need transfinite induction, because we need to choose the elements of the Hamel basis one at a time. We know that the set of (Borel-)measurable set has the same cardinality as $\mathbb{R}$ , thus the set of functions $c:A\to \mathbb{R}$ , that can be defined as a continuous function $\mathbb{R}\to\mathbb{R}$ restricted to a measurable set $A$ with positive measure, has the cardinality $|\mathbb{R}\times \mathbb{R}|=|\mathbb{R}|$ . Now we index this set by a set $I$ . Using axiom of choice, we can well-order this set, and we can even choose the ordering such that $|\{j\in I|j<|I|=|\mathbb{R}|$ for all $i\in I$ . Now for each $i\in I$ we choose $x_i$ and $\lambda_i$ such that $x_i$ is in the domain of $c_i$ and $f(x_i)=c_i(x_i)$ and such that the $x_i$ ‘s to be linear independent over $\mathbb{Q}$ .

To show that this is possible, I only need to show that when we have chosen $x_j$ for all $j < i$ we can choose $x_i$ such that $x_i$ is linearly independent of the $\{x_j|j<i\}$ over $\mathbb{Q}$ and in the domain of $c_i$ . The rest follows by transfinite induction. We know that measurable sets with positive measure are uncountable, so if we assume the continuum hypothesis (a statement independent of ZFC: it states that a set cannot have a cardinality between $|\mathbb{N}|$ and $|\mathbb{R}|$ ), any measurable set have the same cardinality as $\mathbb{R}$ . (It is still true without the continuum hypothesis, but it is more difficult to prove. See [BS].) We know that $|\{x_j|j<|\mathbb{R}|$ so the cardinality of the linear span over $\mathbb{Q}$ of this set is also less than $|\mathbb{R}|$ , since you cannot reach $|\mathbb{R}|$ by taking countable union and finite products of sets of smaller cardinalities. (In general, still assuming axiom of choice, you cannot get a set with some infinite cardinality $\kappa$ , by taking finite products of sets with smaller cardinality, or by taking union of $\mu<\kappa$ sets with smaller cardinality.) Since the domain of $c_i$ have the same cardinality as $\mathbb{R}$ , we can choose an element $x_i$ in the domain of $c_i$ and not in the linear span of $\{x_j|j<i\}$ .

By transfinite induction, we have now chosen $x_i$ ‘s such that they are linearly independent over $\mathbb{Q}$ . However, we cannot be sure that they span all of $\mathbb{R}$ . So we end by using the axiom of choice once again to extend the set $\{x_i|i\in I\}$ to a Hamel basis, and we set the rest of the $\lambda$ ‘s to be zero. This gives us a solution to Cauchy’s functional equation, with a graph that intersects any continuous function on any measurable set with positive measure.

References

[BS]: James M. Briggs and Thomas Schaffter. Measure and Cardinality. The American Mathematical Monthly, Vol. 86, No. 10, pp. 852-855.

[EH]: Ernst Hansen. Measure Theory. Department of Mathematical Sciences University of Copenhagen. 2009.

[MO]: mathoverflow: Do sets with positive lebesgue measure have same cardinality as R?

Categories: Uncategorized
Tags: Functional equations, Measure theory

Comments: 2 Comments

Cauchy’s functional equation I

December 20, 2010

Next semester, I’m going to write my undergraduate thesis about the $P\neq NP$ problem, and right now I’m trying to decide if I should write it in Danish or in English. So I decided to translate a few pages about Cauchy’s functional equation that I wrote in Danish last year. Today I’ll post the first half of this, and I will post the rest in a few days (update: It’s here. Here you can also find the notes in pdf.). If you have anything to say about the mathematics in this post or about my English, please post a comment.

Cauchy’s functional equation

Cauchy’s functional equation, $f(x+y)=f(x)+f(y), f:\mathbb{R}\to\mathbb{R}$ looks very simple, and it has a class of simple solutions, $f(x)=\lambda x$ , but there are many other and more interesting solutions. In these notes, I will show you what some of these “wild” solutions look like, and I will use them to prove that there exist a set $A\subset \mathbb{R}$ , such that neither $A$ nor $\mathbb{R}\setminus A$ contains a measurable subset with positive measure. Section 1 is about Cauchy’s functional equation on the rational numbers, in section 2 I show that there some wild solutions on $\mathbb{R}$ , and in section 3 I will show that their graphs are dense in $\mathbb{R}^2$ . In section 4 I’ll show that these functions are ugly from a measure theoretical point of view, and in section 5, I’ll show that some of these functions are wilder than others. E.g., I will prove that there is a solution to Cauchy’s functional equation, that intersects any continuous function from $\mathbb{R}$ to $\mathbb{R}$ .

1: The simple solutions

First, we consider the equation over the rational numbers. That is, $f(x+y)=f(x)+f(y),f:\mathbb{Q}\to\mathbb{Q}$ By setting $x=y=0$ we get $f(0)=2f(0)$ and thus $f(0)=0$ . Let’s set $\lambda = f(1)$ . If $f(n)=\lambda n$ we get: $f(n+1)=f(n)+f(1)=\lambda n+\lambda=\lambda (n+1)$ By definition of $\lambda$ , we have $f(n)=\lambda n$ for $n=1$ , so by induction, $f(n)=\lambda n$ for all $n\in\mathbb{N}$ . More generally, we can prove that for $x\in \mathbb{Q}$ and $n\in\mathbb{N}$ we have $f(nx)=nf(x)$ : It is clearly true for $n=1$ and if it is true for $n$ we get: $f((n+1)x)=f(nx+x)=$ $f(nx)+f(x)=nf(x)+f(x)=(n+1)f(x)$ Let $x$ be a positive rational number, and write it as $x=\frac{n}{m}$ , where $n,m\in \mathbb{N}$ . Now, $mf(x)=mf(n/m)=f(n)=nf(1)=\lambda n$ Dividing by $m$ we get $f(x)=f(n/m)=\lambda(n/m)=\lambda x$ . Furthermore, $0=f(0)=f(x+(-x))=f(x)+f(-x)$ so $f(x)=-f(-x)$ . Putting it all together we have $f(x)=\lambda x$ for all $x\in \mathbb{Q}$ . It is easy to verify that $f(x)=\lambda x$ is a solution for the general equation on $\mathbb{R}$ .

2: Existence of wild solutions

Now consider Cauchy’s functional equation on the real numbers, $f(x+y)=f(x)+f(y), f:\mathbb{R}\to\mathbb{R}$ The proof from last section, tells us that $f(q)=qf(1)$ for all rational numbers $q$ , and using the same idea, we can prove that $f(qx)=qf(x)$ for all $q\in \mathbb{Q}$ and $x\in \mathbb{R}$ . But this does not imply that $f(x)=xf(1)$ for all the real numbers. However, if we assume that $f$ is continuous, we can show that $f(x)=\lambda x$ for all $x\in \mathbb{R}$ : We simply choose a sequence $(x_i)_{i\in \mathbb{N}}$ of rational numbers that converge to $x$ . By continuity we get $f(x)=f\left(\lim_{i\to\infty}x_i\right)=\lim_{i\to\infty}f(x_i)=\lim_{i\to\infty}\lambda x_i=\lambda x$ But it is much more fun if we do not have any assumptions on $f$ ! Using axiom of choice we can find non-continuous solutions. The idea is: A priori we only know that $f(0)=0$ . Now we choose some value for $f$ , e.g. $f(1)=3$ . This determines $f$ on all the rational numbers, $f(q)=3q$ for $q\in \mathbb{Q}$ , but the value of $f$ is not determined on any irrational number. So we make another choice, let’s say $f(\sqrt{2})=\pi$ . Now the functional equation tells us that $f(q_1+q_2\sqrt{2})=3q_1+\pi q_2$ for all $q_1,q_2\in \mathbb{Q}$ . But for numbers $x$ not on this from, we cannot determine the value of $f(x)$ . So we simply continue by choosing more and more values of the function. Unfortunately, we have to make infinitely many choices, so we need axiom of choice. In the rest of these notes, I will assume axiom of choice. To formalize the above, we consider the set of real numbers as a vector space over $\mathbb{Q}$ , in much that same way as you can consider $\mathbb{C}$ to be a two dimensional vector space over $\mathbb{R}$ . An important difference is, that when we consider $\mathbb{R}$ to be a vector space over $\mathbb{Q}$ it is infinite dimensional: it even has uncountably many dimensions. We now use the axiom of choice to choose a basis $(x_i)_{i\in I}, x_i\in \mathbb{R}$ (a so-called Hamel basis) and we choose some coefficients $(\lambda_i)_{i\in I},\lambda_i\in \mathbb{R}$ . This defines a linear map from this vector space to itself: $f\left(\sum_{i\in I}q_ix_i\right)=\sum_{i\in I}q_i\lambda_i,$ where the $q_i$ s are rational numbers, and only finitely many of them are non-zero. I called this function ‘linear’, so it sounds like it is a nice function. But it is not! It is only linear when we consider $\mathbb{R}$ as a vector space over $\mathbb{Q}$ and forget about the rest of the structure on $\mathbb{R}$ . This function is only linear in the usual sense on $\mathbb{R}$ if $\frac{\lambda_i}{x_i}$ is the same for all $i$ . All functions on this form are solutions to the Cauchy’s functional equation, and conversely all solutions to Cauchy’s functional equation are on this form.

3: What do I mean by “wild”?

A function can be more or less wild/ugly/pathological. Here is a list of possible definitions of what makes a function $f$ wild. The list is ordered, such that any of the properties imply the one above.

$f$ is discontinuous.
$f$ is discontinuous in every point in $\mathbb{R}$ .
$f$ is unbounded on any open interval.
$f$ is unbounded above on any open interval.
the graph of $f$ , defined by $\{(x,f(x))|x\in\mathbb{R}\}\subset \mathbb{R}^2$ , is dense in $\mathbb{R}^2$ , that is, any point in $\mathbb{R}^2$ is the limit of a sequence of points in the graph of $f$ .

All of these statements are true for any non-linear solution to Cauchy’s functional equation. I will show that the last one of these is true. Proof: Let $f$ be a non-linear solution. If $(x_1,y_1)$ and $(x_2,y_2)$ are points in the graph of $f$ , and $q$ is a rational number, we see that the points $(x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2)$ and $q(x_1,y_1)=(qx_1,qy_1)$ are both in the graph too. In words, any linear combination over $\mathbb{Q}$ of points in the graph are also in the graph. Since $f$ is non-linear we can find real numbers $x_1$ and $x_2$ , both non-zero, such that $\frac{f(x_1)}{x_1}\neq \frac{f(x_2)}{x_2}$ . Now the two vectors $(x_1,f(x_1))$ and $(x_2,f(x_2))$ are linearly independent (over $\mathbb{R}$ ), so they span the plane. That is, any point $(x,y)$ can be written as $a(x_1,f(x_1))+b(x_2,f(x_2))$ for some $a,b\in \mathbb{R}$ . Let $q_i$ and $r_i$ be sequences of rational numbers with $\lim_{i\to \infty}q_i=a$ and $\lim_{i\to\infty}r_i=b$ . Now $q_i(x_1,f(x_1))+r_i(x_2,f(x_2))$ is a sequence of points in the plan converging to $(x,y)$ , so the graph is dense in $\mathbb{R}^2$ .