# 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\}$. Nov 25, 2019 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$. Nov 25, 2019 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 . . . Nov 25, 2019 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). Nov 25, 2019 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). Nov 25, 2019 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.