In this article we learn what the algebra generated by a set system is. We prove some important properties and get to know the Borel -algebra.
Let be a set system over a basic set and a function on sets. Our goal is to find out how and under what conditions can be continued to a measure on a reasonable -algebra .
A continuation must be defined at least on the domain of definition of the function to be continued. Therefore, the set system must be contained in .
One possibility would be to choose by default the power set as domain of definition of the continuation (i.e., the largest possible domain): It is a algebra and contains . But this is not always a sensible choice:
- The power set is in general too ambitious a target for a continuation: the volume problem shows that with intuitive geometric volumes there can be problems defining them on the whole power set. So the power set may be too large to continue a measure to it.
- The power set may also be unnecessarily large: compared to the set system , may contain too many sets to which continuation then makes no sense. A simple example for this case is when is a measure and itself is already a algebra, but not the power set.
A concrete example for the second point is the following:
Example (Reasonable extension of )
Let and . Let further be a function defined on the set of sets with . The set system
is a -algebra containing . But of course the power set is also such a -algebra. Intuitively, however, makes little sense as a domain of definition of a continuation of . This is because the power set also contains the one-element subsets of . However, does not provide any information about these at all: we could arbitrarily choose the value for from . A larger value is not possible because of monotonicity, since must hold. Then, because of additivity,
The -algebra we are looking for should therefore not be larger than necessary. We have already stated above that it should, however, contain at least the set system . So we first consider all super--algebras of , i.e., all -algebras containing . To find the smallest among these, we proceed as in constructing the (topological) closure of a set: The closure of a set is the smallest closed superset and is defined as a section over all closed supersets. Analogously, we choose the smallest super--algebra of to be the intersection over all these -algebras.
Definition: Generated -algebra[Bearbeiten]
The -algebra, which we defined in the previous section as the intersection over all super--algebras of , is called generated -algebra:
Definition (Generated -algebra)
Let be a set and be a set system. The -algebra
is called the algebra generated by . The "operator of generation " defined by it is called the operator. The set system is called generator of .
is another notation for the intersection , where .
Although there is no in , the algebra generated of a set system depends of course on the underlying basic set . Let, for instance . Then is the algebra generated by over . For another basic set this is a different set system. Often, the is clear from the context and is therefore omitted in the notation of the operator.
One can also define other kinds of generated set systems according to the same principle. For example, one can define the ring or -ring generated by a set system .
We still need to verify that the generated -algebra is well-defined, that is, that the definition makes sense. To do this, we need to show:
- The set over which the intersection is formed is not empty. That is, there is at least one -algebra containing .
- is indeed a -algebra.
The first point is clear since the power set is a -algebra containing . For the proof of the second point, we have to prove that the intersection of arbitrary many -algebras is always a -algebra again. Then, we have that as a section over certain -algebras is indeed a -algebra.
Theorem (The intersection of -algebras is again a -algebra.)
Let be a non-empty set of -algebras over . That is, every element in is a -algebra. Then is a -algebra.
Proof (The intersection of -algebras is again a -algebra.)
We need to prove that satisfies the three properties of a -algebra:
The basic set is in :
Each element of is a -algebra over and thus contains the basic set. Thus is also contained in the section over all these elements, i.e. in .
Let be arbitrary. By definition of , lies in the intersection of all algebras from We conclude for all . Since every is a -algebra, the complement also lies in for all . Thus is also in the section over all these -algebras, that is, in
Completeness under countable unions:
Let . By definition of these sets lie in the intersection of all -algebras from , so we have that for all Since every is a -algebra and hence complete under formation of countable unions, every from also contains the union Thus this union also lies in the section over all these -algebras from , i.e. in .
We have now shown that is a -algebra. Intuitively, it should be the smallest -algebra containing the set system . We prove this in the next section "Properties of the -operator".
Properties of the -operator[Bearbeiten]
We establish some useful properties of the -operator:
Let be a set system. The -operator now satisfies the following properties:
- Minimality: is the smallest -algebra containing . If is a -algebra, then .
- Extensivity: By definition, is subset of every -algebra over which we take the intersection in the definition of the -operator. That is, for any , is element every -algebra over which we intersect. Then is also element of the intersection of all these -algebras, which is exactly . Since this is true , we have .
- Minimality: Let be a -algebra with . Since is one of the sets over which we intersect in the definition of , we have that . If is a -algebra we may readily conclude . From extensivity we obtain the other inclusion and therefore we have .
- Idempotency: The idempotency follows directly from the minimality. We have that is always a -algebra, and therefore we have .
- Monotonicity: Let . Then, we have due to extensivity. Since is a -algebra, it follows from minimality that holds.
The properties 1., 3. and 4. (extensivity, idempotency and monotonicity) make the -operator an enveloping operator (it determines the envelope of a set, like wrapping a gift), just as the closure "" of sets turning "" into "".
In the section "Motivation" we have seen a first example for a generated -algebra: Let and Then is the -algebra generated by : is a -algebra and the smallest one containing . Another example for a finitely generated -algebra is the following:
If one wants to describe the probability of the occurrence of events when rolling a dice by using a measure, the domain of definition is the -algebra, which contains all elementary events. These are all one-element subsets of the basic set The -algebra generated by the set generated is the power set
The -algebra of the one-element subsets of a countable basic set often appears in discrete probability theory as a domain of definition of the distribution of discrete random variables. In this case of a discrete, i.e. countable basic set (such as or ), the -algebra generated by these elementary events is the power set . So actually, introducing -algebras would not be necessary. However, the situation is different if the basic set is over-countable, like :
Theorem (-algebra over generated by point sets)
Let be the basic set. The -algebra generated from the set of one-element subsets is
Proof (-algebra over generated by point sets)
We perform the proof in two steps. First, we show that is a algebra containing , i.e., holds. Next we show . Then we conclude .
Proof step: is a -algebra containing
The elements from (which are subsets of the basic set) contain only one-element each. Thus, they are countable. It follows directly that every element from is also contained in , so . We now show that is a -algebra. To do this, we check the three criteria:
is of course satisfied, since is countable.
If , then is countable or is countable. In case 1, is countable, so it is contained in .
In case 2, has a countable complement, so is contained in .
Let now a union of sets from . Then we distinguish two cases.
In case 1, for at least one the set has countable complement. But then as a subset of a countable set is also countable and hence contained in .
In case 2 for all the set is countable. Then, of course, their union is countable and hence contained in .
Thus is really -algebra and it contains .
Let be arbitrary. Then we distinguish two cases.
In case 1, is countable. Consider as a countable union of sets from . Then is in particular also a countable union of sets in and because of the union stability of -algebras with respect to countable unions, it follows that .
In case 2 is countable, so according to case 1 it is contained in . From the complement stability of it now follows that also is true.
We have that also .
Following the monotonicity of the -operator, we have that .
Since and are already -algebras, it follows from the minimality of the operator that
holds true, i.e. .
Some algebras are so large that they cannot be written down explicitly, as in the previous examples. They can then only be characterized by the generator. An example for this is the -algebra generated by the intervals over , which is an often-used but very rich example.
Example (-algebra generated by intervals or cuboids)
The geometric length is the function over which assigns to all intervals , respectively, , , their length . We do not yet know whether this function can be continued to a measure on a -algebra. But a reasonable domain of definition of such a continuation would then be the -algebra generated of all such intervals, i.e. with .
More generally, one can consider the geometric volume that assigns to all axis-parallel cuboids in their volume, i.e., the product of the side lengths. A cuboid is a product of intervals (open, half-open or closed). Again, we do not yet know whether this set function can be continued to a measure. But a reasonable domain of definition for a continuation would then be the -algebra , generated by the set system of cuboids .
Link to the article where a continuation from one to the other function above is defined.
Proving that two set systems generate the same -algebra[Bearbeiten]
It is common to want to find out whether two -algebras and are equal. For this we would prefer to simply show mutual inclusion directly, i.e. to prove and . But if were defined only by generators , this is not an easy job. We would have to take any set in the inclusion proof and show that also holds. The problem is that in general, -sets look very complicated, so we do not know what such set looks like and what properties it has. We only know that it is contained in every superset--algebra of . However, we know what the generators look like. So it is way easier to just show that the generators are included in each other. This is what we will do now.
Subset-relations for generators[Bearbeiten]
Let be -algebras and let be a generator of (that is a set with ). Now if the producer of is a subset of , then also our -algebra is already a subset of the -algebra . That is .
First we see that from the minimality of the -operator, we get . Now we use the monotonicity of the -operator:
Thus we have already simplified our problem considerably. We no longer need to show for arbitrary sets that is true (which might be a great mess to do). It suffices to prove the inclusion for sets from the generator of .
The opposite inclusion can be simplified using the same principle. That is, instead of showing for any that holds (again, a great mess), we take a generator of and show for all that is satisfied.
Proving that a set is contained in a -algebra[Bearbeiten]
We now know that it suffices to show only for the sets from the generator that they lie in the respective other -algebra. But how can we prove in general for a set that it lies in a certain -algebra ?
We know that is closed under the operations complement and countable union (and hence also under taking differences and countable cuts). Therefore every set generated by these operations from sets of the generator is again in . Thus, to prove that a set is in , it suffices to take some sets from the generator and write it as an outcome of some set operations between those sets.
Since -algebras can be very large, however, there is no general method to find such a representation of over the sets from the generator.
Example: The -algebra generated by intervals[Bearbeiten]
We will now demonstrate this principle with an example.
Consider the set system , , . Then, we have . Now, the set system generates the same -algebra.
We show , since then the claim of the theorem follows.
It is enough according to the previous theorem to show that holds.
Let also . Then and also . Because of the diference stability of then also . Since was arbitrary, it follows that , and from this follows the claim of this proof step.
We show again . Let for this .
The sets and are also in as countable unions of sets from . The union is contained (again because of union stability) in , and with the complement stability of then follows . Since was arbitrary, it follows that .
As in the other two proof steps, we again show .
Let for this be arbitrarily. We have that then for all , the set . Then, because of the union stability with respect to countable unions, . Since was arbitrary, it follows , and hence also .
It makes sense in the following to define .
We now show that also generates this algebra.
Because of the monotonicity, from directly follows . For the other set inclusion we again show, according to our principle, . Let for this be arbitrarily. We can assume that is bounded, because if it was not, we could write as a countable union of bounded intervals and thus reduce the statement to the bounded case.
That means there are , so that, one of the following cases occurs
In the first three cases is contained in a known generator from , and hence also in .
In the case as countable unions of sets in lies again in .
Since was arbitrarily chosen from , it follows that .
Thus finally obtain .
Both inclusions are shown and we have that .
Generators of the Borel -algebra [Bearbeiten]
We now apply the principle of the last section to a very important example, namely the so-called Borel -algebra.
Theorem (Different generators of the Borel -algebra on real numbers)
Let . Then, we call the Borel -algebra over .
We show that is equivalently generated by the following set systems: , .
That means, .
Proof (Different generators of the Borel -algebra on real numbers)
We prove that . Then all these -algebras must be equal.
As proved in the previous theorem, it suffices to show that holds.
Let also be chosen arbitrarily.
Our idea is to represent as a countable union of sets from .
Let for and the set . Then is a countable union of elements of , and thus because of the stability of union with respect to countable sets of -algebras, also an element of .
We now show that .
, as it is as union of subsets of , is of course also a subset of , i.e. .
For the opposite inclusion let be arbitrary. We will now cleverly construct a half-open cube with rational side length and rational center such that is fulfilled.
Since is open, is also open with respect to the maximum norm. In the following, let always be the -environment of with respect to the maximum norm. There exists then an with because is open.
Let , . Then, we have . Let Since is dense in , there is now . It follows conversely that . Moreover, .
Thus is one of the sets over which we take the union in the definition of . So .
Since was arbitrarily chosen from , we have and consequently .
Since was arbitrary, , from which follows.
We show again .
To do this, let be arbitrary, i.e., is closed. We then have that by definition is open, so . Then, because of the complement stability of -algebras, .
Since was arbitrary, it also follows that and hence .
We proceed as in Step 1 and 2 and show .
Let be arbitrarily. Let . Then is closed, so .
We now define sets as follows: for let . Then these are closed sets, so we have that also . The are the "missing" -dimensional side faces of the -dimensional half-open cuboid .
Further we have that
Since is difference stable and union stable with respect to countable unions (it is a -algebra), it follows that .
Since this is true for any ,we have and therefore .
Now we have that as previously considered, and from this follows . That means, the Borel -algebra is generated from the set of half-open cuboids, or equivalently fro the set of closed sets or the set of open sets.
In the theorem we represented the Borel -algebra as the -algebra generated by the set system of the right-open cuboids. One can show that the following systems of cuboids also generate the Borel -algebra:
- the set system of open cuboids .
- the set system of closed cuboids .
- the set system of left open cuboids .
- the set system of all cuboids .
In the section "Examples" above, we already encountered the last mentioned set system, as well as the -algebra generated by it.
We now know that the Borel -algebra on is also generated by all open or by all closed subsets of . One can define more generally the Borel -algebra on a topological space as the -algebra generated by all open sets (note that the "topology" is just this "set of all open sets") . On , this agrees with our definition.
The Borel -algebra is one of the most important -algebras in mathematics. It plays the role of the "smallest and simplest -algebra, where stuff makes sense". We will encounter it later in the construction of the Lebesgue measure, again.
Link to the article, where the Borel -algebra is treated in detail.