My Math Forum  

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

Number Theory Number Theory Math Forum


Thanks Tree6Thanks
Reply
 
LinkBack Thread Tools Display Modes
December 12th, 2016, 02:13 AM   #11
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 306
Thanks: 21

Maschke, you can stop with the two approaches we've discussed. Again, I'll comment on this more fully next weekend, but I agree now wholeheartedly that the Vitali set was a bad idea ( $q_k$ is more likely to be in [-0.5, 0.5] than elsewhere so the proof I used fails in producing a natural uniformly at random). I believe the 'addition mod 1' approach is also flawed because once you pick your $r$ uniformly at random it's generally relative to 0 if using the rationals in [0, 1) and trying to 'wrap' those where $r + q > 1$ back starting from 0. Therefore, whatever bijection you choose between the naturals and the rationals in [0, 1), the natural corresponding to 0 is the one that gets selected without some 'impossibly fancy' cleanup.

However, keeping the cosets and ditching both the Vitali and addition mod 1 approaches leaves something that I believe works, so again, until next weekend.
AplanisTophet is offline  
 
December 12th, 2016, 08:54 AM   #12
Senior Member
 
Joined: Aug 2012

Posts: 1,429
Thanks: 352

Quote:
Originally Posted by AplanisTophet View Post
However, keeping the cosets and ditching both the Vitali and addition mod 1 approaches leaves something that I believe works, so again, until next weekend.
Just a brief comment. Do you understand that countable additivity precludes there being a uniform measure on the naturals, or on any countable set? That's a key point. Once you know that, you'll stop saying, "something I believe works," and start saying, "something that looks like it works and I can't figure out why it doesn't."

There is no uniform probability measure on the naturals and that's very easy to prove. By uniformity, the measure of each point must be the same. If the measure of a point is $0$, by countable additivity the measure of $\mathbb N$ must be $0$. And if the measure of a point is greater than zero, the measure of $\mathbb N$ must be infinite. It's not possible to find a uniform measure such that the measure of $\mathbb N$ is $1$.

As an example, if we drop the uniformity requirement, there is a probability measure on $\mathbb N$. Just assign the value $\frac{1}{2^n}$ to the natural number $n$. So the measure of $1$ is $\frac{1}{2}$, the measure of $10$ is $\frac{1}{1024}$, etc. By countable additivity, the measure of $\mathbb N$ is therefore $1$, and we have a nice probability measure. But some numbers are a lot more likely than others, so we lose uniformity.

You can't put a uniform measure on the naturals. That's a solid fact.

Last edited by Maschke; December 12th, 2016 at 08:59 AM.
Maschke is offline  
December 12th, 2016, 10:06 AM   #13
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 306
Thanks: 21

Quote:
Originally Posted by Maschke View Post
Just a brief comment. Do you understand that countable additivity precludes there being a uniform measure on the naturals, or on any countable set? That's a key point. Once you know that, you'll stop saying, "something I believe works," and start saying, "something that looks like it works and I can't figure out why it doesn't."

There is no uniform probability measure on the naturals and that's very easy to prove. By uniformity, the measure of each point must be the same. If the measure of a point is $0$, by countable additivity the measure of $\mathbb N$ must be $0$. And if the measure of a point is greater than zero, the measure of $\mathbb N$ must be infinite. It's not possible to find a uniform measure such that the measure of $\mathbb N$ is $1$.

As an example, if we drop the uniformity requirement, there is a probability measure on $\mathbb N$. Just assign the value $\frac{1}{2^n}$ to the natural number $n$. So the measure of $1$ is $\frac{1}{2}$, the measure of $10$ is $\frac{1}{1024}$, etc. By countable additivity, the measure of $\mathbb N$ is therefore $1$, and we have a nice probability measure. But some numbers are a lot more likely than others, so we lose uniformity.

You can't put a uniform measure on the naturals. That's a solid fact.
I do realize the above, hence my comment in the OP that it was impossible to have a set A. You gave me a set A though, so even though I see this is as a paradox and agree with you, I still very much look forward to you "working with [your] understanding of this problem, which is that we can seemingly induce this mystery distribution."

So here is the approach I suggest and after this I'm done. We both assume there is something wrong because of your argument above, but can you find it?


