# Can random variables that almost surely solve equations be repaired to surely solve these equations?

Let $$(X_\alpha)_{\alpha \in A}$$ be a family of boolean random variables $$X_\alpha: \Omega \to \{0,1\}$$ on a probability space $$\Omega = (\Omega, {\mathcal F}, {\mathbf P})$$. Let $${\mathcal S}$$ be a family of boolean sentences that each involve finitely many of the $$X_\alpha$$. Suppose that each sentence $$S \in {\mathcal S}$$ is almost surely satisfied by the $$(X_\alpha)_{\alpha \in A}$$. Can one then "repair" the random variables by locating further random variables $$(\tilde X_\alpha)_{\alpha \in A}$$ with each $$\tilde X_\alpha$$ almost surely equal to $$X_\alpha$$, such that the $$\tilde X_\alpha$$ surely satisfy all the sentences $$S \in {\mathcal S}$$?

If $$|A| \leq \aleph_0$$ (that is to say there are at most countably many random variables) then the task is easy, for then the set of sentences $$S$$ is also at most countable, and (because the countable union of null events is null) there is a single null event $$N$$ outside of which the $$X_\alpha$$ already surely satisfy all the sentences $$S$$. In particular there is a deterministic choice $$X_\alpha^0 \in \{0,1\}$$ of boolean inputs that satisfy all the sentences, and if one sets $$\tilde X_\alpha$$ to equal $$X_\alpha$$ outside of $$N$$ and $$X_\alpha^0$$ in $$N$$, we obtain the claim.

If $$|A| \leq \aleph_1$$ (that is to say $$A$$ has at most the cardinality of the first uncountable ordinal) and $$\Omega$$ is complete, then a slight variant of the above argument also works. We may well order $$A$$ so that every element $$\alpha$$ has at most countably many predecessors. We then use transfinite induction to recursively select $$\tilde X_\alpha$$ almost surely equal to $$X_\alpha$$, with the property that for all (not just almost all) sample points $$\omega \in \Omega$$, the tuple $$(\tilde X_\beta(\omega))_{\beta \leq \alpha}$$ may be extended to a tuple $$(x_\beta)_{\beta \in A}$$ solving all the sentences $$S \in {\mathcal S}$$. Indeed, if such variables $$\tilde X_\beta$$ have already been constructed for all $$\beta < \alpha$$, then the random variable $$X_\alpha$$ will already have this property outside of a null set $$N_\alpha$$ (here we use the fact that the set of tuples in the metrisable space $$\{0,1\}^{\{ \beta: \beta \leq \alpha\}}$$ that can be extended is the continuous image of a compact set and is thus closed and measurable). For each $$\omega \in N_\alpha$$, there exists at least one choice of $$\tilde X_\alpha(\omega)$$ that will obey the required extension property, thanks to the compactness theorem; using the axiom of choice to arbitrarily define $$\tilde X_\alpha$$ on this null set, we obtain a $$\tilde X_\alpha$$ with the required properties (it is measurable because $$\Omega$$ is assumed complete), and then the entire tuple $$(\tilde X_\alpha)_{\alpha \in A}$$ will surely satisfy all the sentences $$S \in {\mathcal S}$$. [It may be possible to drop the completeness hypothesis here by appealing to a measurable selection theorem; I have not thought about this carefully.]

Another illustrative case where the answer is affirmative is if $$A$$ is arbitrary and $${\mathcal S}$$ is just the collection of equality sentences $$X_\alpha = X_\beta$$ for $$\alpha,\beta \in A$$. Thus we have $$X_\alpha=X_\beta$$ almost surely for each $$\alpha,\beta$$, and we wish to modify each $$X_\alpha$$ on a null set to create new random variables $$\tilde X_\alpha$$ such that $$\tilde X_\alpha = \tilde X_\beta$$. Note that for each $$\omega \in \Omega$$ it is not necessarily the case (even after deleting a null set) that all the $$X_\alpha(\omega)$$ are equal to each other (e.g., suppose $$A=\Omega=[0,1]$$ and $$X_\alpha(\omega) = 1_{\alpha=\omega}$$), but nevertheless the problem is easily solved in this case by arbitrarily selecting one element $$\alpha_0$$ of $$A$$ and defining $$\tilde X_\alpha := X_{\alpha_0}$$.

