Appendix A: Fine structure of prediction with the axiom of choice
In the introductory part of Sect.
5 we introduced the Occam prediction systems (parametrised by well-orders on
\(\Omega\)), but limited ourselves to results required in the rest of that section. In this appendix, we extend these prediction systems and study them more systematically; the new notions and results of this appendix are not needed in the main part of the paper.
Remember that ⪯ is a well-order on
\(\Omega\), which in this appendix can be any of the
\(\Omega\) considered in the main part of the paper (unless
\(\Omega\) is explicitly pointed out). The
Occam prediction system is as follows:
-
given \(\omega|_{[0,t)}\), the prediction \(\omega^{t-}\) for the rest of \(\omega\) is defined as the ⪯-smallest \(\omega'\) such that \(\omega'|_{[0,t)}=\omega|_{[0,t)}\);
-
given
\(\omega|_{[0,t]}\), the prediction for the rest of
\(\omega\) is
\(\omega^{t}\), as defined in Sect.
5:
\(\omega^{t}\) is the ⪯-smallest element
\(\omega'\) satisfying
\(\omega'|_{[0,t]}=\omega|_{[0,t]}\);
-
the revised prediction \(\omega^{t+}\) at the time \(t\in[0,1)\) is \(\omega^{t'}\) for any \(t'\in(t,1]\) such that the function \(s\mapsto\omega^{s}\) is constant over \((t,t']\).
The existence of
\(\omega^{t+}\) was shown in part 3 of Lemma
5.1 (and was already used in the proof of Theorem
3.3 in Sect.
5.3). By definition,
\(\omega^{1+}\) is undefined, but notice that
\(\omega^{t}\) and
\(\omega^{t-}\) are defined for all
\(t\in[0,1]\) (in particular,
\(\omega^{0-}\) is the ⪯-smallest element of
\(\Omega\)).
We have the following three dichotomies for time points
\(t\in[0,1]\) for the purpose of short-term prediction of a given
\(\omega\in\Omega\):
-
\(t\) is past-successful (for \(\omega\)) if there exists \(t'< t\) such that \(\omega^{t'}=\omega^{t-}\); in particular, 0 is not past-successful;
-
\(t\) is present-successful if \(\omega^{t-}=\omega^{t}\);
-
\(t\) is future-successful if \(\omega^{t}=\omega^{t+}\); in particular, 1 is not future-successful.
This gives us a partition of all
\(t\in[0,1]\) into
\(2^{3}=8\) classes. We say that
\(t\) is
\((-,0,+)\)
-successful (for the short-term prediction of
\(\omega\) using the Occam prediction system) if
\(t\) is simultaneously past-successful, present-successful, and future-successful; this is the highest degree of success. More generally, we include − (respectively, 0, +) in the designation of the class of
\(t\) if and only if
\(t\) is past- (respectively, present-, future-) successful. The
\(t\) that are
\(()\)-successful are not successful at all: they are not past-successful, not present-successful, and not future-successful. We use notation such as
\(C^{(-,0,+)}_{\omega}\) and
\(C^{()}_{\omega}\) for denoting the set of
\(t\) of the class indicated as the superscript. For example,
\(C^{(-,0)}_{\omega}\) is the class of
\(t\in[0,1]\) that are past- and present-successful but not future-successful for
\(\omega\).
The definition (
5.1) can be expressed in our new terminology by saying that
\(W_{\omega}\) are the
\(t\in[0,1]\) that are not future-successful (which agrees with
\(1\in W_{\omega}\)); in our new notation,
$$ W_{\omega} = C^{(-,0)}_{\omega} \cup C^{(-)}_{\omega} \cup C^{(0)}_{\omega} \cup C^{()}_{\omega}. $$
(A.1)
Let us modify the definition (
5.1) by setting
$$ F_{\omega} := \big\{ t\in[0,1] :\big( \forall t'\in(t,1], \omega^{t'}\ne\omega^{t} \big) \text{ or } \big( \forall t'\in[0,t), \omega^{t'}\ne\omega^{t} \big) \big\} ; $$
in particular,
\(\{0,1\}\subseteq F_{\omega}\). This is the set of times
\(t\in[0,1]\) when the Occam prediction system fails in the weakest possible sense that can be expressed via our three dichotomies; namely,
\(F_{\omega}\) is the set
\([0,1]\setminus C^{(-,0,+)}\) of
\(t\in[0,1]\) that are not
\((-,0,+)\)-successful. If
\(t\in[0,1]\setminus F_{\omega}\), the Occam prediction system correctly predicts
\(\omega|_{[t_{1},t_{2}]}\) already at time
\(t_{1}\), where
\((t_{1},t_{2})\ni t\) is a neighbourhood of
\(t\).
It is always true that \(W_{\omega}\subseteq F_{\omega}\), and even the set \(F_{\omega}\) is still small:
Part 1 of Lemma
5.1 is a special case of Lemma
A.1, since any subset of a well-ordered set is well-ordered. We can also see that each of the eight classes apart from
\(C^{(-,0,+)}_{\omega}\) is well-ordered.
The following lemma shows that \(F_{\omega}\) splits \([0,1]\) into intervals of constancy of \(t\mapsto\omega^{t}\).
Let us check that the analogue of Lemma
A.2 still holds for
\(W_{\omega}\) in place of
\(F_{\omega}\) if
\(\Omega=C[0,1]\), but fails in general.
The following result (easy but tiresome) shows that each of the eight classes may be non-empty, apart from the case
\(\Omega=C[0,1]\), where there are six potentially non-empty classes (two of them being subsets of
\(\{0\}\)). In particular, it implies that
\(W_{\omega}\ne F_{\omega}\) is possible, and moreover,
\(F_{\omega}\setminus W_{\omega}\) may contain any
\(c\in(0,1)\) (which is also clear from the proof of Lemma
A.3).
Lemma
A.4 shows that the number of different unions (such as (
A.1)) that can be formed from the classes
\(C_{\omega}^{(\cdots)}\) is very large (namely,
\(2^{8}=256\)), and many of these are potentially interesting. For each of the unions, we can ask what sets in
\([0,1]\) can be represented as such a union for different
\(\omega\). We answer this question only for the union (
A.1), which plays the most important role in this paper.
An analogue of Lemma
A.5 (however, with “⊇” in place of “=”) is contained in Theorem 3.5 of [
4].