1) Let $q_1, q_2, q_3, …$ be an enumeration of $A = \mathbb{Q} \cap (0,1)$.

2) Select a real number $r \in (0,1)$ uniformly at random.

3) Let $B = \mathbb{Q} \cap (-r, 1-r)$. Note that $r \in (0,1) \Rightarrow 0 \in B$. Also note that the length of $(-r, 0)$ is completely dependent upon $r$ which was selected uniformly at random, so the length has likewise been selected uniformly at random.

4) Let $f:A \rightarrow B$ be a bijection.* This step is to relate some $q_i$ to the element $0 \in B$ in a way that allows any $i \in \mathbb{N}$ a chance of being selected uniformly at random, just as $r$ and the length of $(-r, 0)$ were.

5) Let $C = \{ r + q : q \in B \}$. Note that $0 \in B \Rightarrow r \in C$.

6) Let $g:B \rightarrow C$ be a bijective function: $g(b) = b + r$. Note that $0 \in B \Rightarrow \exists g(0) = r$.

7) $\exists i \in \mathbb{N} : f(q_i) = 0 \Rightarrow g(f(q_i) = g(0) = r$. Therefore, where $r$ was selected uniformly at random, so was $i$.


* The cardinality of A is equal to the cardinality of B, so a bijection can exist. There is something interesting here, however. Note that $z:\mathbb{R}(0,1) \rightarrow \mathbb{R}(-r, 1-r)$ is a bijection where $z(x) = x – r$, but $q \in A \Rightarrow z(q) = q - r \notin B$ if $r \notin \mathbb{Q}$ because any rational less an irrational is not rational. I therefore suggest that $\exists k \in A$ such that $f:A \rightarrow B$ is a bijection where $f(a) = a – k$. This poses the question, what is the result $t$ of the equation: $(1/3 – 0) – (f(1/3) – z(0)) = 1/3 – ((1/3 – k) – (0 – r)) = 1/3 – 1/3 + k – r = k – r = t$? What is unusual is that $k - r = t$ must be all but infinitesimal… It is the smallest difference between two disjoint “shifted copies” of the rational numbers in $\mathbb{R}$ \ $\mathbb{Q}$.
AplanisTophet is offline  
December 12th, 2016, 10:42 AM   #14
Senior Member
 
Joined: Aug 2012

Posts: 1,429
Thanks: 352

> after this I'm done

It's ok with me if you can't post till the weekend. But if you're done, that saves me the trouble of responding at all. Are you done or should I take the trouble to read what you wrote and try to respond?

I don't want to flog a dead horse if you've lost interest.

(ps -- minor horse flogging). I'm still confused about your basic idea. Ignoring the details, you randomly select a real $r$ in $(0,1)$. The probability of $r$ is zero. Now you pull back $r$ to uniquely identify a natural number $i$. But then the probability of $i$ is zero. So you haven't got a probability measure because by countable additivity, the probability of $\mathbb N$ is $0$. No matter how you shift around your intervals, I don't see how you are addressing this problem.

I'll spend some time working through the details of your argument but I don't see how anything's changed from my original objection, which is that you assign probability 0 to every natural number. That is indeed a uniform measure; but it's not a uniform probability measure, because it fails to sum to $1$ over the whole space of naturals.

> 7) $\exists i \in \mathbb{N} : f(q_i) = 0 \Rightarrow g(f(q_i) = g(0) = r$. Therefore, where $r$ was selected uniformly at random, so was $i$.

Yes. $i \in \mathbb N$ was selected uniformly at random, based on selecting $r \in \mathbb R$ uniformly at random. However, the selection of a random real in $(0,1)$ is a uniform probability measure; but the selection of a natural in $\mathbb N$ is a uniform measure but not a uniform probability measure, since your measure fails to sum to $1$ across the naturals.

That's because $\sum_{i=1}^\infty 0 = 0$ if we assume countably additivity; but $\int_0^1 dx = 1$. This is a philosophical mystery but it's not a mathematical mystery.

Last edited by Maschke; December 12th, 2016 at 11:19 AM.
Maschke is offline  
December 14th, 2016, 08:57 AM   #15
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 306
Thanks: 21

Quote:
Originally Posted by Maschke View Post
> 7) $\exists i \in \mathbb{N} : f(q_i) = 0 \Rightarrow g(f(q_i) = g(0) = r$. Therefore, where $r$ was selected uniformly at random, so was $i$.

Yes. $i \in \mathbb N$ was selected uniformly at random, based on selecting $r \in \mathbb R$ uniformly at random.
I see a problem still. What about the bijection in step 4? I didn't bother defining it. Each bijection in step 4 for each possible r must be constructively defined prior to selecting r. If we can do that, then I think we've got ourselves a proof.

In glossing over the issue of what set of bijections to use I was erroneously assuming we could simply "shift" to the left by subtracting a rational constant k from each rational in A so that { a - k : a in A } would end up equaling $B_r$ for any given real r in (0,1), but these only work when r is a rational because otherwise we are trying to fit a square peg into a round hole so to speak.

I will keep thinking this over and try to come to some conclusions this weekend still when I have more time. Thanks again Maschke.
AplanisTophet is offline  
December 14th, 2016, 10:04 AM   #16
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 306
Thanks: 21

I know you questioned the use of Vitali sets, but they provide an easy solution to the bijection issue. We can have a constant $k$ that is rational to go from A to $B_r$ whenever r is rational, but since most reals aren't rational, we can use the corresponding v in V (where both v and r in { r + q : q in $\mathbb{Q}$ }) and say instead that $B_r = \mathbb{Q} \cap ( -|v - r|, 1 - |v - r|)$. Then we'll have a guaranteed constant $k$ where f(a) = a - k is a bijection between A and $B_r$ for any r in (0, 1).

With that, I'd say we've got a way of selecting a natural number uniformly at random. Assuming we might not want to use a Vitali set (and the axiom of choice that comes with it), I'm open to any more ideas on how to get our set of predefined bijections.

(I assumed it would take me more time to come up with something like that, but I really will try and refrain until this weekend now, lol)

Last edited by AplanisTophet; December 14th, 2016 at 10:07 AM.
AplanisTophet is offline  
December 14th, 2016, 12:13 PM   #17
Senior Member
 
Joined: Aug 2012

Posts: 1,429
Thanks: 352

You're chasing red herrings. You argument is actually much simpler than all that.

We have a partition of $(0,1)$ into an uncountable collection of countable sets. The sets making up the partition are called cells.

If we randomly choose $p \in (0,1)$, it's in exactly one cell of the partition. That cell is countable. Choosing a bijection, we can map $p$ to some natural number $i$. Therefore $i$ has been uniformly chosen. [Once we "randomly" choose a bijection, a point you haven't explained yet. There are uncountably many bijections from a countable set to the natural numbers, so you haven't really bought yourself anything].

That argument is correct as soon as we know that there's at least one such uncountable partition of countably infinite cells. But the relation $\sim$ induces such a partition so we're done. In this case, each cell is exactly the translation of the rationals by a real

By diving into the details of the $\sim$ relationship you are obscuring the very simple proof that you gave in your original post. The only reason we need $\sim$ is to show that at least one such partition exists. You are confusing yourself with all the shifts. They're irrelevant, as is the exact nature of the partition, as long as there is at least one.

Now, what is the flaw in your thinking? It's true that you have a uniform measure on the natural numbers. Namely, you assign $0$ to every natural number.

However that does not meet the definition of a probability measure, since the probabilities don't sum to $1$.

Don't blame me, blame Andrey Kolmogorov, who gave the axioms of probability measures. He said they have to add to $1$. And after all, that's an extremely natural notion. The sum of the probabilities of head and tails, the faces of a die, the numbers on a roulette wheel all add up to $1$. It's just a definition but it's the one everyone accepts.

https://en.wikipedia.org/wiki/Andrey_Kolmogorov
https://en.wikipedia.org/wiki/Probability_axioms

So: Yes, you have a uniform measure on the naturals that assigns probability $0$ to every natural. However you don't have a probability measure, by the very definition of probability measure.

I've made this point several times already and you don't seem to be engaging with it.

Last edited by Maschke; December 14th, 2016 at 12:20 PM.
Maschke is offline  
December 14th, 2016, 06:39 PM   #18
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 306
Thanks: 21

As always, thank you again Maschke. I’ve learned quite a few things since this started and I really respect your patience and time here. To that end I'm sorry about "chasing red herrings" but this is still short despite the fact that maybe it could be simpler. It's just that I think we must have all possible bijections definable prior to selecting our $r$, so ... um ... sorry ... but I used a Vitali set just to show it can be done rather than just asserting there is a bijection because I'm really not sure how to keep the randomness in tact without the Vitali set at this point. Please bear with me.

1- Let $q_1, q_2, q_3,$ … be an enumeration of $A = \mathbb{Q} \cap [0,1]$.

2- Let $V$ be a Vitali set, which contains one and only one element $v$ from each coset $\{ r + q : q \in \mathbb{Q} \} \in \mathbb{R}/\mathbb{Q}$ such that $0 \leq v \leq 1$.

3- Select a real number $r \in [0,1]$ uniformly at random. Note: A common way of doing this cited by mathematicians is the theoretical flipping of a coin infinitely many times followed by some trivial 'clean-up' given that there are two binary expansions of each dyadic rational, e.g. 0.1 = 0.01111111...

4- Let $v_r \in V \Rightarrow v_r, r \in \{ r + q : q \in \mathbb{Q} \}$.

5- Let $B = \mathbb{Q} \cap [-|v_r-r|, 1-|v_r-r|]$. Note that $v, r \in [0,1] \Rightarrow 0 \in B$. Also note that the length of $[-|v-r|, 0]$ is dependent upon $r$, which was selected uniformly at random, so the length has likewise been selected uniformly at random.

6- Let $f:A \rightarrow B$ be a bijection such that $f(a) = a - |v_r-r|$.

7- Let $C = \{ r + q : q \in B \}$. Note that $0 \in B \Rightarrow r \in C$.

8- Let $g:B \rightarrow C$ be a bijective function: $g(b) = b + r$. Note that $0 \in B \Rightarrow \exists g(0) = r$.

9- $\exists i \in \mathbb{N} : f(q_i) = 0 \Rightarrow g(f(q_i)) = g(0) = r$. Therefore, where $r$ was selected uniformly at random, so was $i$.

PS - Please note that I’ve stated a few times that I realize the probability for each $i \in \mathbb{N}$ is 0. That is a necessary aspect of picking an element of any infinite set uniformly at random. I’ve clarified very precisely what I mean by uniformly at random for this purpose. I expect this to be received no differently than the ability to pick a real in [0, 1] uniformly at random, which is generally accepted by mathematicians as being theoretically possible despite our inability to truly ‘flip a coin’ an infinite number of times. I have never heard of a mathematician acknowledging the ability to select a natural number this way (hence the OP) and always assumed it could not be done for the reasons you give (that the sum of 0’s = 0). I am not about to assert that each natural has some microscopic probability dx or anything, just that we can in theory select a natural uniformly at random given a common sense definition of what that means with respect to any infinite set. I’m happy with that. Fair enough?
AplanisTophet is offline  
December 15th, 2016, 09:19 AM   #19
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 306
Thanks: 21

So I figured it out for real this time. The answer is… da da da daaaa… I’m wrong! (I know, who could have guessed, lol)

Let’s get some statements in here that I believe are actually true to conclude.

1) We cannot define a method for picking a number from $\mathbb{R}$ uniformly at random (which should have been our first clue, as if we could the proof would have been done), only a subset.

