My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree1Thanks
Reply
 
LinkBack Thread Tools Display Modes
August 6th, 2014, 10:08 AM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Messing Around - Relating Sets of Dyadics to Reals

I haven't seen any new threads here for a while. As always, I promise this is Fields Medal material , but perhaps someone will find it interesting anyways.

To start, in my hopeless quest to find a discrete uniform distribution over $\mathbb{N}$, I was thinking in terms of base 2 on the unit interval and came across the following:

Let $D = \{d \in (0,1]: d \text{ is a dyadic rational } \}$

Let $\alpha(x) = \{ d \in D : d < x \}$

Conjecture: There exists $x,y \in (0,1]$ where $x \not= y$ and $\alpha(x) = \alpha(y)$.

Can anyone give an example where this is true? I'm thinking no, though it better be true if $|\mathbb{R}_{(0,1]}| > |D|$, so the lack of a real-world example isn't going to deter me here.

Assuming the conjecture is true, we can create a unique interval on (0,1] for each dyadic in $D$:

Let $\beta(x) = d \rightarrow (d \in D \wedge \alpha(x) = \alpha(d))$.

Each dyadic $d \in D$ then defines its own interval equal to $\{ x \in (0,1] : \beta(x) = d \}$.

These intervals are interesting. Their measure would have to be 0, because the sum of the measures would equal $\infty$ otherwise, but at the same time we must assume that the set of elements in each interval has a cardinality equal to $2^{\aleph_0}$ and is continuous. Is this possible? (clearly, it is, but )

Let $z$ be a randomly selected element of (0,1] given a uniform distribution. As CRGreathouse pointed out in an earlier thread, we can do this by randomly choosing each bit $x_i$ of $0.x_1x_2x_3...$ (temporarily ignoring the patchable problem of each dyadic having two binary representations, except 1, and all other elements of (0,1] having only one representation).

This is the paragraph where CRGreathouse will have to come save the day (ie... potential crankery warning)... That said, we are guaranteed to have $\beta(z)$ equal to a dyadic in (0,1]. All dyadics in $D$ had an equal probability of being equal to $\beta(z)$, having selected $z$ uniformly at random, so we must conclude that our dyadic $\beta(z)$ is selected uniformly at random as well. ... Might as well finish it. Let $\psi$ be a bijection from $D$ onto $\mathbb{N}$. Then we have a unique positive integer, $\psi(\beta(z))$, where again all positive integers had an equal chance of being equal to $\psi(\beta(z))$, so I conclude that $\psi(\beta(z))$ is also selected uniformly at random.

Last edited by AplanisTophet; August 6th, 2014 at 10:16 AM.
AplanisTophet is offline  
 
August 6th, 2014, 10:49 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
For those of you following along: "dyadic rational" is the name for rational numbers with a denominator (in lowest terms) which is a power of 2.

Quote:
Originally Posted by AplanisTophet View Post
Let $D = \{d \in (0,1]: d \text{ is a dyadic rational } \}$

Let $\alpha(x) = \{ d \in D : d < x \}$

Conjecture: There exists $x,y \in (0,1]$ where $x \not= y$ and $\alpha(x) = \alpha(y)$.
The conjecture is false. There is a dyadic rational in (min(x,y), max(x,y)) unless x = y.

Quote:
Originally Posted by AplanisTophet View Post
it better be true if $|\mathbb{R}_{(0,1]}| > |D|$
I have no idea why you think these two are related.

Quote:
Originally Posted by AplanisTophet View Post
Let $z$ be a randomly selected element of (0,1] given a uniform distribution. As CRGreathouse pointed out in an earlier thread, we can do this by randomly choosing each bit $x_i$ of $0.x_1x_2x_3...$ (temporarily ignoring the patchable problem of each dyadic having two binary representations, except 1, and all other elements of (0,1] having only one representation).
Right... but be sure to specify that you want z to be selected uniformly at random (not just "a randomly selected element of (0, 1]" which could have some other distribution).

Quote:
Originally Posted by AplanisTophet View Post
Assuming the conjecture is true
I skipped this part since it isn't.
Thanks from AplanisTophet
CRGreathouse is offline  
August 6th, 2014, 01:56 PM   #3
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Quote:
Originally Posted by AplanisTophet View Post
Can anyone give an example where [the conjecture from the op] is true? I'm thinking no, though it better be true if $|\mathbb{R}_{(0,1]}| > |D|$, so the lack of a real-world example isn't going to deter me here.
Quote:
Originally Posted by CRGreathouse View Post
I have no idea why you think these two are related.
Well, let $\gamma(x) = \alpha(x) \setminus \bigcup_{y \in (0,x)} \alpha(y)$

The set $\gamma(x)$ will then contain at least one element if the conjecture is false (and $x \leq 1$). Further, the collection $\{ \gamma(x) : x \in (0,1] \}$ must be pairwise disjoint.

Let $\delta(d) = x \rightarrow d \in \gamma(x)$

Then, $\delta$ is a function from (a subset of) $D$ onto $\mathbb{R}_{(0,1]}$, and the cardinality of $D$ must be equal to or greater than the cardinality of $\mathbb{R}_{(0,1]}$.

