Strange function
David Turner
I'm trying to construct a bijection from the group R/Q (quotient group
of reals over rationals) onto R (the reals). Group operation in each
case is addition. Firstly, does it exist and secondly, how might I go
about doing it?
I think my problem is that I cannot 'see' what R/Q is. The way I'm
trying to think about it is with an equivalence relation ~ such that a~b
<=> a-b is rational. Obviously R/Q is isomorphic to the set of
equivalence classes of ~. The bijection I'm looking for maps each
equivalence class onto a single real. Intuitively, there are fewer
equivalence classes than reals, which I know is wrong because there are
uncountably many reals and an uncountable number of equivalence classes,
but I'm having trouble thinking round this intuition.
TIA
--
Dave Turner
dc...@cam.ac.uk
Why put off until tomorrow something which you can get out of
completely?
Virgil
<dc...@cam.ac.uk> wrote:
> Hi all,
>
> I'm trying to construct a bijection from the group R/Q (quotient group
> of reals over rationals) onto R (the reals). Group operation in each
> case is addition. Firstly, does it exist and secondly, how might I go
> about doing it?
>
> I think my problem is that I cannot 'see' what R/Q is. The way I'm
> trying to think about it is with an equivalence relation ~ such that a~b
> <=> a-b is rational. Obviously R/Q is isomorphic to the set of
> equivalence classes of ~. The bijection I'm looking for maps each
> equivalence class onto a single real. Intuitively, there are fewer
> equivalence classes than reals, which I know is wrong because there are
> uncountably many reals and an uncountable number of equivalence classes,
> but I'm having trouble thinking round this intuition.
>
> TIA
I think it unlikely that you will be able to come up with a specific
construction of such a function. The best you will probably be able to
come up with is proving what you already know, that such a bijection
exists.
David C. Ullrich
wrote:
>Hi all,
>
>I'm trying to construct a bijection from the group R/Q (quotient group
>of reals over rationals) onto R (the reals). Group operation in each
>case is addition. Firstly, does it exist and secondly, how might I go
>about doing it?
Yes, there is such a thing. You're not going to be able
to "construct" it without using the Axiom of Choice, giving a
very non-constructive "construction".
Dunno what the context is here. You need to note
first that if K is any field then there is a notion of "vector space
over K", that being a vector space with elements of K for scalars.
In particular there is such a thing as a "vector space over Q",
and R _is_ a vector space over Q. For the rest of this that's how
we view R, as a Q-vector space.
The set {1} is linearly independent, since it contains
exactly one vector and that vector is non-zero. Any independent
set can be extended to a basis. So there exists a set B contained
in R such that 1 is an element of B and also every x in R has a
unique representation
x = q_1*b_1 + ... + q_n*b_n
where the q_j are rational and the b_j are in B. (B is often
called a "Hamel basis".)
Let B' be B \ {1}, that is, B with 1 removed. Let
R' be the Q-span of B', that is the set of all linear combinations
of elements of B' (with rational coefficients).
Now B is certainly infinite (since R is uncountable), and
hence B and B' have the same cardinality. Hence R and R' are
isomorphic (isomorphic as Q-vector spaces, and hence isomorphic
as additive groups) because two vector spaces over the same
field are isomorphic if and only if they have the same dimension.
Otoh since B is a basis for R there is a linear map
from R to R assigning the elements of B to any elements of
R we wish. In particular there is a Q-linear map T:R->R such
that
T(1) = 0
and
T(b) = b (b in B, b <> 1).
It's easy to see that the range of T is exactly T(R) = R'.
Otoh the range of T is isomorphic to the domain modulo
the kernel (or nullspace), so this says that R' is isomorphic
to R/kernel(T). But the kernel of T is exactly Q. So
R' is isomorphic to R/Q.
Hence R and R/Q are isomorphic since they're
both isomorphic to R'. (Isomorphic as Q-vector spaces and
hence as additive groups.)
>I think my problem is that I cannot 'see' what R/Q is. The way I'm
>trying to think about it is with an equivalence relation ~ such that a~b
><=> a-b is rational. Obviously R/Q is isomorphic to the set of
>equivalence classes of ~. The bijection I'm looking for maps each
>equivalence class onto a single real. Intuitively, there are fewer
>equivalence classes than reals, which I know is wrong because there are
>uncountably many reals and an uncountable number of equivalence classes,
>but I'm having trouble thinking round this intuition.
>
>TIA
>
David Turner
>
> Yes, there is such a thing. You're not going to be able
> to "construct" it without using the Axiom of Choice, giving a
> very non-constructive "construction".
>
> Dunno what the context is here.
Okok I admit it - this is (almost) a homework question. The original
question was "Construct a function f: R -> R such that f takes every
value on every interval". I thought through it and came to the
conclusion that it would be possible if I could construct a bijection
from R/Q -> R, and this seemed the only sensible way of going about it.
> You need to note
> first that if K is any field then there is a notion of "vector space
> over K", that being a vector space with elements of K for scalars.
> In particular there is such a thing as a "vector space over Q",
> and R _is_ a vector space over Q. For the rest of this that's how
> we view R, as a Q-vector space.
Ok, I can accept that. That is a viewpoint I hadn't thought of.
> The set {1} is linearly independent, since it contains
> exactly one vector and that vector is non-zero. Any independent
> set can be extended to a basis. So there exists a set B contained
> in R such that 1 is an element of B and also every x in R has a
> unique representation
>
> x = q_1*b_1 + ... + q_n*b_n
>
> where the q_j are rational and the b_j are in B. (B is often
> called a "Hamel basis".)
>
> Let B' be B \ {1}, that is, B with 1 removed. Let
> R' be the Q-span of B', that is the set of all linear combinations
> of elements of B' (with rational coefficients).
>
> Now B is certainly infinite (since R is uncountable), and
> hence B and B' have the same cardinality. Hence R and R' are
> isomorphic (isomorphic as Q-vector spaces, and hence isomorphic
> as additive groups) because two vector spaces over the same
> field are isomorphic if and only if they have the same dimension.
Aha! There is the missing link. I would have thought that B would be
linearly dependent if it were possible to remove 1 from it and still
have a spanning set but infinity is obviously less well-behaved than
that.
I think I get the gist of what is going on, and maybe the question was
worded a little badly because 'construct' implies a more concrete
definition than simply proving such a function exists, which you suggest
is all that is possible.
Many many thanks
David C. Ullrich
David Turner <dc...@cam.ac.uk> wrote:
> "David C. Ullrich" wrote:
> >
> > Yes, there is such a thing. You're not going to be able
> > to "construct" it without using the Axiom of Choice, giving a
> > very non-constructive "construction".
> >
> > Dunno what the context is here.
>
> Okok I admit it - this is (almost) a homework question. The original
> question was "Construct a function f: R -> R such that f takes every
> value on every interval". I thought through it and came to the
> conclusion that it would be possible if I could construct a bijection
> from R/Q -> R, and this seemed the only sensible way of going about
it.
I realized after I sent the message that you'd asked for
a _bijection_ between R and R/Q. I'd assumed you wanted an
isomorphism - getting a bijection is no problem at all.
Luckily, homework-problem-wise, I have no idea what getting
a bijection from R to R/Q has to do with what the problem actually
asked. What's the connection? Given a bijection f from R to R/Q then
the function that takes every value on every interval is what?
??? When you remove 1 from B you do _not_ get a spanning set.
Well, you don't get something that spans R. _Any_ subset of a
spanning set spans _something_. Like here B' spans R'.
> I think I get the gist of what is going on, and maybe the question was
> worded a little badly because 'construct' implies a more concrete
> definition than simply proving such a function exists, which you
suggest
> is all that is possible.
Note again I didn't say _anything_ about functions that
take every value on every interval. Or I didn't mean to and
I'm not aware that I did. I've only thought about it for a few
seconds, but I don't see the connection between the two questions.
> Many many thanks
>
> --
> Dave Turner
> dc...@cam.ac.uk
>
> Why put off until tomorrow something which you can get out of
> completely?
>
--
Oh, dejanews lets you add a sig - that's useful...
Sent via Deja.com http://www.deja.com/
Before you buy.
David Whitbeck
Well use the Cantor map to get from Q to Z. So Z ~= Q. Now f:R->S^1
(unit circle under mult. and Z under addition) by f(x)=exp(i*2*pi*x). ker
f=Z, im f =S^1, f is a homomorphism so apply the first isomorphism theorem
and bust out with R/Z ~= R => R/Q ~= R.
easy soln: Or you can note that R/Q are the left cosets of Q that
partition the group R. So an element of R/Q looks like r+Q where r is
real so you could you use as your function g(r+Q)=r, which I believe is
bijective.
David
In article <3A2648AE...@cam.ac.uk>, David Turner <dc...@cam.ac.uk> wrote:
> Hi all,
>
> I'm trying to construct a bijection from the group R/Q (quotient group
> of reals over rationals) onto R (the reals). Group operation in each
> case is addition. Firstly, does it exist and secondly, how might I go
> about doing it?
>
> I think my problem is that I cannot 'see' what R/Q is. The way I'm
> trying to think about it is with an equivalence relation ~ such that a~b
> <=> a-b is rational. Obviously R/Q is isomorphic to the set of
> equivalence classes of ~. The bijection I'm looking for maps each
> equivalence class onto a single real. Intuitively, there are fewer
> equivalence classes than reals, which I know is wrong because there are
> uncountably many reals and an uncountable number of equivalence classes,
> but I'm having trouble thinking round this intuition.
>
> TIA
>
Unknown
Whitbeck) wrote:
>fun stuff:
>Well use the Cantor map to get from Q to Z. So Z ~= Q. Now f:R->S^1
>(unit circle under mult. and Z under addition) by f(x)=exp(i*2*pi*x). ker
>f=Z, im f =S^1, f is a homomorphism so apply the first isomorphism theorem
>and bust out with R/Z ~= R => R/Q ~= R.
>
>easy soln: Or you can note that R/Q are the left cosets of Q that
>partition the group R. So an element of R/Q looks like r+Q where r is
>real so you could you use as your function g(r+Q)=r, which I believe is
>bijective.
This isn't well defined: 0 = g(0+Q) = g(1+Q) = 1.
>In article <3A2648AE...@cam.ac.uk>, David Turner <dc...@cam.ac.uk> wrote:
>
>> Hi all,
>>
>> I'm trying to construct a bijection from the group R/Q (quotient group
>> of reals over rationals) onto R (the reals). Group operation in each
>> case is addition. Firstly, does it exist and secondly, how might I go
>> about doing it?
--
lemma
Dave L. Renfro
[sci.math Fri, 01 Dec 2000 19:40:55 +0000]
<http://forum.swarthmore.edu/epigone/sci.math/chimpderpin/3A27FEC7...@cam.ac.uk>
wrote (in part)
> Okok I admit it - this is (almost) a homework question. The
> original question was "Construct a function f: R -> R such that
> f takes every value on every interval". I thought through it
> and came to the conclusion that it would be possible if I could
> construct a bijection from R/Q -> R, and this seemed the only
> sensible way of going about it.
[Hopefully your homework has been turned in by now.]
Note that any such function satisfies the intermediate value
property, which shows in a rather strong way that the converse of
"f is continuous in an interval ==> f has the intermediate value
property in that interval" is false.
1. On page 644 of The American Mathematical Monthly 107
(Aug.-Sept. 2000):
Let {D_t, t in R} be a resolution of R into disjoint, dense
subsets. Define f: R --> R by f(x) = t for x in D_t. If t in
R, then S_t = D_t intersect (a,b) not= emptyset; indeed S_t
is dense in (a,b). For c in S_t, then, f(c) =t, and f is
"as discontinuous as possible" at c since f assumes all real
values on every neighborhood of c.
[Contributed by Donald P. Minassian, Butler University]
2. Let H be any Hamel basis for the reals R as a vector space
over the rationals and let g: H --> R be surjective. Extend
g to all of R by letting g(rx) = r*g(x) when r is a nonzero
rational number and x in H, and define g however you wish
otherwise. Then g takes every real value in every interval.
See pp. 5-6 of [1] and p. 97 of [2].
3. For each 0 < x < 1, let h(x) = lim-sup(n --> infinity) of
(1/n)*(b1 + b2 + b3 + ... + bn), where .b1b2b3... is the
dyadic expansion of x that doesn't have a tail of 1's.
[Note that h(x) is only a Baire 2 function.] Then h takes
every value in every subinterval of (0,1). See pp. 5-6 of
[1] and pp. 98-99 of [2].
4. There exists a function F: R --> R that takes every real
value c-times, c = 2^(Aleph_0), in every interval. See [3].
5. There exists a function G: R --> R that takes every real
value c-times in every perfect set. See [3].
6. There exists a function C: R --> R that takes every real
value c-times in every perfect set, and yet the graph of
y = C(x) is a connected subset of R^2. See p. 312 of [4].
[1] Anderw M. Bruckner, DIFFERENTIATION OF REAL FUNCTIONS,
CRM Monograph Series 5, Amer. Math. Soc., 1994.
[QA 304 .B78 1994]
[2] Andrew M. Bruckner and Jack G. Ceder, "Darboux continuity",
Jahresbericht Deutschen Mathem.-Vereinigung 67 (1965), 93-117.
<http://www.emis.de/cgi-bin/zarchive?an=144.30003>
<http://www.emis.de/cgi-bin/zarchive?an=144.301>
[3] Israel Halperin, "Discontinuous functions with the Darboux
property", Amer. Math. Monthly 57 (1950), 539-540.
<http://www.emis.de/cgi-bin/zarchive?an=040.17301>
[4] Solomon Marcus, "Functions with the Darboux property and
functions with connected graphs", Math. Annalen 141 (1960),
311-317. <http://www.emis.de/cgi-bin/zarchive?an=095.26902>
Dave L. Renfro