However, I do not have a good intuition as to whether the answer to this question is affirmative in general, even if one assumes good properties on the probability space $$\Omega$$ (e.g., that it is a standard probability space). The appearance of the cardinal $$\aleph_1$$ hints that perhaps the answer is sensitive to undecidable axioms in set theory.

(For my ultimate application I would eventually like to replace the boolean space $$\{0,1\}$$ with the interval $$[0,1]$$ or other Polish spaces, and the sentences $$S$$ with closed conditions involving finitely many or countably many of the variables at a time, but the Boolean case already seems nontrivial and captures much of the essence of the problem.)

EDIT: The following "near-counterexample" may also be suggestive. Set $$\Omega = [0,1]$$, let $$A = 2^{[0,1]}$$ be the power set of $$\Omega$$, and let $$\mathcal{S}$$ be the set of sentences $$X_\alpha = X_\beta$$ where $$\alpha,\beta \subset [0,1]$$ differ by at most one point. If one sets $$X_\alpha(\omega) := 1_{\omega \in \alpha}$$, then one morally has that the $$X_\alpha$$ almost surely satisfy all the sentences in $$S$$, but that there is no way to repair the $$X_\alpha$$ to random variables $$\tilde X_\alpha$$ that surely satisfy the equations as this would force $$\tilde X_{[0,1]} = \tilde X_\emptyset$$ while $$X_{[0,1]}=1$$ and $$X_\emptyset = 0$$. However this is not actually a counterexample because most of the $$X_\alpha$$ are non-measurable. (Removed due to errors)