Last edited by AplanisTophet; August 6th, 2014 at 02:17 PM.
AplanisTophet is offline  
August 7th, 2014, 05:45 AM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by AplanisTophet View Post
Well, let $\gamma(x) = \alpha(x) \setminus \bigcup_{y \in (0,x)} \alpha(y)$
Let's simplify that. $\alpha(x)=(0,x)\cap D,$ so
$$
\gamma(x)=\left[(0,x)\setminus\bigcup_{y<x}(0,y)\right]\cap D=\{z:\ z<x\wedge\forall y<x,\ z>y\}\cap D=\emptyset\cap D=\emptyset
$$

Quote:
Originally Posted by AplanisTophet View Post
The set $\gamma(x)$ will then contain at least one element if the conjecture is false (and $x \leq 1$).
No, the conjecture is false and $\gamma(x)$ is uniformly empty.
CRGreathouse is offline  
August 7th, 2014, 07:55 AM   #5
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Quote:
Originally Posted by CRGreathouse View Post
No, the conjecture is false and $\gamma(x)$ is uniformly empty.
I agree that $\gamma(x)$ is uniformly empty as implied by the op, but then I don't see how the conjecture is not true if that is the case.

Specifically, if the conjecture is false, we have $y < x \rightarrow \alpha(y) \subset \alpha(x)$. This should hold true for every possible value of $y < x$. It doesn't though, so at what point do we hit a $y$ where it doesn't?
AplanisTophet is offline  
August 7th, 2014, 08:08 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by AplanisTophet View Post
I agree that $\gamma(x)$ is uniformly empty as implied by the op, but then I don't see how the conjecture is not true if that is the case.
I'm sorry for your confusion, but I don't understand it.

Quote:
Originally Posted by AplanisTophet View Post
Specifically, if the conjecture is false, we have $y < x \rightarrow \alpha(y) \subset \alpha(x)$.
I think you mean $0<y<x<1\rightarrow\alpha(y)\subsetneq\alpha(x).$ Right?

Expanding, this is $0<y<x<1\rightarrow(0,y)\cap D\subsetneq(0,x)\cap D.$ In other words, $(y,x)\cap D\ne\emptyset$ when $0<y<x<1$ ("there is some dyadic rational between y and x when y < x"). This is pretty obvious, yes? It's a standard undergraduate exercise to prove this for $\mathbb{Q}$ in place of D, and this version is no harder.
CRGreathouse is offline  
August 7th, 2014, 08:27 AM   #7
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Quote:
Originally Posted by CRGreathouse View Post
Expanding, this is $0<y<x<1\rightarrow(0,y)\cap D\subsetneq(0,x)\cap D.$ In other words, $(y,x)\cap D\ne\emptyset$ when $0<y<x<1$ ("there is some dyadic rational between y and x when y < x"). This is pretty obvious, yes? It's a standard undergraduate exercise to prove this for $\mathbb{Q}$ in place of D, and this version is no harder.
It's only obvious when $y$ is not thought of as approaching $x$ infinitesimally. I compare this to standing in a field and declaring the world is flat based on what is observable from a point in the field.

If $\gamma(x)$ is empty and $y$ never equals $x$, then there must exist a $y$ and $x$ where $\alpha(y) = \alpha(x)$. I don't see any way around this.
AplanisTophet is offline  
August 7th, 2014, 08:57 AM   #8
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
That I may properly understand you: you're claiming that there are real numbers $y<x$ such that there are no dyadic rationals in $(y,x)$. Correct?
CRGreathouse is offline  
August 7th, 2014, 10:45 AM   #9
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 422
Thanks: 26

Quote:
Originally Posted by CRGreathouse View Post
That I may properly understand you: you're claiming that there are real numbers $y<x$ such that there are no dyadic rationals in $(y,x)$. Correct?
No. We'll have to leave that alone or we'll get stuck on this.

We know that as $x$ increases, $\alpha(x)$ changes (grows, I'll say). Let $dx$ be an infinitesimal change in $x$. Does $\alpha(x) = \alpha(x + dx)$? If $x \in D$, the answer is no, it doesn't. If $x \not\in D$, then I believe the answer is yes.

Now what say you?
AplanisTophet is offline  
August 7th, 2014, 11:32 AM   #10
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Quote:
Originally Posted by AplanisTophet View Post
Now what say you?
The only real infinitesimal is 0.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
dyadics, messing, reals, relating, sets



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Approach reals by 3-smooth numbers Maurice1969 Number Theory 11 October 23rd, 2013 12:24 AM
Independence of Reals mathbalarka Number Theory 1 May 9th, 2013 06:51 AM
Prove a set is a subring of the reals HairOnABiscuit Abstract Algebra 11 September 11th, 2012 12:37 PM
Integration over the reals? finding R(dx) cernlife Real Analysis 5 May 30th, 2011 09:37 PM
functions in reals such that inequality holds maximus101 Real Analysis 5 February 14th, 2011 06:19 PM





Copyright © 2018 My Math Forum. All rights reserved.