2) We bought into the idea that we could have these bijections between $\mathbb{N}$ and each cell of our partition based on the OP, thereby producing a natural number uniformly at random, but I now believe we cannot. That is to say, yes, we can have the bijections, but actually defining them eliminates our ability to keep the selection of a natural as one being chosen uniformly at random. E.g., in my post above, there are only two ways to get $|v_r – r| = 1$ while there are an infinite number of ways to get $|v_r – r| = 1/2$, so the resulting natural that we come up with has not been selected uniformly at random.

Therefore Maschke, in conclusion, I must ask you: Is it possible to actually define the bijections in step 1 of the second part of the OP in a way that preserves our selection of a natural uniformly at random (meaning simply that each natural has an equal chance of being selected using a method where one and only one is selected) and are you willing to try and provide an example? This is my last chance to be wrong, but I believe the answer is a firm “no” at this point.

Also Maschke, despite everything here most likely being rubbish, I really learned a lot as we were going through this. I had no idea what a cell, Vitali set, the partitions $\sim$ you identified, etc., were when we started. I’m obviously a novice mathematician at best but a crank at worst, or at least I would be a crank if I refused to agree that I’m wrong, so maybe there is a little hope for me yet as I’ve learned something in that regard too. The point is that I really enjoyed all this and I very much appreciate what you did. It’s wonderful that you’ll take some time for people ‘like me’ and you certainly deserve some credit for that. Sincerely, thank you.

