In a common model, probability theory assigns a number between zero and one to events. But some events cannot be assigned a probability, even zero. Nobody understands probability, in some sense.
This post is not about economics, although these ideas do have an application in mainstream economics. It is not at all novel. This is one of my favorite proofs in all of math, typically taught sometimes after an introductory mathematical analysis class. My undergraduate class in probability and statistics only alluded to measure theory.
2.0 An Introduction to Probability and a OverviewSuppose one has some sort of repeatable experiment, like rolling a pair of dice, dealing out a five-card poker hand, or spinning a spinner. The set of all possible outcomes is the sample space. Consider a subset of the sample space, such as all rolls in which the pair add up to seven, the hand is a straight flush, or the spinner stops at an angle between zero and 180 degrees. That subset is called an event. If all points in the sample space have the same probability of outcome, the probability is the ratio of the size of the subset for the event to the size of the sample space. (I suppose, more generally, this definition works for non-uniform distributions where the "size" includes weights, so to speak.) Probability is a set function, that is it maps each set in some sort of collection of subsets of the sample space into the real numbers.
This definition works well when the sample space contains a finite number of points. The "size" of a set is then just the number of points in the set. But consider the spinner example, where, with appropriate scaling of angles, the sample space is any real number in the interval [0, 1]. The number of points in a range of scaled angles [a, b] and in the sample space is, in both cases, uncountably infinite. Clearly, one needs some other concept of size here. And the concept of a probability measure provides the needed notion.
The demonstration of the existence of a non-measurable set validates the claim in the introduction. In the proof, the interval [0, 1] is partitioned into an uncountably infinite number of sets, each with only a countably infinite number of points in each set. The axiom of choice is used to "construct" from this partition another partition of the interval into a countably infinite number of sets, each with an uncountably infinite number of points. All of these sets have the same measure, and that measure must add up over the countably infinite number of sets to unity. But that measure can thus be neither zero nor non-szero. So some events exist, given the axiom of choice, without a probability.
3.0 Some Properties of a MeasureI use m(S) to denote the measure of a set. For this post, I consider measures with the following properties:
- The measure of an interval is merely the length of the interval:
m([a, b]) = b - a
- The measure of the empty set is zero:
m(∅) = 0
- The measure of any set S is non-negative. For all S
m(S) ≥ 0
- The measure of a set is translation invariant. Let S * x denote the set formed by adding x to each element S modulo one. (This definition keeps the translation of a set in the unit interval within the unit interval.) For all S and x:
m(S * x) = m(S)
- The measure of a set is countably additive. Let S1, S2, S3, ... be a sequence of disjoint sets. That is, for any i ≠ j, Si ∩ Sj = ∅. Then:
m(S1 ∪ S2 ∪ S3 ...) = m(S1) + m(S2) + m(S3) + ...
I have above selected the properties of specific kinds of measures. But they are all that is needed for the proof of the existence of unmeasurable sets.
In the spinner example, some non-empty sets have a measure of zero. For example, the probability that the spinner will stop at any given real number in the interval is zero. So is the probability that the spinner will stop at any element in a countably infinite set.
4.0 A Partition of the Unit Interval into Uncountably Infinite Equivalence ClassesDefine an equivalence relation as follows. Let two real numbers x1, x2 be equivalent if and only if x2 - x1 is a rational number. Partition the real numbers into equivalence classes by this equivalence relation. The rational numbers is one such equivalence class. The set of real numbers that differ from the square root of two by a rational number is another equivalence class. The set of real numbers differing from the square root of three by a rational number is a third equivalence class. The number π generates a third equivalence class. In fact, there are an uncountable infinite number of equivalence classes, and each such class can be put into a one-to-one mapping to the set of rational numbers.
Consider the collection of sets formed by the intersections of these equivalence classes with the unit interval. This is now a partition of the unit interval. I guess this is easy to understand, as compared to what comes next in this proof.
5.0 An Application of the Axiom of ChoiceI now apply the axiom of choice. Let S be a set that contains one and only one point from each of the equivalence classes. Thus, S is a subset of the unit interval containing an uncountably infinite number of points. The difference between any two points in S is an irrational number.
For each rational number r in the unit interval, form the translation S * r. The set of rational numbers in the unit interval is countably infinite. That is, these rational numbers can be ordered in a sequence r1, r2, r3, ...
Corresponding to this sequence is a sequence of sets S*r1, S*r2, S*r3, ... Each one of these sets is a translation of the set S. They all contain an uncountably infinite number of points, and they are all subsets of the unit interval. The intersection of any two of these sets is the empty set. Furthermore every point in the unit interval is in exactly one of these sets.
6.0 Finishing the Proof
The union of these disjoint sets is the unit interval, and the measure of the unit interval is unity. Thus:
m(S*r1 ∪ S*r2 ∪ S*r3 ...) = m([0, 1]) = 1 - 0 = 1
By countable additivity:
m(S*r1 ∪ S*r2 ∪ S*r3 ...) = m(S*r1) + m(S*r2) + m(S*r3) + ...
By translation invariance:
m(S*r1 ∪ S*r2 ∪ S*r3 ...) = m(S) + m(S) + m(S) + ...
Therefore:
1 = m(S) + m(S) + m(S) + ...
Suppose the measure of S were zero. Then we would have proven that zero equals one, an obvious contradiction. But suppose the measure of S were positive. Then the right hand size of the above equality would be infinity, another contradiction. So no measure can be assigned to the set S. In the model of a spinner, the set S represents an event, and no probability can be assigned to this event.
7.0 ConclusionHas anybody proved the existence of an unmeasurable set with a proof that is not a variation of the above? Can such existence be proven without relying on a proof by contradiction? How would you show that all proofs of such existence must use the axiom of choice? I believe it is also the case that the existence of an unmeasurable set implies the axiom of choice, although I have never seen this proven.
Probabilities cannot be assigned to some events. You will almost certainly never encounter such events in practical applications.
Appendix A. Some Mathematical BackgroundThe above post presumes knowledge that the rationals are countable, that the reals constitute an uncountable infinity, and that an equivalence relation yields equivalence classes that partition a set into nonoverlapping subsets.
A.1 The Rationals are CountableA countably infinite set can be ordered to be in one-to-one correspondence with the natural numbers, {1, 2, 3, ... }. (Sometimes I begin with zero.) Consider the ordering of positive fractions in Table A-1. The subscripts in parantheses show the order. The fractions are the ratio of the column index to the row index. Obviously, this sequence can be repeated forever. But some rational numbers are repeated. For example, the third fraction in the sequence is 1/2. But r(12) is 2/4. So when enumerating the positive rationals, throw out these repeats. Call the resulting sequence r1, r2, r3, and so on.
| 1 | 2 | 3 | 4 | 5 | ... | |
| 1 | r(1) = 1/1 | r(2) = 2/1 | r(6) = 3/1 | r(7) = 4/1 | r(15) = 5/1 | ... |
| 2 | r(3) = 1/2 | r(5) = 2/2 | r(8) = 3/2 | r(14) = 4/2 | .. | |
| 3 | r(4) = 1/3 | r(9) = 2/3 | r(13) = 3/3 | ... | ||
| 4 | r(10) = 1/4 | r(12) = 2/4 | ... | |||
| 5 | r(11) = 1/5 | ... | ||||
So at least the positive rational numbers are countable. Then consider the sequence 0, r1, -r1, r2, -r2, ... Thus, the rational numbers are countable.
A.2 The Reals are UncountableThe uncountability of the reals are demonstrated by Cantor's diagonizability argument. It is a proof by contradiction.
I think it easiest to think of the proof with real numbers in binary notation. And it is sufficient to show the real numbers between zero and one are uncountable. Accordingly, suppose somebody claims to have a sequence of all the real numbers between zero and one, as in Table A-2. One constructs a new real number as follows. Let the first digit to the right of the binary point be 0, if the corresponding digit in x1 is 1; 1, if the corresponding digit is 0. Let the second digit to the right of the binary point in this new number be 0, if the corresponding digit in x2 is 1; 1, if the corresponding digit is 0. And so on. Given some arbitary sequence, I have now constructed a new real number that cannot appear in the sequence. For it differs from every number in the sequence by at least one digit. So no such sequence can be constructed for the real numbers.
| x1 | 0.1001010... |
| x2 | 0.0001000... |
| x3 | 0.1010010... |
| x4 | 0.0111000... |
| ... | ... |
This mathematics demonstrates there are different sizes infinities. Nobody know whether or not there is another size infinity between the rationals and the reals. I am not even sure what this question would mean. But, if you accept that the above makes sense, you probably accept that there are an infinity of sizes of infinity bigger than the reals.
A.3 Equivalence RelationsA relation on a set S is a set of ordered pairs of elements in the set. Informally, the ordered pairs denote the subset of the Cartesian product S x S where the relation is true. Let a ˜ b denote an equivalence relation. That is:
- The relation is reflexive. For all a in S:
a ˜ a
- The relation is symmetric. For all a, b in S:
If a ˜ b, then b ˜ a
- The relation is transitive. For all a, b, c in S:
If a ˜ b and b ˜ c, then a ˜ c
In a sense, an equivalence relation is a generalization of equality. Every equivalence relation generates an equivalence classes, and vice versa. An equivalence class C is a subset of S such that for all a, b in C, a is equivalent to b. Equivalence classes partition a set. Every point in the set is in one equivalence class and only in one equivalence class. Any two equivalence classes are disjoint; their intersection is the empty set.
Posts
No comments:
Post a Comment