December 9th, 2016, 07:49 PM  #1 
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Set Theory Question
Is it possible for a set A to exist where: 1) all elements of A have a cardinality equal to that of the natural numbers and 2) the set A is a partition of the set of real numbers greater than 0 and less than 1 (meaning the union of the sets in A is equal to the set of reals greater than 0 and less than 1, the intersection of any two distinct sets in A is empty, and trivially A does not contain the empty set given condition 1 above)? I believe no. My reasoning is as follows. 1) For each element of A, let there exist a bijection between it and the set of natural numbers. 2) Select a real on the interval (0,1) uniformly at random (this of course assumes one could carry out an operation where, for example, a coin is flipped an infinite number of times along with a trivial bit of ‘clean up’ given there are two binary expansions for all dyadic rationals in the interval, e.g. 0.1 = 0.0111111…). Call this real p. 3) The real number p is an element of one and only one set in A by definition of A. Let Z be the element of A that contains p. 4) There is a bijection between the set of natural numbers and the set Z from step 1. Call it function f. There in turn exists a natural number n such that f(n) = p. 5) The natural number n would therefore have also been selected uniformly at random, which is (or has been proven) impossible. Does this seem correct? Thank you in advance! 
December 9th, 2016, 08:36 PM  #2 
Senior Member Joined: Sep 2015 From: Southern California, USA Posts: 1,512 Thanks: 761 
The countable union of countable sets is countable. https://proofwiki.org/wiki/Countable...s_is_Countable $(0,1)$ is not countable. So there is no way you are going to completely cover $(0,1)$ the union of your sets. 
December 9th, 2016, 08:52 PM  #3  
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Quote:
 