Last edited by AplanisTophet; December 15th, 2016 at 09:21 AM.
AplanisTophet is offline  
December 15th, 2016, 10:41 AM   #20
Senior Member
 
Joined: Aug 2012

Posts: 1,429
Thanks: 352

I have some issues with things you wrote in your last two posts, which I'll try to clarify later.

For the moment I'm putting aside these concerns and instead I'll offer some perspectives I found regarding putting uniform probability distributions on the naturals. I'll just give the highlights and references, but each of the links I provide is well worth reading in its entirety. I claim no expertise in anything that follows beyond my ability to have Googled it.

* Even Kolmogorov was unhappy about the state of affairs with regard to the natural numbers.

Quote:
It's an obvious and well-known fact that there is no uniform probability measure on a set of natural numbers (i.e. the one that gives the same probability to each singleton). On a recent probability seminar one professor mentioned that this nonexistance is one of the main objections to measure-theoretic formulation of probability and that even Kolmogorov admitted the problem in it.
http://mathoverflow.net/questions/47...et-of-naturals

Mathoverflow is a site for professional mathematicians. This is a relatively readable article but do realize that they are talking about advanced mathematical ideas.


* The consensus among experts is that the best way around the problem is to drop countable additivity, and instead study finitely additive measures. The most widely known finitely additive measure on the naturals is natural density. This is the theory that assigns the even numbers probability $\frac{1}{2}$, etc.

