If I make a target, but instead of making it a circle, I make it an immeasurable set, and you throw a dart at it, what’s the probability of hitting the target?
Immeasurable objects are physically impossible. The actual target will be measurable, even if the way you came up with it was to try to follow the “instructions” that describe an immeasurable set.
Hmm. What is the exact length of your, say, pen? Is it a rational number or a real number… I mean the EXACT lengh...?
Note if the answer to the last question is “it is a real number”, then it is possible to construct the bet as proposed by the OP.
Before you quote “Planck’s Length” in your reply, there is currently no directly proven physical significance of the Planck length (at least according to Wikipedia).
For the same reasons you outline above, I’m okay with fighting this hypothetical target.
If I must dignify the hypothesis with a strategy: my “buy” and “sell” prices for such a bet correspond to the inner and outer measures of the target, respectively.
If you construct a set in real life, then you have to have some way of judging whether the dart is “in” or “out”. I reckon that any method you can think of will in fact give a measurable set.
Alternatively, there are several ways of making all sets measurable. One is to reject the Axiom of Choice. The AoC is what’s used to construct immeasurable sets. It’s consistent in ZF without AoC that all sets are Lebesgue measurable.
If you like the Axiom of Choice, then another alternative is to only demand that your probability measure be finitely additive. Then you can give a “measure” (such finitely additive measures are actually called “charges”) such that all sets are measurable. What’s more you can make your probability charge agree with Lebesgue measure on the Lebesgue measurable sets. (I think you need AoC for this though.)
In L.J. Savage’s “The Foundations of Statistics” the axioms of probability are justified from decision theory. He only ever manages to prove that probability should be finitely additive; so maybe it doesn’t have to be countably additive. One bonus of finite additivity for Bayesians is that lots of improper priors become proper. For example, there’s a uniform probability charge on the naturals.
I’ve been thinking about this a bit more. My current thinking is basically what Coscott said:
We only care about probabilities if we can be forced to make a bet.
In order for it to be possible to decide who won the bet, we need that (almost always) a measurement to some finite accuracy will suffice to determine whether the dart is in or out of the set.
Thus the set has a boundary of measure zero.
Thus the set is measurable.
What we have shown is that in any bet we’re actually faced with, the sets involved will be measurable.
(The steps from 2 to 3 and 3 to 4 are left as exercises. (I think you need Lebesgue measurable sets rather than just Borel measurable ones))
Note that the converse fails: I believe you can’t make a bet on whether or not the dart fell on a rational number, even though the rationals are measurable.
Here’s a variant which is slightly different, and perhaps stronger since it also allows some operations with “infinite accuracy”.
In order to decide who won the bet, we need a referee. A natural choice is to say that the referee is a Blum-Shub-Smale machine, i.e. a program that gets a single real number x∈[0,1] as input, and whose operations are: loading real number constants; (exact) addition, substraction, multiplication and division; and branching on whether a≤b (exactly).
Say you win if the machine accepts x in a finite number of steps. Now, I think it’s always the case that the set of numbers which are accepted after n steps is a finite union of (closed or open) intervals. So then the set of numbers that get accepted after any finite number of steps is a countable union of finite unions of intervals, hence Borel.
Immeasurable sets are not something in the real world that you can throw a dart at.
I can rephrase your problem to be:
“If I have an immeasurable set X in the unit interval, [0,1), and I generate a uniform random variable from that interval, what is the probability that that variable is in X?”
The problem is that a “uniform random variable” on a continuous interval is a more complicated concept than you think. Let me explain, by first giving an example where X is measurable, lets say X=[0,pi-3). We analyze random continuous variables by reducing to random discrete variables. We can think of a “uniform random variable” as a sequence of digits in a decimal expansion which are determined by rolling a 10 sided die. So for example, we can roll the die, and get 1,4,6,2,9,..., which would correspond to .14629..., which is not in the set X. Notice that while in principle we might have to roll the die arbitrarily many times, we actually only had to roll the die 3 times in this case, because once we got 1,4,6, we knew the number was too big to be in the set X. We can use this fact that we almost always have to roll the die only a finite number of times to get a definition of the “probability of being in X.” In this case, we know that the probability is between .141 and .142, by considering 3 die rolls, and if we consider more die rolls, we get more accuracy that converges to a single number, pi-3.
Now, let’s look at what goes wrong if X is not measurable. The problem here is that the set is so messy that even if we we know about the first finitely many digits of a random number, we wont be able to tell if the number is in X. This stops us from doing the procedure like above and defining what we mean.
EDIT: I retract the following. The problem with it is that Coscott is arguing that “something in the real world that you can throw a dart at” implies “measurable” and he does this by arguing that all sets which are “something in the real world that you can throw a dart at” have a certain property which implies measurability. My “counterexamples” are measurable sets which fail to have this property, but this is the opposite of what I would need to disprove him. I’d need to find a set with this property that isn’t measurable. In fact, I don’t think there is such a set; I think Coscott is right.
The sets with this property (that you can tell whether your number is in or out after only finitely many dice rolls) are the open sets, not the measurable sets. For example, the set [0,pi-3] is measurable but not open. If the die comes up (1,4,1,5,9,...) then you’ll never know if your number is in or out until you have all the digits. For an even worse example take the rational numbers: they’re measurable (measure zero) but any finite decimal expansion could be leading to a rational or an irrational.
The sets with this property (that you can tell whether your number is in or out after only finitely many dice rolls) are the open sets, not the measurable sets.
That doesn’t seem right to me. Take as my target the open set (0, pi-3). If I keep rolling zeros I’ll never be able to stop. (Edit: I know that the probability of rolling all zeros approaches 0 as the number of die rolls approaches infinity, but I assume that a demon can take over the die and start feeding me all zeros, or the digits of pi-3 or whatever. As I think about this more I’m thinking maybe what you said works if there is no demon. Edit 2: Or not. If there’s no demon and my first digit is 0 then I can stop, but that’s only because 0 is expressible as an integer divided by a power of ten. If there’s no demon and I roll the first few digits of pi-3, I know that I’ll eventually go over or under pi-3, but I don’t know which, and it doesn’t matter whether pi-3 itself is in my target set.)
Every die roll tells me that the random number I’m generating lies in the closed interval [x, x+1/10^n], where x is the decimal expansion I’ve generated so far and n is how many digits I’ve generated. If at some point I start rolling all 0s or all 9s I’ll be rolling forever if the number I’m generating is a limit point of the target set, even if it’s not in the target set.
I should have been more accurate and said “If the random number that you’ll eventually get does in fact lie in the set, then you’ll find out about this fact after a finite number of rolls.”
This really does define open sets, since for any point in an open set there’s an open ball of radius epsilon about it which is in the set, and then the interval [x, x+1/10^n] has to be in that ball once 1/10^n < epsilon/2.
EDIT: (and the converse also holds, I think, but it requires some painfully careful thinking because of the non-uniqueness of decimal expansions)
I think a more exact representation of what Coscott actually said is the following property: “We almost always only have to roll the die finitely many times to determine whether the point is in or out.”
This still doesn’t specify measurable sets (because of the counterexample given by the rationals). I think the type of set that this defines is “Sets with boundary of measure zero” where the boundary is the closure minus the interior. Note that the rationals in [0,1) have boundary everywhere (i.e. boundary of measure 1).
Ah, so if my target set is (0, pi-3) and the demon feeds me the digits of pi-3, I will be rolling forever, but if the demon feeds me the digits of pi-3-epsilon (or any other number in (0, pi-3)) I will be able to stop after a finite amount of rolls.
I think the type of set that this defines is “Sets with boundary of measure zero” where the boundary is the closure minus the interior.
That sounds right to me, although I don’t understand measure very well. I was informally thinking of this property as “continuousness”.
Yeah, but I can’t explain explain that without analysis not appropriate for a less wrong post. I remember that the probability class I took in undergrad dodged the measure theory questions by defining probabilities on open sets, which actually works for most reasonable questions. I think such a simplification is appropriate, but I should have had a disclaimer.
Thanks! I think it’s quite reasonable to reject choice and take as an axiom that all sets are measurable, so I’m interested in the consequences of it. I’d always been told that the continuum hypothesis is orthogonal to everything people care about, but that’s only after assuming choice.
There’s also the Axiom of Determinacy that rejects Choice and, when paired with the existence of a very strong measurable cardinal, gives a very broad class of measurable sets.
Could you give an example of a set whose measurability I might care about, other than subsets of R?
something for random processes?
Well, I guess this pretty much depends on the area you’re working on. I’m interested in the foundation of mathematics, for which measurable sets are of big importance (for example, they are the smallest critical point of embedding of transitive models, or they are the smallest large cardinal property that cannot be shown to exists inside the smallest inner model). Outside of that area, I guess the interest is all about R and descriptive set theory.
Edit: It’s not true that measurable cardinals are the smallest large cardinals that do not exists in L. Technically, the consistency strength is called 0#, and between that and measurables there are Ramsey cardinals.
Could you give a reference for the combination?
Well, the definitive source is Kanamori’s book “The higher infinite”, but it’s advanced. Some interesting things can be scooped up from Wikipedia’s entry about the axiom of determinacy.
That doesn’t actually answer Douglas’s statement that the continuum hypothesis is orthogonal to everything people care about if one assumes choice. In fact Doug’s statement is more or less correct. See in particular discussion here. In particular, ZF + CH implies choice for sets of real numbers, which is what we care about for most practical purposes.
A comment at your link baldly asserts that ZF+CH implies choice for sets of real numbers, but the link seems otherwise irrelevant. Do you have a better citation? In particular, what do you mean by CH without choice? In fact, the comment asserts that ZF+CH implies R is well-orderable, which I don’t think is true under weaker notions of CH.
In particular, what do you mean by CH without choice?
CH in that context then is just that there are no sets of cardinality between that of R and N. You can’t phrase it in terms of alephs (since without choice alephs aren’t necessarily well-defined). As for a citation, I think Caicedo’s argument here can be adopted to prove the statement in question.
I said that I doubt your claim, so blog posts proving different things aren’t very convincing. Maybe I’m confused by the difference between choice and well-ordering, but imprecise sources aren’t going to clear that up.
In fact, it was Caicedo’s post that lead me to doubt Buie. Everything Caicedo says is local. In particular, he says that CH(S) and CH(2^S) imply that S is well-orderable. Buie makes a stronger specific claim that CH implies R is well-orderable, which sounds like a stronger specific claim, unlikely to be proved by local methods. I guess it is not exactly stronger, though, because the hypothesis is a little different (CH=CH(N), not CH(R)).
Alephs are defined without choice. They are bijective equivalence classes of ordinals. In any event, ℵ_1 is the union of countable ordinals. Sometimes they are called cardinals.
It is widely reported that the (weak) CH is the that every uncountable subset of the reals is bijective with the reals, while strong CH is that the reals are bijective with ℵ_1. I think you and Buie are simply confusing the two statements.
Also, sometimes people use “weak continuum hypothesis” to mean 2^ℵ_0 < 2^ℵ_1; I think it is strictly weaker than the statement that there are no sets between ℵ_0 and 2^ℵ_0.
Hmm, that does make it seem like I may be confused here. Possible repaired statement would then use GCH in some form rather than just CH and that should go through then since GCH will imply that for all infinite S, CH(S) and CH(2^S), which will allow one to use Caicedo’s argument. Does that at least go through?
It is widely reported that the (weak) CH is the that every uncountable subset of the reals is bijective with the reals, while strong CH is that the reals are bijective with ℵ_1. I think you and Buie are simply confusing the two statements.
Yes, Caicedo mentions that GCH implies AC. This is a theorem of Siepinski, who proved it locally. Specker strengthened the local statement to CH(S)+CH(2^S) ⇒ S is well-orderable. It is open whether CH(S) ⇒ S is well-orderable.
Ok. That makes sense. I think we’re on the same page then now, and you are correct that Buie and I were confuse about the precise version of the statements in question.
If I make a target, but instead of making it a circle, I make it an immeasurable set, and you throw a dart at it, what’s the probability of hitting the target?
In other words, “what is the measure of an unmeasurable set?”. The question is wrong.
I suppose the question is: What should you do if you’re offered a bet on whether the dart will hit the target or not?
There’s no way to avoid the question other than arguing somehow that you’ll never encounter an immeasurable set.
I’ll never encounter an immeasurable set.
Immeasurable objects are physically impossible. The actual target will be measurable, even if the way you came up with it was to try to follow the “instructions” that describe an immeasurable set.
Hmm. What is the exact length of your, say, pen? Is it a rational number or a real number… I mean the EXACT lengh...?
Note if the answer to the last question is “it is a real number”, then it is possible to construct the bet as proposed by the OP.
Before you quote “Planck’s Length” in your reply, there is currently no directly proven physical significance of the Planck length (at least according to Wikipedia).
For the same reasons you outline above, I’m okay with fighting this hypothetical target.
If I must dignify the hypothesis with a strategy: my “buy” and “sell” prices for such a bet correspond to the inner and outer measures of the target, respectively.
If you construct a set in real life, then you have to have some way of judging whether the dart is “in” or “out”. I reckon that any method you can think of will in fact give a measurable set.
Alternatively, there are several ways of making all sets measurable. One is to reject the Axiom of Choice. The AoC is what’s used to construct immeasurable sets. It’s consistent in ZF without AoC that all sets are Lebesgue measurable.
If you like the Axiom of Choice, then another alternative is to only demand that your probability measure be finitely additive. Then you can give a “measure” (such finitely additive measures are actually called “charges”) such that all sets are measurable. What’s more you can make your probability charge agree with Lebesgue measure on the Lebesgue measurable sets. (I think you need AoC for this though.)
In L.J. Savage’s “The Foundations of Statistics” the axioms of probability are justified from decision theory. He only ever manages to prove that probability should be finitely additive; so maybe it doesn’t have to be countably additive. One bonus of finite additivity for Bayesians is that lots of improper priors become proper. For example, there’s a uniform probability charge on the naturals.
I’ve been thinking about this a bit more. My current thinking is basically what Coscott said:
We only care about probabilities if we can be forced to make a bet.
In order for it to be possible to decide who won the bet, we need that (almost always) a measurement to some finite accuracy will suffice to determine whether the dart is in or out of the set.
Thus the set has a boundary of measure zero.
Thus the set is measurable.
What we have shown is that in any bet we’re actually faced with, the sets involved will be measurable.
(The steps from 2 to 3 and 3 to 4 are left as exercises. (I think you need Lebesgue measurable sets rather than just Borel measurable ones))
Note that the converse fails: I believe you can’t make a bet on whether or not the dart fell on a rational number, even though the rationals are measurable.
Here’s a variant which is slightly different, and perhaps stronger since it also allows some operations with “infinite accuracy”.
In order to decide who won the bet, we need a referee. A natural choice is to say that the referee is a Blum-Shub-Smale machine, i.e. a program that gets a single real number x∈[0,1] as input, and whose operations are: loading real number constants; (exact) addition, substraction, multiplication and division; and branching on whether a≤b (exactly).
Say you win if the machine accepts x in a finite number of steps. Now, I think it’s always the case that the set of numbers which are accepted after n steps is a finite union of (closed or open) intervals. So then the set of numbers that get accepted after any finite number of steps is a countable union of finite unions of intervals, hence Borel.
Immeasurable sets are not something in the real world that you can throw a dart at.
I can rephrase your problem to be: “If I have an immeasurable set X in the unit interval, [0,1), and I generate a uniform random variable from that interval, what is the probability that that variable is in X?”
The problem is that a “uniform random variable” on a continuous interval is a more complicated concept than you think. Let me explain, by first giving an example where X is measurable, lets say X=[0,pi-3). We analyze random continuous variables by reducing to random discrete variables. We can think of a “uniform random variable” as a sequence of digits in a decimal expansion which are determined by rolling a 10 sided die. So for example, we can roll the die, and get 1,4,6,2,9,..., which would correspond to .14629..., which is not in the set X. Notice that while in principle we might have to roll the die arbitrarily many times, we actually only had to roll the die 3 times in this case, because once we got 1,4,6, we knew the number was too big to be in the set X. We can use this fact that we almost always have to roll the die only a finite number of times to get a definition of the “probability of being in X.” In this case, we know that the probability is between .141 and .142, by considering 3 die rolls, and if we consider more die rolls, we get more accuracy that converges to a single number, pi-3.
Now, let’s look at what goes wrong if X is not measurable. The problem here is that the set is so messy that even if we we know about the first finitely many digits of a random number, we wont be able to tell if the number is in X. This stops us from doing the procedure like above and defining what we mean.
Is this clear?
EDIT: I retract the following. The problem with it is that Coscott is arguing that “something in the real world that you can throw a dart at” implies “measurable” and he does this by arguing that all sets which are “something in the real world that you can throw a dart at” have a certain property which implies measurability. My “counterexamples” are measurable sets which fail to have this property, but this is the opposite of what I would need to disprove him. I’d need to find a set with this property that isn’t measurable. In fact, I don’t think there is such a set; I think Coscott is right.
The sets with this property (that you can tell whether your number is in or out after only finitely many dice rolls) are the open sets, not the measurable sets. For example, the set [0,pi-3] is measurable but not open. If the die comes up (1,4,1,5,9,...) then you’ll never know if your number is in or out until you have all the digits. For an even worse example take the rational numbers: they’re measurable (measure zero) but any finite decimal expansion could be leading to a rational or an irrational.
That doesn’t seem right to me. Take as my target the open set (0, pi-3). If I keep rolling zeros I’ll never be able to stop. (Edit: I know that the probability of rolling all zeros approaches 0 as the number of die rolls approaches infinity, but I assume that a demon can take over the die and start feeding me all zeros, or the digits of pi-3 or whatever. As I think about this more I’m thinking maybe what you said works if there is no demon. Edit 2: Or not. If there’s no demon and my first digit is 0 then I can stop, but that’s only because 0 is expressible as an integer divided by a power of ten. If there’s no demon and I roll the first few digits of pi-3, I know that I’ll eventually go over or under pi-3, but I don’t know which, and it doesn’t matter whether pi-3 itself is in my target set.)
Every die roll tells me that the random number I’m generating lies in the closed interval [x, x+1/10^n], where x is the decimal expansion I’ve generated so far and n is how many digits I’ve generated. If at some point I start rolling all 0s or all 9s I’ll be rolling forever if the number I’m generating is a limit point of the target set, even if it’s not in the target set.
I should have been more accurate and said “If the random number that you’ll eventually get does in fact lie in the set, then you’ll find out about this fact after a finite number of rolls.”
This really does define open sets, since for any point in an open set there’s an open ball of radius epsilon about it which is in the set, and then the interval [x, x+1/10^n] has to be in that ball once 1/10^n < epsilon/2.
EDIT: (and the converse also holds, I think, but it requires some painfully careful thinking because of the non-uniqueness of decimal expansions)
I think a more exact representation of what Coscott actually said is the following property: “We almost always only have to roll the die finitely many times to determine whether the point is in or out.”
This still doesn’t specify measurable sets (because of the counterexample given by the rationals). I think the type of set that this defines is “Sets with boundary of measure zero” where the boundary is the closure minus the interior. Note that the rationals in [0,1) have boundary everywhere (i.e. boundary of measure 1).
Ah, so if my target set is (0, pi-3) and the demon feeds me the digits of pi-3, I will be rolling forever, but if the demon feeds me the digits of pi-3-epsilon (or any other number in (0, pi-3)) I will be able to stop after a finite amount of rolls.
That sounds right to me, although I don’t understand measure very well. I was informally thinking of this property as “continuousness”.
Yeah, but I can’t explain explain that without analysis not appropriate for a less wrong post. I remember that the probability class I took in undergrad dodged the measure theory questions by defining probabilities on open sets, which actually works for most reasonable questions. I think such a simplification is appropriate, but I should have had a disclaimer.
What Quinn said.
Throwing darts at immeasurable set was a technique used to ‘prove’ the continuum hypothesis.
Could you give a reference? Are you assuming choice?
Sorry, it was used to ‘disprove’ the continuum hypothesis.
It’s the Freiling axiom.
Thanks! I think it’s quite reasonable to reject choice and take as an axiom that all sets are measurable, so I’m interested in the consequences of it. I’d always been told that the continuum hypothesis is orthogonal to everything people care about, but that’s only after assuming choice.
There’s also the Axiom of Determinacy that rejects Choice and, when paired with the existence of a very strong measurable cardinal, gives a very broad class of measurable sets.
Could you give an example of a set whose measurability I might care about, other than subsets of R? something for random processes?
Could you give a reference for the combination?
Well, I guess this pretty much depends on the area you’re working on. I’m interested in the foundation of mathematics, for which measurable sets are of big importance (for example, they are the smallest critical point of embedding of transitive models, or they are the smallest large cardinal property that cannot be shown to exists inside the smallest inner model). Outside of that area, I guess the interest is all about R and descriptive set theory.
Edit: It’s not true that measurable cardinals are the smallest large cardinals that do not exists in L. Technically, the consistency strength is called 0#, and between that and measurables there are Ramsey cardinals.
Well, the definitive source is Kanamori’s book “The higher infinite”, but it’s advanced. Some interesting things can be scooped up from Wikipedia’s entry about the axiom of determinacy.
CH is orthogonal to ZF. CH is orthogonal to ZFC.
If ZFC is inconsistent, then ZF is also inconsistent.
AC is orthogonal to CH.
That doesn’t actually answer Douglas’s statement that the continuum hypothesis is orthogonal to everything people care about if one assumes choice. In fact Doug’s statement is more or less correct. See in particular discussion here. In particular, ZF + CH implies choice for sets of real numbers, which is what we care about for most practical purposes.
A comment at your link baldly asserts that ZF+CH implies choice for sets of real numbers, but the link seems otherwise irrelevant. Do you have a better citation? In particular, what do you mean by CH without choice? In fact, the comment asserts that ZF+CH implies R is well-orderable, which I don’t think is true under weaker notions of CH.
CH in that context then is just that there are no sets of cardinality between that of R and N. You can’t phrase it in terms of alephs (since without choice alephs aren’t necessarily well-defined). As for a citation, I think Caicedo’s argument here can be adopted to prove the statement in question.
I said that I doubt your claim, so blog posts proving different things aren’t very convincing. Maybe I’m confused by the difference between choice and well-ordering, but imprecise sources aren’t going to clear that up.
In fact, it was Caicedo’s post that lead me to doubt Buie. Everything Caicedo says is local. In particular, he says that CH(S) and CH(2^S) imply that S is well-orderable. Buie makes a stronger specific claim that CH implies R is well-orderable, which sounds like a stronger specific claim, unlikely to be proved by local methods. I guess it is not exactly stronger, though, because the hypothesis is a little different (CH=CH(N), not CH(R)).
Alephs are defined without choice. They are bijective equivalence classes of ordinals. In any event, ℵ_1 is the union of countable ordinals. Sometimes they are called cardinals.
It is widely reported that the (weak) CH is the that every uncountable subset of the reals is bijective with the reals, while strong CH is that the reals are bijective with ℵ_1. I think you and Buie are simply confusing the two statements.
Also, sometimes people use “weak continuum hypothesis” to mean 2^ℵ_0 < 2^ℵ_1; I think it is strictly weaker than the statement that there are no sets between ℵ_0 and 2^ℵ_0.
Hmm, that does make it seem like I may be confused here. Possible repaired statement would then use GCH in some form rather than just CH and that should go through then since GCH will imply that for all infinite S, CH(S) and CH(2^S), which will allow one to use Caicedo’s argument. Does that at least go through?
I think you are likely correct here.
Yes, Caicedo mentions that GCH implies AC. This is a theorem of Siepinski, who proved it locally. Specker strengthened the local statement to CH(S)+CH(2^S) ⇒ S is well-orderable. It is open whether CH(S) ⇒ S is well-orderable.
Ok. That makes sense. I think we’re on the same page then now, and you are correct that Buie and I were confuse about the precise version of the statements in question.