December 10th, 2016, 06:09 AM  #4  
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Quote:
Below I'll create a set that fails to be a partition as requested above, but that otherwise is exactly what I want to create. You'll note that the set I create is uncountable, just like the set A would be, but that each element of the set is countable. Let x be any real in the interval (0,1). Let g(x) be equal to a set containing x, 0.0x, 0.1x, 0.01x, 0.[each dyadic rational >0 & <1][followed by x], ... (this is possible because the dyadic rationals may be put into a countably infinite list). For example, if x = 0.1100110011..., then g(x) = { x, 0.01100110011..., 0.11100110011..., 0.011100110011..., ... } The above is flawed in terms of what I want the set A to be because { g(x) : x is in (0,1) } is not a partition of the set of reals in (0,1). I want to do something similar, but ensure that the resulting set is in fact a partition meeting the specifications of the set A. Again, I do not think it is possible, because it would allow one in theory to select a natural number uniformly at random as explained in the OP. I hope this helps elaborate. I really appreciate any more feedback. Last edited by AplanisTophet; December 10th, 2016 at 06:19 AM.  
December 10th, 2016, 09:06 AM  #5 
Senior Member Joined: Sep 2015 From: Southern California, USA Posts: 1,512 Thanks: 761 
how about this $\forall x \in (0,1)$ form the countably infinite set of $x$ repeated infinitely. take the set of all these repeated sequences. each element is countably infinite the intersection of the sequences is the emtpy set as each real number is distinct the union will cover $(0,1)$ as you've chosen every real from this interval I'm just not sure it's valid to index these sequences with a real number. Maybe parameterize would be a better term. 
December 10th, 2016, 11:05 AM  #6 
Senior Member Joined: Aug 2012 Posts: 1,575 Thanks: 380 
The equivalence relation $x \sim y$ if $x  y \in \mathbb Q$ induces such a partition. This is a standard example. It's the first part of the construction of a nonmeasurable set. https://en.wikipedia.org/wiki/Vitali_set It's sufficient to note that $\sim$ is an equivalence relation (convince yourself this is true). Every equivalence relation induces a partition so we're done. It's clear that each equivalence class must be countable, since $\mathbb Q$ is one class and every other class is in bijection with $\mathbb Q$ (also needs proof). So there must be uncountably many classes. https://en.wikipedia.org/wiki/Equiva...ence_relations I'm not sure why this doesn't give a way of uniformly selecting a random natural number as you suggest. But since the probability of choosing any particular $p \in (0,1)$ is $0$, the probability of selecting any particular natural number using this method is also $0$; and by countable additivity, the chance of picking any natural number at all is $0$. So this is not a probability measure on $\mathbb N$, since a probability measure must assign $1$ to the entire set. Perhaps that's the answer to this mystery. It's not entirely surprising that we get a probability paradox here, since as I mentioned, this example is the first step in constructing a set of reals that can not be assigned any probability at all. (ps) The rest of the construction of the Vitali set goes as follows. Given the partition induced by $\sim$, use the Axiom of Choice to form a set $V$ (for Giuseppe Vitali) that contains exactly one element from each equivalence class. Now show that the translations of $V$ (that is, the collection of sets $V + r$ for $r \in \mathbb R$, with addition mod $1$) is a partition of $(0,1)$ into a countable collection of uncountable sets. Therefore we can apply countable additivity. If the measure of $V$ is $0$, then by countable additivity the measure of $(0,1)$ must be $0$, which is false. Likewise if the measure of $V$ is positive, the measure of $(0,1)$ must be infinite, which is likewise false. Therefore $V$ can not possibly be assigned a measure or probability, if our measure is required to be translation invariant and assign $1$ to the unit interval. Last edited by Maschke; December 10th, 2016 at 11:22 AM. 
December 10th, 2016, 09:55 PM  #7  
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21  Quote:
As cited below, mathematicians tend to accept the possibility of selecting an element of [0,1] uniformly at random despite the probability of selecting any given element being 0. They then turn around and use that same logic to assert that no natural number can be selected uniformly at random. This is seemingly inconsistent. The ‘true definition’ of selecting an element of a set uniformly at random simply means that each element of the set has an equal chance of being selected based on a process that selects one and only one element of the set. In the case of any infinite set, is it crankery to assert that no element can be selected uniformly at random simply because we cannot calculate the probability of selecting any given element and proceed to sum the values of a probability mass function to 1? I suggest that the true definition of selecting an element of a set uniformly at random given above is appropriate for all sets while the outcome of a probability mass function providing values that sum to 1 is merely a consequence of dealing with finite sets that should not be used to hinder our application of probability to infinite sets. The following is therefore a method by which we are guaranteed in theory to generate a natural number uniformly at random: 1 Let $D = \mathbb{Q} \cap \left[1, 1\right]$. 2 Let $B = q_1, q_2, q_3, …$ be an enumeration of $D$. 3 Define a coset of $\mathbb{Q}$ in $\mathbb{R}$ as any set of the form $x + \mathbb{Q} = \{ x + q : q \in \mathbb{Q} \}$ where $x$ is in $\mathbb{R}$ (Reference, see here). 4 Let $V$ be a Vitali set (a subset $V$ of the interval [0,1] containing a single point from each coset of $\mathbb{Q}$ in $\mathbb{R}$ as referenced here). Note that the axiom of choice is required to construct such a set $V$, which is a nonmeasurable set, as was proven by Robert Solovay in 1970 (see here  i.e., he proved that the statement “every subset of the reals is Lebesgue measurable” is consistent with the ZF axioms of set theory). 5 Let $A = \bigcup_{k = 1}^\infty \left(q_k + V\right)$, where $q_k \in B$. Note that [0,1] is a subset of $A$. To prove this, let $x$ be in [0,1]. Since $V$ is a Vitali set, there exists a $v \in V$ such that $v \in x + \mathbb{Q}$ and as a result $v = x + q$ for some $q \in \mathbb{Q}$. Where $v$ and $x$ both lie in [0,1], it follows that $q = v – x$ lies in [1,1]. Thus, $q \in D$ and $x \in q + V$, which proves that $x \in A$. (Reference  This was adapted from Lemma 4 on page 4, here). 6 Assume that the real number $x$ from step 5 above is selected uniformly at random from the interval [0,1]. Note – see here: “…if we limit ourselves to the real numbers that are between 0 and 1, we can assign a uniform distribution to these numbers which will give them each an equal probability.” 7 Where $q$ lies in [1,1] if $q = v – x$ per step 5 above, there exists an element $q_k$ of $B$ such that $q_k = q$. 8 The natural number $k$ such that $q_k = q$ has therefore also been selected uniformly at random. This contradicts what is generally understood (see here, the same source that said it was possible to select an element of [0,1] uniformly at random – “…but can we define a probability distribution on the set of integers (rather than the real numbers between 0 and 1) such that they each occur with equal probability (i.e. does a uniform distribution on the integers exist)? The answer, sadly, is no. A probability mass function (which is the kind of probability distribution we need in this case) is defined to be a positive function that has a sum of values equal to 1. But any positive function that assigns an equal value to each integer must have probabilities that sum to either infinity or zero, so the desired distribution is impossible to construct.” A wellknown criticism of the axiom of choice is that it allows mathematicians to establish the existence of an object despite not having to explicitly define the object. Proving the existence of a subset of the real numbers that is not Lebesgue measurable is an example of such criticism given that it is consistent that such a set is not definable. I suggest that the ability to select a natural number uniformly at random is simply another odd result obtained via an application of the axiom of choice that is no more counterintuitive than the BanachTarski paradox. This assumes that a means of generating a suitable partition of $\mathbb{R}$ for this proof requires application of the axiom of choice, as is the case with any Vitali set. Perhaps there is another way to create such a partition without using the axiom of choice. Proof of whether or not the axiom of choice is required to create a partition of [0,1] with an uncountable number of countably infinite elements may be something to be desired given this result. Finally, a bit of humor (as I realize I might be getting a little ahead of myself here): Shall we call this the BKMaschke method assuming it is seen as a ‘legitimate’ way of selecting a natural number uniformly at random? Maschke simply saw this as paradoxical, so in that case we can call this the BKMaschke Paradox instead? Ok, in all seriousness, thank you again for your thoughts on this.  
December 10th, 2016, 10:27 PM  #8 
Senior Member Joined: Aug 2012 Posts: 1,575 Thanks: 380 
I haven't gone through that yet but I wanted to make a couple of comments. * First, since it's known that there is uniform probability measure on $\mathbb N$; and it's known that the partition induced by $\sim$ (as defined earlier) exists; then there must be something wrong with your idea. However although I outlined an argument as to what's wrong with your idea, I wasn't fully convinced and I've been thinking about it a bit. If I come to any conclusions I'll post them. It does seem like your method will assign a probability of $0$ to each natural number, but I haven't got the formal proof yet. * Secondly I am not sure why you're now using the Vitali set. I only threw that in for completeness and because it's such a cool example. My thinking was that the $\sim$ partition is only one example, but we have to approach the problem in generality, considering some arbitrary partition into uncountably many sets, each of which is countable. It seems like it might be a dead end or confusing direction to use $V$, which gives us a countable partition of uncountable sets. That's kind of changing the subject so I'm confused by what you're doing. (Without having read it yet, so take that into consideration). * The core mystery is how you add up infinitely many zeros to get one. We can teach the freshman calculus students that $\int_0^1 dx = 1$ but no physicist or mathematician or philosopher can truly explain it. Is this the kind of thing you're thinking about? * Also one more thing that's bothering me. I'm not an expert on probability. When we put a uniform distribution on the real line, the "reasonable" thing to do with it is say things like, "A random dart will land in $(0, \frac{1}{3})$ with probability $\frac{1}{3}$. That's sane, we all believe it. But once we try to reason about hitting particular points, which each have probability zero, we get in trouble. I'm sure the probability theorists must have thought about this and have an answer. Just some thoughts before I take a look at your post in detail. Last edited by Maschke; December 10th, 2016 at 10:35 PM. 
December 11th, 2016, 12:16 AM  #9  
Senior Member Joined: Aug 2012 Posts: 1,575 Thanks: 380 
I have some detailed comments. I hope it's ok if I just let 'er rip with my thoughts and reactions, rather than having to sugar coat anything. In other words even if I seem critical, it's because I'm trying to understand your ideas. In general I can't tell if you're trying to understand some math or grinding an axe of some sort. I'll provide details as I go. Quote:
Quote:
Quote:
Therefore our task at hand is to figure out why your clever argument is wrong. That's what I'm trying to do. If on the other hand you are trying to show that "math is wrong" or whatever, this is not going to be a productive way to go. I hope you will trust me on this. Now you are about to go into a convoluted and incomplete construction of the Vitali set, for no particular reason. Right here, you are working with $[1,1]$ as a means, I am guessing, of avoiding having to define addition mod 1. That's nonstandard and a little confusing. Quote:
Why are you referencing that particular paper? Is it from your class, or is it something you found randomly? Your exposition here is extremely off the mark since the conversation we're having does not require the construction of the Vitali set. I wish you'd explain why you're doing this. Quote:
Quote:
Quote:
That's all pretty clear. As I say I am pretty sure that doesn't work for the reasons I've outlined earlier, and I'm working to formulate a sharper argument. But I don't see why you are invoking the Vitali set, nor why it's needed for your example. So I'm really glazing over on all this exposition that you've copy/pasted from some paper. Quote:
As I say I'm working with my understanding of this problem, which is that we can seemingly induce this mystery distribution using just the original $\sim$ partition. I do not see the relevance of the Vitali set; and I am a little frustrated by the copy/pasting/adapting from that mystery paper. Quote:
All well and good, I enjoy talking about the various philosophies of math. But here we are trying to understand why your argument doesn't work. Intuitionist axe grinding isn't going to help. Quote:
Quote:
We have already constructed such a partition, namely $\sim$ as defined earlier. That equivalence relation immediately gives us an uncountable partition into countable sets. That's all you need to induce your seeming uniform distribution on the naturals. This has nothing at all to do with the Vitali set; and you don't need Choice to define $\sim$. And you don't need Choice to show that there's no uniform distribution on the naturals. That's a consequence of assuming that a probability measure is countably additive. To sum up, the problem here is to explain why $\sim$ doesn't give us a means to define a thing that can't exist, namely a uniform probability measure on the naturals. You have introduced a mathematical red herring, the Vitali set, which is irrelevant to the discussion. And you have introduced some philosophical red herrings by taking first a finitistic stance, then a definability stance, and here and there an antiChoice stance. All these things are distractions from what I think is a very interesting problem: To understand why your clever idea doesn't work. That's how I see all this. I'm just trying to understand why you started copy/pasting the proof of the Vitali set and objecting to the Axiom of Choice and undefinable sets. Your original argument was already clear, and this most recent post very unclear. Hope all this comes across as, if not exactly constructive criticism, at least the result of a good faith attempt by me to read what you wrote and to share my reactions. It would be fair to say that my fundamental orientation is that you didn't break math, and therefore we need to find the flaw in your argument. Last edited by Maschke; December 11th, 2016 at 12:28 AM.  
December 11th, 2016, 06:30 AM  #10 
Senior Member Joined: Jun 2014 From: USA Posts: 308 Thanks: 21 
Thank you again Maschke. I assure you that I find your comments constructive and well reasoned. If anything I just appreciate you taking the time and further I feel that ignoring what you've wrote is a path to crankery. I also have no axe grind nor am I trying to break math, so where you are keeping me grounded in reality here, perhaps its ok for me to try and push the envelope a little noting I won't get very far if things don't 'add up' (pun intended). I see what you mean about how the Vitali set is not a necessity given that we could do a similar proof merely with ~ as you defined earlier. I used it because, assuming I'm not mistaken, choice is needed to create the uncountable number of bijections between the natural numbers and each of the elements of A (see #1 of the second part of the OP). If I was using choice anyways, then the Vitali set allows for a simple construction of the proof and the same general criticism regarding the axiom of choice is applicable regardless (that it allows us to prove the existence of things, in this case an uncountable number of bijections, without actually defining them). I think the main issue here has to do with what we can perhaps more appropriately call my layman's definition of selecting an element of a set uniformly at random. I see two fundamental requirements of such a selection: 1) each element of the set must have an equal chance of being selected given a method of selection and 2) that one and only one element of the set is guaranteed to be selected given the method of selection. What we might call the "formal definition" of discrete uniform distribution requires that "a finite number of values are equally likely to be observed." The continuous uniform distribution that is used for infinite sets is only relative in the sense that our random variable $r$ has a 100% chance of being selected from the interval [0,1], but it says nothing of the probability of selecting any given $r$. Where a discrete uniform distribution and a continuous uniform distribution don't apply, then I'll leave you with this question Maschke: What is the proper way to define the term 'selecting an element of an infinite set uniformly at random?' I believe you have only two options. The first is to assert that the definition of a discrete uniform distribution excludes the possibility of picking from an infinite number of values and move on entirely. The second is to entertain the possibility of selecting an element of an infinite set uniformly at random by accepting that, where no equation 1/x may be used to compute the probability of selecting any given element, the standard definition of a discrete uniform distribution used for probability isn't applicable. In accepting an applicable definition of what it means to select an element of an infinite set uniformly at random, I in no way think we break math. That is to say, I don't think we violate the definition of a discrete uniform distribution because it only applies to finite sets. I question why we can select an element of [0,1] uniformly at random despite the probability of selecting any given element of the interval being 0 while being simultaneously unable to select a natural number uniformly at random because the probability of selecting any given natural is 0. If you can explain that, I'm all ears. Perhaps there is some sort of actual proof that states why you cannot select a natural number uniformly at random. I believe there is, or at least that's what has been ingrained, but I'm not sure where to find it. That would be a good place to turn. I sincerely hope that the logic isn't simply that the probability of selecting any given natural number is 0, therefore it can't be done. If that's the only 'proof,' then I strongly suggest we adopt my layman's definition above for purposes of making a discrete variable selection uniformly at random from any given infinite set. At this point I'll take a break and step back from this for a time I've got a busy week ahead of me. I look forward to any more of your feedback Maschke (or anyone else's too for that matter). I'll refrain from posting any more of my thoughts again until at least next weekend and see if something else comes to mind. Thank you again. 

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 