https://en.wikipedia.org/wiki/Natural_density

* I found a research paper where someone worked out a finitely additive measure on the naturals even more general than natural density.

Abstract:

Quote:
In this paper, we address the problem of constructing a uniform probability measure on $\mathbb N$. Of course, this is not possible within the bounds of the Kolmogorov axioms, and we have to violate at least one axiom. We define a probability measure as a finitely additive measure assigning probability 1 to the whole space, on a domain which is closed under complements and finite disjoint unions. We introduce and motivate a notion of uniformity which we call weak thinnability, which is strictly stronger than extension of natural density. We construct a weakly thinnable probability measure, and we show that on its domain, which contains sets without natural density, probability is uniquely determined by weak thinnability. In this sense, we can assign uniform probabilities in a canonical way.
http://link.springer.com/article/10....959-015-0611-2

* People have made a run at this problem (without success) by using the nonstandard reals aka hyperreals. This is a system that satisfies the first-order properties of the real numbers, but that includes infinitesimals (Mathoverflow link)

* There is something in Bayesian probability theory analagous to the Dirac delta function, a "function" that isn't really a function that concentrates all its mass at one point. These are called "improper priors." (Mathoverflow link)

* There is an enlightening discussion thread of this issue on the xkcd math forum. Well worth reading.

http://forums.xkcd.com/viewtopic.php?t=106398
Thanks from AplanisTophet

Last edited by Maschke; December 15th, 2016 at 10:49 AM.
Maschke is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
question, set, theory



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Set Theory Question Mathsisthebestandisamazin Number Theory 7 November 22nd, 2016 04:44 PM
Kalphauer Theory Groundbreaking Theory? Yes or No? Need Help Completing Theory. flextera New Users 0 July 30th, 2014 12:12 PM
Category theory question ipp Abstract Algebra 0 December 8th, 2013 08:39 AM
Graph Theory question 12arte12 Applied Math 0 December 8th, 2013 07:20 AM
Question in Graph Theory mathdude Applied Math 6 November 30th, 2010 01:06 PM





Copyright © 2017 My Math Forum. All rights reserved.