• Just in case some more probabilistic terminology helps, your "repaired" random variables $\tilde{X}_\alpha$ form a modification of the stochastic process $\{X_\alpha\}$. – Nate Eldredge Nov 25 '19 at 17:01
• I might be missing something, but I don't see why your near-counterexample works. What forces $\tilde X_{[0,1]} = \tilde X_\emptyset$? Using the Axiom of Choice, there is a mapping $c: \mathcal P([0,1]) \rightarrow \mathcal P([0,1])$ such that $c(\alpha) = c(\beta)$ whenever $\alpha$ and $\beta$ have a finite symmetric difference. But then one could repair the $X_\alpha$ by setting $\tilde X_\alpha = X_{c(\alpha)}$ for each $\alpha$. – Will Brian Nov 25 '19 at 19:21
• @TerryTao: Thanks for clarifying. Your question reminds me of an old theorem of Shelah from a paper called "Lifting problem of the measure algebra." As far as I can tell, his results give you a "near-counterexample" to your question, in the sense of giving an actual counterexample to a closely related question. Specifically, let's modify your question by insisting that the $X_\alpha$ are all Borel, and asking that the $\tilde X_\alpha$ be Borel as well. Given this version of the question, let's take $A$ to be all Borel subsets of $[0,1]$, and let's take $\mathcal S$ to be the set of all . . . – Will Brian Nov 25 '19 at 21:12
• . . . sentences of the form $X_\alpha \leq X_\beta$ whenever $\alpha \subseteq \beta$ modulo a set of measure $0$. In this case, any (Borel) repairs you make $X_\alpha \mapsto \tilde X_\alpha$ would give rise to what Shelah calls a "splitting" of the measure algebra. The main theorem of Shelah's paper is that it is consistent that there is no such splitting (assuming ZFC is consistent at all). – Will Brian Nov 25 '19 at 21:14
• @WillBrian I'm happy to give $\Omega$ the Borel sigma algebra, in which case it does seem like Shelah's result shows that it is consistent with ZFC that such a extension result does not hold in general (as one can encode the property of being a Boolean algebra homomorphism in terms of a family of atomic sentences). Please feel free to write up your response as an answer and I can accept it (well, I guess there is still the possibility that there is a further example that does not require axioms beyond ZFC exists, but this doesn't seem to be in the literature as far as I can tell). – Terry Tao Nov 25 '19 at 21:47

In Terry's answer, he shows that his original question reduces to the question of whether, given a $$\sigma$$-algebra $$\mathcal F$$ on some set $$X$$ and a measure $$\mu$$ on $$(X,\mathcal F)$$, there is a splitting'' of the quotient algebra $$\mathcal F / \mathcal N$$, where $$\mathcal N$$ denotes the ideal of $$\mu$$-null sets. In this context, a splitting is a Boolean homomorphism $$\Phi: \mathcal F / \mathcal N \rightarrow \mathcal F$$ such that $$\Phi([A]) \in [A]$$ for all $$A \in \mathcal F$$. (Some authors call this a lifting instead of a splitting.) When some such $$\Phi$$ exists, let us say that $$(X,\mathcal F,\mu)$$ has a splitting.

I did some digging on this question this afternoon, and found two very good sources of information: David Fremlin's article in the Handbook of Boolean Algebras (available here) and a survey paper by Maxim Burke entitled "Liftings for noncomplete probability spaces" (available here). I'll summarize some of what I found below to supplement what Terry mentions in his answer. He mentions already that it is independent of ZFC whether $$([0,1],\text{Borel},\text{Lebesgue})$$ has a splitting:

$$\bullet$$ (von Neumann, 1931) Assuming $$\mathsf{CH}$$, $$([0,1],\text{Borel},\text{Lebesgue})$$ has a splitting.

$$\bullet$$ (Shelah, 1983) There is a forcing extension in which $$([0,1],\text{Borel},\text{Lebesgue})$$ has no splitting.

Also mentioned already is the fact that if we expand the $$\sigma$$-algebra in question from the Borel sets to all Lebesgue-measurable sets, then the situation is more straightforward:

$$\bullet$$ (Maharam, 1958) If $$(X,\mu)$$ is a complete probability space, then $$(X,\mu\text{-measurable},\mu)$$ has a splitting.

Now on to some not-yet-mentioned results. First, it's worth pointing out that one can obtain splittings with nice extra properties.

$$\bullet$$ (Ioenescu-Tulcea, 1967) Let $$G$$ be a locally compact group, and let $$\mu$$ denote its Haar measure. Then $$(G,\mu\text{-measurable},\mu)$$ has a translation-invariant splitting (which means $$\Phi([A+c]) = \Phi([A])+c$$ for every $$\mu\text{-measurable}$$ set $$A$$).

Once again, shrinking our $$\sigma$$-algebra from all $$\mu$$-measurable sets to only the Borel sets causes problems.

$$\bullet$$ (Johnson, 1980) There is no translation-invariant splitting for $$([0,1],\text{Borel},\text{Lebesgue})$$.

Thus, interestingly, Shelah's consistency result becomes a theorem of $$\mathsf{ZFC}$$ if we insist on the splitting being translation-invariant (with respect to mod-$$1$$ addition). More generally:

$$\bullet$$ (Talagrand, 1982) If $$G$$ is a compact Abelian group and $$\mu$$ is its Haar measure, then there is no translation-invariant splitting for $$(G,\text{Borel},\mu)$$.

What stood out to me most in Fremlin and Burke's articles is how many questions seem to be wide open.

Open question: Is it consistent that every probability space has a lifting?

If yes, this would give a consistent positive answer to Terry's original question.

Open question: Is it consistent with $$2^{\aleph_0} > \aleph_2$$ that $$([0,1],\text{Borel},\text{Lebesgue})$$ has a splitting?

(Carlson showed that it is consistent to have $$2^{\aleph_0} = \aleph_2$$ and for $$([0,1],\text{Borel},\text{Lebesgue})$$ to have a splitting. Specifically, he showed that this holds whenever one adds precisely $$\aleph_2$$ Cohen reals to a model of $$\mathsf{CH}$$.)

Open question: Does Martin's Axiom (or $$\mathsf{PFA}$$, or $$\mathsf{MM}$$) imply that $$([0,1],\text{Borel},\text{Lebesgue})$$ has a splitting?

Open question: What of the same question in other well-known models of set theory (the random model, Sacks model, Laver model, etc.)?

After chasing down references relating to the paper of Shelah mentioned by Will Brian, I now have a satisfactory answer to the question. It all hinges on whether there is a splitting of the quotient algebra $${\mathcal F}/{\mathcal N}$$ of the $$\sigma$$-algebra $${\mathcal F}$$ by the null ideal $${\mathcal N}$$, that is to say a Boolean algebra homomorphism $$\Phi: {\mathcal F}/{\mathcal N} \to {\mathcal F}$$ that is a left inverse for the quotient map $$\pi: {\mathcal F} \to {\mathcal F}/{\mathcal N}$$.

First suppose that such a map exists. Then for each $$\alpha \in A$$ and $$\omega \in \Omega$$ there is a unique element $$\tilde X_\alpha(\omega)$$ of $$\{0,1\}$$ with the property that $$\omega \in \Phi( \pi( X_\alpha^{-1}( \{\tilde X_\alpha(\omega)\} ) ).$$ It is a tedious but routine matter to check that $$\tilde X_\alpha: \Omega \to \{0,1\}$$ is a modification of $$X_\alpha$$ (a random variable that agrees almost surely with $$X_\alpha$$), and that the $$\tilde X_\alpha$$ satisfy every sentence $$S \in {\mathcal S}$$ surely (rather than just almost surely).

Conversely, suppose that every family of random variables $$X_\alpha$$ that almost surely obeys each sentence $$S$$ in a family $${\mathcal S}$$ can be modified to surely obey such a sentence. We consider the family $$(X_\alpha)_{\alpha \in {\mathcal F}}$$ defined by $$X_\alpha(\omega) = 1_{\omega \in \alpha}$$ and consider the Boolean algebra homomorphism sentences $$X_{\alpha \cup \beta} = \max( X_\alpha, X_\beta ); \quad X_{\alpha \cap \beta} = \min(X_\alpha, X_\beta )$$ $$X_0 = 0; X_1 = 1$$ $$X_{\alpha^c} = 1 - X_\alpha$$ for $$\alpha, \beta \in {\mathcal F}$$, together with the sentences $$X_\alpha = X_\beta$$ whenever $$\alpha,\beta$$ differ by a null element in $${\mathcal N}$$. Then the indicated random variables $$X_\alpha$$ obey each these sentences almost surely. By hypothesis, there exists a modification $$\tilde X_\alpha$$ of each $$X_\alpha$$ that obey these sentences surely. If we then define $$\tilde \Phi: {\mathcal F} \to {\mathcal F}$$ by the formula $$\tilde \Phi(\alpha) := \{ \omega \in \Omega: \tilde X_\alpha(\omega) = 1 \}$$ then one can verify that $$\tilde \Phi$$ is a Boolean algebra homomorphism such that $$\tilde \Phi(\alpha)=\tilde \Phi(\beta)$$ whenever $$\alpha,\beta$$ differ by a null element, and such that $$\tilde \Phi(\alpha)$$ differs from $$\alpha$$ by a null element. Thus $$\tilde \Phi$$ descends to a splitting of $${\mathcal F}/{\mathcal N}$$.

As mentioned by Will Brian, the main result of

Shelah, Saharon, Lifting problem of the measure algebra, Isr. J. Math. 45, 90-96 (1983). ZBL0549.03041.

is that it is consistent with ZFC that $$[0,1]$$ with the Borel sigma-algebra has no splitting; on the other hand it is a classical result of von Neumann and Stone that assuming CH, this measurable space has a splitting. So for this space at least the problem I asked is undecidable in ZFC! On the other hand, the main result in

Maharam, Dorothy, On a theorem of von Neumann, Proc. Am. Math. Soc. 9, 987-994 (1959). ZBL0102.04103.

shows that a splitting always exists for complete probability spaces.