Wikipedia:Reference desk/Archives/Mathematics/2008 December 31

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 31

Proof that a function from the rationals to dyadic rationals is a bijection

I've been working at this for a while now but haven't really managed to get anywhere with it:

we define f(n) = n for each integer n. we define f(x) as follows a rational x: assume f(x) is defined for all rationals with denominators less than q; then if x = p/q is a rational with denominator q (in lowest terms), we set f(x) = (f(x−) + f (x+))/2, where x− and x+ are the rationals closest to x on either side with denominators less than q. [So f (1/2) = 1/2 , f (1/3) = 1/4 , f (1/4) = 1/8 , f(2/5) = 3/8 , and so on.]

How would one show that f maps Q bijectively to the set D of dyadic rationals (rationals with denominator 2^k)? You can show inductively all f(x) are dyadic rationals, but I'm unsure as to how to show the mapping is 1-1? Are there any appropriate theorems which would be relevant in this case, for example?

Due to the nature of the rationals and the integers, it seems reasonable to only be concerned with integers in the range [0,1], and due to the symmetry of rationals counting from 0->1 and 1->0, we can further restrict this to [0,1/2]. I've also tried looking for a general formula for f(p/q) but other than f(1/n) = 2/(2^n), and f(p/q)+f(1-(p/q))=1, I've achieved very little.

Many thanks,

Mathmos6 (talk) 01:06, 31 December 2008 (UTC) Mathmos6

Do you mean $f(x)={\frac {f(x-)+f(x+)}{2}}$? Otherwise I don't understand how the function produces anything but integers. —Bkell (talk) 01:28, 31 December 2008 (UTC)

Yes - sorry about that, edited now. Mathmos6 (talk) 01:37, 31 December 2008 (UTC)Mathmos6

I think it's easiest to see that it's an isomorphism from the Stern-Brocot tree to a similar binary tree defined on the dyadic rationals. Since each rational (in the interval (0,1), but rationals outside that interval don't really complicate the problem much) appears once as a node in the Stern-Brocot tree and each dyadic rational appears once as a node in the dyadic rational tree, the isomorphism of trees produces a bijection of numbers. —David Eppstein (talk) 01:55, 31 December 2008 (UTC)

Interesting! I've never come across that before - how would you prove the isomorphism between two Stern-Brocot trees, for someone new to the idea? Thanks! Mathmos6 (talk) 02:35, 31 December 2008 (UTC)Mathmos6

Check that the roots correspond and that the transformation preserves left and right children. Then use induction on the lengths of paths to show, for any specification of a node via a path of left and right children from the root, that the specified nodes of the two trees correspond. —David Eppstein (talk) 07:37, 31 December 2008 (UTC)

The function you are describing is the restriction of Minkowski's question mark function to rational numbers. As it maps the interval [0,1] to itself, I think the existence of an inverse function is proved just by showing that the original function is strictly monotonic. Alternativley, you can construct an explicit inverse from the dyadic rationals to the rationals by encocoding the binary expansion of each dyadic rational as a finite continued fraction - this inverse function is called the Conway box function. Gandalf61 (talk) 10:57, 31 December 2008 (UTC)

Very interesting; but who introduced the notation"?"? Minkowski? --PMajer (talk) 10:26, 1 January 2009 (UTC)

Uncountability of x S.T. f(x)=0

We let $f:\mathbb {R} \rightarrow \mathbb {R}$ be a function s.t. $f(x)\geq 0\forall x$, and s.t., whenever $y\neq x$ and $x-f(x)\leq y\leq x+f(x)$, we have $f(y)<f(x)$. I need to show there are uncountably many x with f(x) = 0.

I'm really struggling to even -picture- this function, let alone begin on a proof! Any help understanding would be greatly appreciated!

Ta guys,

Spamalert101 (talk) 02:07, 31 December 2008 (UTC)

I don't know that it's going to help much to try to picture "this function"; there are lots of functions satisfying the statement.

Anyway let's see if this gets you started:

Suppose $x_{0}\,$ is a value such that $f(x_{0})\geq 1$. What special property does $x_{0}\,$ have on the interval $[x_{0}-1,x_{0}+1]\,$ (besides the obvious one, namely that it's the midpoint of the interval)? If it were the case that, say, $f\left(x_{0}+{\frac {1}{4}}\right)\geq 1$, what property would $x_{0}+{\frac {1}{4}}$ have, and are these two things consistent with one another? --Trovatore (talk) 02:58, 31 December 2008 (UTC)

S³ vs P³

How does a topologist distinguish these manifolds? mike40033 (talk) 04:55, 31 December 2008 (UTC)

I assume P³ is the real projective 3-space. Then S³ is simply connected, while P³ has the cyclic group of order 2 as fundamental group. —Preceding unsigned comment added by Aenar (talk • contribs) 13:11, 31 December 2008 (UTC)

You probably allude to the fact that singular homology doesn't see the difference: but the cohomology algebra does, for The cup-length is 1 for the 3-sphere and 3 for the real P³; an elementary invariant is also the Lyusternik–Schnirelmann category: it's 2 for S ³, 4 for P³. Related with this, any $C^{1}$ function on P³ has at least 4 critical points, whereas a function on S³ may have only 2, a maximum and a minimum point.--PMajer (talk) 14:06, 31 December 2008 (UTC)

But integral singular homology does see the difference, unless by P³ you mean something other than real projective 3-space. Algebraist 17:36, 31 December 2008 (UTC)

Yes you are perfectly right, sorry. The real P³, of course. Singular homology does not distinguish between P³ and S²xS¹, this is the big match: the Poincaré polynomial of both is 1+t+t²+t³; but then cohomology algebra works, since the cup-length of S²xS¹ is 2. There is in fact a function on S²xS¹ with only 3 critical points (degenerate). Thank you for correcting me. --PMajer (talk) 20:39, 31 December 2008 (UTC)

Thanks! This should be helpful... mike40033 (talk) 04:11, 2 January 2009 (UTC)