Function ranging over all real values on every open interval
Twoflower
José Carlos Santos
> How can we construct function from R to R which, on every
> open interval, takes every real value?
We can't, but if you want to know how to *prove* that such a function
exists, see example 1.2 from:
http://books.google.com/books?id=fXfEG-F2zJUC&pg=PP1&dq=Bruckner+real+functions#PPA5,M1
Best regards,
Jose Carlos Santos
jbrig...@gmail.com
> How can we construct function from R to R which, on every open interval, takes every real value? Hope I'm clear :-)
So we start with x in an arbitrary open interval and want to produce y
Start by truncating x to just the fractional part.
Express x as a decimal expansion and interpret as a sequence: x[1], x
[2], x[3], etc.
Consider the sequence of all digits in x with odd indices, x[1], x[3],
x[5], ...
If this sequence converges to a fixed digit then let y[1] be that
digit.
If this sequence fails to converge then let y[1] be zero.
Now consider the sequence of all digits in x with indices that are odd
multiples of 2
x[2], x[6], x[10], ...
If this sequence converges to a fixed digit then let y[2] be that
digit.
Otherwise let y[2] be zero.
Repeat in the obvious fashion with digit y[i] being produced as the
limit of digits of x at indices that are odd multiples of 2^(i-1).
Interpret sequence y[] as a decimal expansion and read off y as the
corresponding real number.
Clearly the result y depends only on the "rightmost" digits of x and
will be insensitive to any number of leading digits on the left hand
side of the decimal expansion of x. That's perfect for our purposes.
I'm not sure that this function counts as being constructive for your
purposes. It seems to be well defined, but it does not appear to be
computable.
W^3
<9075094.12339403867...@nitrogen.mathforum.org>,
Twoflower <standa...@gmail.com> wrote:
> How can we construct function from R to R which, on every open interval,
> takes every real value? Hope I'm clear :-)
Let I_n enumerate the open intervals with rational endpoints. Let K
denote the Cantor set. Recall K is compact, contains no interval, and
has the cardinality of R. We can find pairwise dijoint sets K_n, with
each K_n a translate and dilate of K, such that K_n is contained in
I_n for each n*. Choose functions f_n that map K_n onto R. Define f =
f_n on K_n, f = 0 elsewhere. This f does the job.
Proof of *: Translate and dilate K to obtain K_1 inside I_1. K_1
contains no interval, so I_2 \ K_I is open and nonempty. Translate and
dilate K to find K_2 inside I_2 \ K_I. Continue, noting at the nth
stage that K_1 U ... U K_n contains no interval.
W^3
That example doesn't prove there's no constructive approach.
José Carlos Santos
>>> How can we construct function from R to R which, on every
>>> open interval, takes every real value?
>> We can't, but if you want to know how to *prove* that such a function
>> exists, see example 1.2 from:
>>
>> http://books.google.com/books?id=fXfEG-F2zJUC&pg=PP1&dq=Bruckner+real+function
>> s#PPA5,M1
>
> That example doesn't prove there's no constructive approach.
I never said it did.
Ross
> How can we construct function from R to R which, on every open interval, takes every real value? Hope I'm clear :-)
This was the Ponder This problem some years back. I will do one from
(0,1) to (0,1). You can use your favorite bijection from (0,1) to R
before and after. Let x be in (0,1). Express x in ternary. If there
are in infinite number of 2's in the expansion, set f(x)=x and ignore
it. Otherwise, let the last 2 be in the n place. Multiply x by 3^n
and take the fractional part, which consists of only 0's and 1's. Now
read it as binary. To prove this works, consider that you have a
target value y that you want to find an x such that f(x)=y. Note that
every interval contains a subinterval of the form ((3m+2)/3^n,(3m+3)/
3^n).
All the points in this subinterval will have a 2 in the n place.
Append the binary expansion of y to the ternary expansion of (3m+2)/
3^n. Read it in ternary and that is your x.
W^3
José Carlos Santos <jcsa...@fc.up.pt> wrote:
Your answer to "how can we construct" was "We can't, but if you want
to know how to *prove* that such a function exists ..." What exactly
did you mean by that then?
José Carlos Santos
>>>>> How can we construct function from R to R which, on every
>>>>> open interval, takes every real value?
>>>> We can't, but if you want to know how to *prove* that such a function
>>>> exists, see example 1.2 from:
>>>>
>>>> http://books.google.com/books?id=fXfEG-F2zJUC&pg=PP1&dq=Bruckner+real+funct
>>>> ion
>>>> s#PPA5,M1
>>> That example doesn't prove there's no constructive approach.
>> I never said it did.
>
> Your answer to "how can we construct" was "We can't, but if you want
> to know how to *prove* that such a function exists ..." What exactly
> did you mean by that then?
I meant that such a function cannot be constructed but, in spite of
that, its existence could be proved. Then I told the OP where he could
see such a proof.
If the OP had asked how one could construct a non-continuous function
from the reals into the reals which preserves the sum I would have
given him the same reply (with a different link, of course :-) ).
The idea that the existence of such a proof would prove that such a
function cannot be constructed never crossed my mind. I don't understand
how you could have interpreted my reply that way.
W^3
José Carlos Santos <jcsa...@fc.up.pt> wrote:
> On 06-02-2009 22:41, W^3 wrote:
>
> >>>>> How can we construct function from R to R which, on every
> >>>>> open interval, takes every real value?
> >>>> We can't, but if you want to know how to *prove* that such a function
> >>>> exists, see example 1.2 from:
> >>>>
> >>>> http://books.google.com/books?id=fXfEG-F2zJUC&pg=PP1&dq=Bruckner+real+fun
> >>>> ct
> >>>> ion
> >>>> s#PPA5,M1
> >>> That example doesn't prove there's no constructive approach.
> >> I never said it did.
> >
> > Your answer to "how can we construct" was "We can't, but if you want
> > to know how to *prove* that such a function exists ..." What exactly
> > did you mean by that then?
>
> I meant that such a function cannot be constructed but, in spite of
> that, its existence could be proved.
That is false, and that is my point. See the example I gave.
> Then I told the OP where he could
> see such a proof.
>
> If the OP had asked how one could construct a non-continuous function
> from the reals into the reals which preserves the sum I would have
> given him the same reply (with a different link, of course :-) ).
>
> The idea that the existence of such a proof would prove that such a
> function cannot be constructed never crossed my mind. I don't understand
> how you could have interpreted my reply that way.
It crossed my mind that you believed the proof you cited, which
appeals to the existence of Hamel bases, surely indicates that no
constructive example can be given. But you're right, I didn't voice my
objection correctly. Let me try again: What led you to believe we
can't construct such an example?
José Carlos Santos
>>>>>>> How can we construct function from R to R which, on every
>>>>>>> open interval, takes every real value?
>>>>>> We can't, but if you want to know how to *prove* that such a function
>>>>>> exists, see example 1.2 from:
>>>>>>
>>>>>> http://books.google.com/books?id=fXfEG-F2zJUC&pg=PP1&dq=Bruckner+real+fun
>>>>>> ct
>>>>>> ion
>>>>>> s#PPA5,M1
>>>>> That example doesn't prove there's no constructive approach.
>>>> I never said it did.
>>> Your answer to "how can we construct" was "We can't, but if you want
>>> to know how to *prove* that such a function exists ..." What exactly
>>> did you mean by that then?
>> I meant that such a function cannot be constructed but, in spite of
>> that, its existence could be proved.
>
> That is false, and that is my point. See the example I gave.
You are right and I was wrong.
>> Then I told the OP where he could
>> see such a proof.
>>
>> If the OP had asked how one could construct a non-continuous function
>> from the reals into the reals which preserves the sum I would have
>> given him the same reply (with a different link, of course :-) ).
>>
>> The idea that the existence of such a proof would prove that such a
>> function cannot be constructed never crossed my mind. I don't understand
>> how you could have interpreted my reply that way.
>
> It crossed my mind that you believed the proof you cited, which
> appeals to the existence of Hamel bases, surely indicates that no
> constructive example can be given. But you're right, I didn't voice my
> objection correctly. Let me try again: What led you to believe we
> can't construct such an example?
What led to my belief was the fact that I was convinced that such a
function could not be Lebesgue measurable.
Yes, you constructed such a function, as well as two other posters. I
wasn't thinking straight. :-(
Dave L. Renfro
>> How can we construct function from R to R which,
>> on every open interval, takes every real value?
José Carlos Santos wrote (cited URL minimized):
> We can't, but if you want to know how to *prove* that
> such a function exists, see example 1.2 from:
>
> http://books.google.com/books?id=fXfEG-F2zJUC&pg=PA5
In 1904 Lebesgue (see p. 90 of [1]) gave a definition of
such a function that fits most any notion of constructability
I know of. Lebesgue gave a Baire 2 function that is very
simply defined from decimal expansions. For English versions
of Lebesgue's function, see [2] and the first two full
paragraphs of p. 116 of [3]. Note that Lebesgue's actual
example (first full paragraph of p. 116 of [3]) takes,
on every open interval, every value in the closed interval
[0,1], but there are many ways to easily modify it (for one
such way, see the second full paragraph on p. 116 of [3])
so that it takes, on every open interval, every real value.
No doubt Lebesgue was aware of this, but the modifications
were probably too tangential and trivial for Lebesgue to
bother with. For other references and more exotic examples
(e.g. a function that takes, in every nonempty perfect set,
every real value 2^aleph_0 many times), see [4]. By the way,
the constructions in Halperins' papers (pp. 117-118 in [3] below
and reference [3] in [4] below) of a function that takes,
in every nonempty perfect set, every real value 2^aleph_0
times follow immediately from Halperin's earlier construction
of a function that takes every real value at least once in
every perfect set and the fact that every nonempty perfect
set can be written as the union of 2^aleph_0 many pairwise
disjoint perfect sets (a short proof of this fact about perfect
sets is given in [5] below). This observation about Halperin's
examples is due to Solomon Marcus in 1960 (reference [4]
in [4] below).
[1] Henri Lebesgue, "Lecons sur l'Intégration et la Recherche
des Fonctions Primitives", Gauthier-Villars, 1904.
http://books.google.com/books?id=soMRAAAAYAAJ&pg=PA90
[2] sci.math -- Non zero Lebesgue measure
(Ilias Kastanas, 8 January 1996)
http://groups.google.com/group/sci.math/msg/502fde0541cc97a0
[3] Israel Halperin, "Discontinuous functions with the Darboux
property", Canadian Mathematical Bulletin 2 (1959), 111-118.
http://books.google.com/books?id=-st_B62xKbYC&pg=PA111
[4] sci.math -- Strange function
(Dave L. Renfro, 4 December 2000)
http://groups.google.com/group/sci.math/msg/712092d7b9852455
[5] sci.math -- uncountability of the reals
(Dave L. Renfro, 1 July 2001)
http://groups.google.com/group/sci.math/msg/86ef3b7928eff8e9
Dave L. Renfro
Zdislav V. Kovarik
On Fri, 6 Feb 2009, Twoflower wrote:
> How can we construct function from R to R which, on every open
interval, takes every real value? Hope I'm clear :-)
>
From my Analysis course long time ago:
A more modest plan first, a function g that maps every (non-empty) open
interval onto (0,1), then we can define
f(x)=(2*g(x)-1)/(1-abs(2*g(x)-1))
To get g(x): hint is "average the digits as much as possible".
Technically:
Replace x by x1=x-floor(x);
x1 has decimal digits
a(1), a(2), ...
calculate g1(x1) = lim sup_n ((a(1)+...+a(n))/n)
for those x1 for which g1(x1)=0 or 9, define
g(x)=1/2 (to avoid endpoints),
otherwise define
g(x)=g1(x1)/9.
(The use of binary digits comes out neater - your exercise.)
The range is as required because g1(x1) does not depend on the first
finitely many digits of x1, which can be the digits used to confine
x1 to the given open interval.
Cheers, ZVK(Slavek).