Countably Factored Spaces

post by Diffractor · 2021-09-09T04:24:58.090Z · LW · GW · 3 comments

Contents

  Why Nice Partitions? What is "Nice" Anyways?
  Countably Factored Spaces: Introduction and Factorization
    Definition 1: Countably Factored Space
  Countably Factored Spaces: Conditional Orthogonality
  Countably Factored Spaces: Polynomials and Probability
None
3 comments

A followup to Scott's "Finite Factored Sets", specifically the Applications part at the end where he talked about the infinite case [? · GW].

As it turns out, there's a natural-seeming (at least to my mathematical tastes) way to generalize all the finite factored set stuff to the infinite case.

To be perfectly clear about what is being claimed:

1: It is possible to deal with arbitrary compact metric spaces, instead of just finite products of finite sets, with a minimum of fuss. In particular this means that we can have countably many axes/basis factors/coordinates now!

2: Orthogonality, time, history, and all that remain perfectly well-defined in the infinite-coordinate case, no meaningful differences crop up in comparision to how the finite case works.

4: Of the three ways to implement the extension to the infinite case which were suggested in Scott's post, it is closest in spirit to the second approach, with having the history of $X$ be the intersection of all the sets $C\subseteq B$ s.t. $C⊢X$. The proffered counterexample from Scott's post is forbidden by restricting the partitions to "sufficiently nice" ones, which makes everything Just Work.

5: Yes, the semigraphoid axioms, and everything not specifically mentioned, work out, with absolutely no special tricks needed besides the single starting restriction on only using "sufficiently nice" partitions and sets.

6: I was only able to get one direction of the fundamental theorem to work out (the conditional orthogonality to conditional probabilistic independence direction), since the nice attributes of ordinary vanilla polynomials don't last when you start mucking about with uncountable sums of countable products of variables. It's fairly plausible that the missing direction of the fundamental theorem does work out and I'm just not a good enough mathematician to show it, feel free to try it yourself. I suspect it'll require a different proof path than the original, though.

7: Daniel Filan has, completely independently of me, generalized all results in "Finite Factored Sets" to countable sets (note that in that case, there can still only be finitely many factors, while this version can have countably many factors. Daniel's version of things is unconstrained by the compactness restriction that I have, though.) Apparently everything works out perfectly, including the fundamental theorem, although the direction of it which I failed to show was also tricky for them, and TurnTrout contributed several essential pieces of the proof for that.

Let's get started.

 

Why Nice Partitions? What is "Nice" Anyways?

So, first off: where someone working in combinatorics sees a partition of a set, a topologist sees a quotient space.

If you've got a space $S$, then a partition $X$ induces a function ${\sim }_X:S\to X$, which maps a point to the unique equivalence class it's in. Then, we just need to stick a topology on the set $X$, which ends up being "put as many open sets in $X$ as you can while keeping the function ${\sim }_X$ continuous".

Basically, taking a quotient is the process of taking a space and using an equivalence relation to go "let's make a new space where all things in the same equivalence class is treated as the same point". Quotient spaces are generally written as something like $S/\sim$. 

So, if you're trying to generalize finite factored sets to the infinite case, and are working with various sorts of partitions, looking at the quotient spaces of the partitions is a very natural thing to do.

The teensy little problem is that taking quotients is just not a very well-behaved operation topologically. Operations like disjoint sum and products are very good at preserving  toplogical properties. You take two "nice" spaces, for many definitions of "nice", take a product, and it'll probably be "nice" as well, for many definitions of "nice". Quotients... not so much. If you're dealing with arbitrary quotients, you can whip up some pretty hideous-looking spaces. The natural next question is whether there's some sort of topological property that is preserved by "sufficiently nice" quotients.

To cash out what "sufficiently nice" means, Hausdorffness is a very basic property on topological spaces, that's held by most spaces encountered in typical mathematical practice (type theory excepted), and topology gets a lot stranger if it isn't present. It's "given two distinct points, there are disjoint open neighborhoods around the two points". Basically, for any two distinct points x and y, it should be possible to come up with some notion of "close to x" and "close to y" that are mutually exclusive. So, we could demand that our quotient spaces at least be this nice.

 

Much nicer than that are compact metrizable spaces. Approximately, any space with a notion of distance, and for all $ϵ$, you can cover the space with finitely many patches of size $ϵ$. Well, actually, this isn't true, compactness is stronger than that, but I think it gets the spirit across. Examples of such spaces are finite batches of points, the space of all finite and infinite bitstrings, the space of probability distributions over a 256-dimensional hypersphere, the Mandelbrot set, and the space of all closed subsets of the interval [0,1]. They're extraordinarily nicely-behaved topologically while still managing to cover a healthy chunk of spaces that might be encountered in practice.

And, as it turns out, there is a lovely theorem that, for compact metrizable spaces $S$, if the quotient space $S/\sim$ happens to be Hausdorff (ie, not terrible), the quotient space will also be compact metrizable (about as nice as possible). Or at least, that's what Math StackExchange says. 

The rough idea behind the proof is that quotients of compact spaces are always compact, so that leaves metrizability. Using compactness of $S$ and Hausdorffness of $S/\sim$, it's possible to show the intermediate result that, for every set $K\subseteq S$ that's a union of equivalence classes and closed, you can take an open neighborhood of $K$ and it will contain a smaller open neighborhood which remains open when shoved through $\sim$. Using this ability to craft open neighborhoods that remain open even after applying $\sim$, you can push enough open sets forward into the quotient space $S/\sim$ to show that it's second-countable and regular (the regularity argument was skipped in the linked post but it's not hard to fill in). And now, you can invoke the Urysohn Metrization Theorem to show the quotient space is metrizable.

A nifty related theorem that we won't use anywhere is that every compact metric space arises as a quotient of the space of infinite bitstrings. $\{0,1{\}}^{\omega }$ is all you need.

 

So... what happens if we try to make all the stuff from "Finite Factored Sets" work with compact metrizable spaces, and we just restrict the sorts of partitions we're dealing with to the nice ones? (those where the resulting quotient space $S/{\sim }_X$ is Hausdorff.) Well then, everything works out exactly as you'd expect and you have to change no important definitions, except one direction of the fundamental theorem gets really dang hard and I gave up on it. The nice behavior of the quotient spaces works miracles to tame the infinite case.

Let's start running through the Finite Factored Sets posts, flagging everywhere which requires special care. For all results not specifically mentioned, assume it works out perfectly with very little effort involved in cleaning things up for the infinite case. As usual, feel free to gloss over proofs if you want, but at least read the discussion and theorem statements.

 

Countably Factored Spaces: Introduction and Factorization

Not much really changes here, except now we aren't dealing with just a batch of sets, we've got some topological structure on them too. And the permissible quotients have to respect the topology appropriately.

The first differences start showing up around definition 8. Since we aren't permitting just any old partition anymore, we need to put in some work to check that the intersection of nice partitions is a nice partition, especially since there can be uncountably many partitions!

 

Proposition 1: Given a compact metrizable space $S$, and a set of partitions $C$ s.t. for all $c\in C$, $S/{\sim }_c$ is Hausdorff, the partition $\bigvee C$, defined by $s_0{\sim }_{\bigvee C}{s}_1\leftrightarrow \forall c\in C:s_0{\sim }_c{s}_1$, has the property that $S/{\sim }_{\bigvee C}$ is Hausdorff.

Proof: Fix two distinct points in $S/{\sim }_{\bigvee C}$. These correspond to equivalence classes in $S$, so we'll write them as $[s_0{]}_{\bigvee C}$ and $[s_1{]}_{\bigvee C}$ for some distinguished $s_0$ and $s_1$. From this point on, a superscript of $p$ on an equivalence class like this means we'll be treating it as a point in a quotient space, a superscript of $e$ means we'll be treating it as an subset of $S$. 

Our task is to find open neighborhoods for those two points in $S/{\sim }_{\bigvee C}$ which don't overlap. Since they're distinct points in the quotient, the corresponding equivalence classes in $S$ are distinct, $s_0$ and $s_1$ are in different equivalence classes. There has to be some $c^{\ast }\in C$ s.t. $[s_0{]}_{c^{\ast }}^e\ne [s_1{]}_{c^{\ast }}^e$ (because otherwise, $s_0$ and $s_1$ would be in the same equivalence class according to ${\sim }_{\bigvee C}$, which is impossible).

What now? Well, now that we've got a $c^{\ast }$ that thinks that $s_0$ and $s_1$ are noticeably different, make a function $\varphi :S/{\sim }_{\bigvee C}\to S/{\sim }_{c^{\ast }}$ defined as $\varphi \left(\right[s{]}_{\bigvee C}^p):=[s{]}_{c^{\ast }}^p$. Basically, you can think of a point in $S/{\sim }_{\bigvee C}$ aka an equivalence class under $\bigvee C$, as being associated with one equivalence class for each $c\in C$, by how the intersection equivalence class is defined. And that tells you what point to map it to in $S/{\sim }_{c^{\ast }}$.

Next up, we'll show that $\varphi \circ {\sim }_{\bigvee C}={\sim }_{c^{\ast }}$. This is easy, we just take some $s\in S$, and go:

$\varphi \left({\sim }_{\bigvee C}\right(s\left)\right)=\varphi \left(\right[s{]}_{\bigvee C}^p)=[s{]}_{c^{\ast }}^p={\sim }_{c^{\ast }}\left(s\right)$

Done. Alright, now that we've got enough setup out of the way, we can start building our disjoint open neighborhoods. The two points $[s_0{]}_{c^{\ast }}^p$ and $[s_1{]}_{c^{\ast }}^p$ are distinct in $S/{\sim }_{c^{\ast }}$, because they correspond to the equivalence classes $[s_0{]}_{c^{\ast }}^e$ and $[s_1{]}_{c^{\ast }}^e$ in $S$ which are distinct. So, they've got some disjoint open neighborhoods $O_0$ and $O_1$, in $S/{\sim }_{c^{\ast }}$, since it's Hausdorff.

We will now let our disjoint open neighborhoods of $[s_0{]}_{\bigvee C}^p$ and $[s_1{]}_{\bigvee C}^p$ be  ${\varphi }^{-1}\left(O_0\right)$ and ${\varphi }^{-1}\left(O_1\right)$. They're disjoint because the preimage of any two disjoint sets is disjoint. They contain the requisite points because $\varphi \left(\right[s_0{]}_{\bigvee C}^p)=[s_0{]}_{c^{\ast }}^p\in O_0$, and the same for the other one. And they're open because their preimage under the quotient function ${\sim }_{\bigvee C}$ is open. To demonstrate this, we have

${\sim }_{\bigvee C}^{-1}\left({\varphi }^{-1}\right(O_0\left)\right)=(\varphi \circ {\sim }_{\bigvee C}{)}^{-1}(O_0)={\sim }_{c^{\ast }}^{-1}(O_0)$

Because we proved that the functions compose like that, and also, since ${\sim }_{c^{\ast }}$ is a continuous function $S\to S/{\sim }_{c^{\ast }}$, the preimage of an open is an open. And we're done! We got disjoint open neighborhoods for any two distinct points. $\square$

 

 

So, this is very nice. You can intersect nicely-behaved partitions however you wish, and it'll still stay as a nicely-behaved partition. There's very strong closure properties.

The next time we hit something nontrivial is around definition 10. A batch of partitions was defined to factorize a set iff the function mapping a point to the tuple of equivalence classes it's in is a bijection. But wait, we have topological structure now! As it turns out, amazingly enough, if that function $\pi :S\to {\prod }_{b\in B}S/{\sim }_b$ defined as $\pi \left(s\right)=\lambda b.{\sim }_b\left(s\right)$ is a bijection, it's actually going to be a homeomorphism! That's the topology version of an isomorphism, it's a continuous function with a continuous inverse, like the mapping back and forth between a donut and a coffee cup. The spaces have identical topological structure and we can consider them as basically the same.

This is quite nifty. Leaving $S$ with whatever topological structure it had originally, and equipping it with the product topology you get from the product of the various quotient spaces you made, are the same thing. So, our restriction on partitions implies the only factorizations available are those of the form "look at your space $S$ and realize it already had the topological structure of a cartesian product from the start, and the quotient functions are just projecting down on the various coordinates."

Since the definition of a finite factored set was essentially a pair of a set, and the batch of quotients/partitions which let you view the set as a product of other sets, this lets us analogously define a countably factored space as a pair of a nice-enough topological space, and the batch of quotients/partitions which let you view the space as a product of other topological spaces.

 

Definition 1: Countably Factored Space

A countably factored space is a $(S,B)$ pair, where $S$ is a compact metrizable space, and $B$ is a set of partitions ${\sim }_b$ s.t. $S/{\sim }_b$ is a compact metrizable space for all $b$, and the function $S\to {\prod }_{b\in B}S/{\sim }_b$ given by  $\lambda s.(\lambda b.{\sim }_b(s\left)\right)$ is a bijection (and actually, a homeomorphism, the topological structure is preserved, though this is nonobvious)

 

Proposition 2: If the function $\pi :\lambda s.(\lambda b.{\sim }_b(s\left)\right)$ is a bijection between $S$ (a compact metrizable space) and ${\prod }_{b\in B}S/{\sim }_b$, with all the $S/{\sim }_b$ being compact metrizable, then it's a homeomorphism.

We'll do this by showing that $\pi$ is continuous, and then using the fact that $\pi$ is a continuous bijection to show that ${\pi }^{-1}$ is continuous. We'll use $x$ for a point in the product space, and $x_b$ for the b'th coordinate.

First up, let's get a form for ${\pi }^{-1}$. The form of the inverse is ${\pi }^{-1}\left(x\right)={\bigcap }_{b\in B}{\sim }_b^{-1}\left(x_b\right)$. Map a batch of equivalence classes to their intersection. If there were multiple points in that intersection, then applying $\pi$ would map them to the same point (they're in the same list of equivalence classes), contradicting injectivity of $\pi$. And if there were no points in that intersection, then there'd be no point in $S$ with that particular combination of equivalence classes, contradicting surjectivity of $\pi$. 

To show that $\pi$ is continuous, take some base open set $O$ for ${\prod }_{b\in B}S/{\sim }_b$. By how the product topology works, there are finitely many $b_n$ and open sets $O_n\subseteq S/{\sim }_{b_n}$, s.t. $O=O_1\times O_2..\times O_n\times {\prod }_{b\in B/\{b_1...b_n\}}S/{\sim }_b$.

By how ${\pi }^{-1}$ is defined, and the fact that the set $O$ factorizes into the product of a bunch of other sets $O_b$ for each of the coordinates, we have

${\pi }^{-1}\left(O\right)={\bigcap }_{b\in B}{\sim }_b^{-1}\left(O_b\right)$

And then, unpack what the form of the various $O_b$ are.

$={\bigcap }_{b\in \{b_1...b_n\}}{\sim }_b^{-1}\left(O_n\right)\cap {\bigcap }_{b\in B/\{b_1...b_n\}}{\sim }_b^{-1}\left(S/{\sim }_b\right)$

$={\bigcap }_{b\in \{b_1...b_n\}}{\sim }_b^{-1}\left(O_n\right)\cap {\bigcap }_{b\in B/\{b_1...b_n\}}S={\bigcap }_{b\in \{b_1...b_n\}}{\sim }_b^{-1}\left(O_n\right)$

And bam, we've written the preimage of our base open, through the function $\pi$, as a finite intersection of preimages of open sets through continuous functions ${\sim }_b$. So it's a finite intersection of opens, and so is open. The preimage of all base opens is open.

This shows that $\pi$ is continuous, because you can write any open in the product space as a union of base opens, and the preimage of a union is the union of the preimages, so it'd be the union of a bunch of open sets, ie, open.

Now that we know $\pi$ is continuous, we'll show that ${\pi }^{-1}$ is. To do this, we'll show that the preimage of any closed set through ${\pi }^{-1}$ is closed (as that's equivalent to the preimage of any open set being open, ie, continuity.) The inverse of ${\pi }^{-1}$ is $\pi$, so we need to show that for any closed set in $S$, applying $\pi$ produces a closed set in the product space, and we'll have a continuous inverse.

This holds because, for any closed set $C\subseteq S$, since $S$ is a compact metrizable space, $C$ is compact. Also, $\pi \left(C\right)$ is compact, because applying a continuous function to a compact set makes a compact set. And, arbitrary products of Hausdorff spaces (our quotient spaces) are Hausdorff, and in any Hausdorff space, compact sets are closed, so $\pi \left(C\right)$ is closed.

Bam, ${\pi }^{-1}$ is continuous, and since we showed that $\pi$ is, it's a homeomorphism. $\square$

 

There's another result that I should mention now, because it's implicitly used in a lot of upcoming arguments, and it justifies the use of the term "countably factored space".

 

Proposition 3: Any compact metrizable space $S$ can only have countably many nontrivial factors.

Assume this is false, and there are uncountably many nontrivial factors. We can identify our compact metrizable space $S$ with ${\prod }_{b\in B}S/{\sim }_b$ by Proposition 2, there's the same topology. All factors are nontrivial, so each space $S/{\sim }_b$ has two distinct points in them. And all the $S/{\sim }_b$ are Hausdorff. Since it's an uncountable product, we can call upon the power of MathOverflow to conclude that ${\prod }_{b\in B}S/{\sim }_b$ isn't a first-countable space. But all compact metrizable spaces are first-countable, contradiction. $\square$

 

Past this point, everything works out precisely as it did in the original post.

 

Countably Factored Spaces: Conditional Orthogonality

We're going to skip proving that history exists the first time around, and all that ordinary orthogonality stuff, because Scott's posts had to run through the proofs a second time in greater generality for conditional everything, so we might as well just show that conditional history exists (and the other associated results), and go "conditioning on the entire space S recovers the ordinary case" so we only have to prove things once.

If a statement is not mentioned here or proved, assume it works out perfectly straightforwardly with no issues and requiring no special tricks. I'll only be focusing on the propositions which take a bit of work to generalize to the infinite case.

 

There is something important to note in this section. We can't condition on an arbitrary subset of $S$, it has to be closed! This is the same sort of topological restriction as the one we imposed on the quotients. Any closed subset of a compact metrizable space is compact metrizable too, so it's motivated by the same reasoning as what motivated the restriction on the quotients. It's far far easier to prove this fact though, since the argument for metrizability is just "if you've got a metric on the full space, the subspace inherits that metric". As usual, we'll restrict subpartitions to those which make the quotient space Hausdorff.

Our first order of business is going to be showing that if you've got a permissible partition $X$, then ${\sim }_X$ restricted to the closed set $E$ is a permissible partition of $E$. We'll actually show something considerably stronger, that the spaces $E/{\sim }_{X|E}$ and ${\sim }_X\left(E\right)$ (as a subspace of $S/{\sim }_X$) are homeomorphic. In other words, it doesn't matter whether you slice $E$ out first and then take a quotient of it, or take the quotient first and slice the image of $E$ out of the quotient space, you'll get the same space. So, in particular, you can go "$S/{\sim }_X$ is compact-metrizable, and ${\sim }_X\left(E\right)$ happens to be closed if $E$ is, so these two isomorphic spaces are also compact-metrizable". And this means that taking permissible quotients of a subspace works perfectly well and causes no issues.

 

Proposition 4: For a compact metrizable space $S$, closed subset $E$, and partition $X$ s.t. $S/{\sim }_X$ is Hausdorff, then $E/{\sim }_{X|E}$ and ${\sim }_X\left(E\right)$ are homeomorphic.

Our attempted homeomorphism $\varphi :E/{\sim }_{X|E}\to {\sim }_X\left(E\right)$ will be mapping the point $[s{]}_{X|E}^p$ (where $s\in E$) to $[s{]}_X^p$.

First off, we've gotta show injectivity. Let's say $[s_0{]}_{X|E}^p$ and $[s_1{]}_{X|E}^p$ are distinct in $E/{\sim }_{X|E}$. Then $\varphi \left(\right[s_0{]}_{X|E}^p)=[s_0{]}_X^p$, and similar for $s_1$. If these two points were identical, $[s_0{]}_X^p=[s_1{]}_X^p$, then the sets $[s_0{]}_X^e$ and $[s_1{]}_X^e$ would be identical in $S$, and so $s_0{\sim }_X{s}_1$, but $s_0,s_1\in E$, so $s_0{\sim }_{X|E}{s}_1$, and so $[s_0{]}_{X|E}^p=[s_1{]}_{X|E}^p$, but they're distinct points, contradiction.

Now for surjectivity. Fix some $[s{]}_X^p\in {\sim }_X(E)$. Then there's some $s^{\prime }\in E$ where ${\sim }_X\left(s^{\prime }\right)=[s{]}_X^p$. So, in particular, $[s^{\prime }{]}_X^p=[s{]}_X^p$. This point $s^{\prime }$, due to being in $E$, maps to the point $[s^{\prime }{]}_{X|E}^p\in E/{\sim }_{X|E}$. Then, we have $\varphi \left(\right[s^{\prime }{]}_{X|E}^p)=[s^{\prime }{]}_X^p=[s{]}_X^p$ And bam, we found a point that maps onto it. Surjectivity is established. It's a bijection. 

The inverse of the bijection maps $[s{]}_X^p$ to $[s^{\prime }{]}_{X|E}^p$, where $s^{\prime }$ is an arbitrary element of $E$ where $s^{\prime }{\sim }_{X}s$ (which must exist because $[s{]}_X^p$ is taken from the image of $E$).

Now, let's show continuity of $\varphi$. Fix an arbitrary open set $O$ in ${\sim }_X\left(E\right)$. By how the subspace topology works, $O=O^{\prime }\cap {\sim }_X\left(E\right)$, where $O^{\prime }$ is some open in $S/{\sim }_X$. We will attempt to show that ${\sim }_{X|E}^{-1}\left({\varphi }^{-1}\right(O\left)\right)=E\cap {\sim }_X^{-1}\left(O^{\prime }\right)$, establishing that the preimage of ${\varphi }^{-1}\left(O\right)$ is open in $E$ equipped with the subspace topology (intersection of $E$ and the preimage of an open, ie, an open), which would show that ${\varphi }^{-1}\left(O\right)$ is open in $E/{\sim }_{X|E}$ by how the quotient topology works, establishing the continuity of $\varphi$.

So, our proof goal switches to proving ${\sim }_{X|E}^{-1}\left({\varphi }^{-1}\right(O\left)\right)=E\cap {\sim }_X^{-1}\left(O^{\prime }\right)$

Let a point $s$ lie in the first set. Then it must be in $E$, and we must have that ${\sim }_{X|E}\left(s\right)\in {\varphi }^{-1}\left(O\right)$. Rewrite this a little bit as $[s{]}_{X|E}^p\in {\varphi }^{-1}(O)$, and then, by applying $\varphi$ to both sides, we have $[s{]}_X^p\in O\subseteq O^{\prime }$, establishing that $s\in {\sim }_X^{-1}\left(O^{\prime }\right)$. So, we have one subset inclusion direction, ${\sim }_{X|E}^{-1}\left({\varphi }^{-1}\right(O\left)\right)\subseteq E\cap {\sim }_X^{-1}\left(O^{\prime }\right)$

For the other subset inclusion direction, let a point $s$ lie in $E$, and applying ${\sim }_X$, we have $[s{]}_X^p\in O^{\prime }$. In particular, $[s{]}_X^p\in {\sim }_X(E)$, so we have $[s{]}_X^p\in O$.

Now, for this $s$, since it's in $E$, $\varphi \left({\sim }_{X|E}\right(s\left)\right)=\varphi \left(\right[s{]}_{X|E}^p)=[s{]}_X^p\in O$. So, it lies in the composition of preimages on the left side, and we have equality, which, by previous arguments, establishes that $\varphi$ is continuous.

Now, we'll show that $E/{\sim }_{X|E}$ is Hausdorff. Take two distinct points in it, shove them through $\varphi$ to get two distinct points in ${\sim }_X\left(E\right)$, use Hausdorffness of${\sim }_X\left(E\right)$ (which happens because $E$ is closed and so compact, and ${\sim }_X$ is continuous, so ${\sim }_X\left(E\right)$ is compact, and $S/{\sim }_X$ is compact metrizable, so ${\sim }_X\left(E\right)$ is a closed subset of a compact metrizable space and so is compact metrizable, and thus Hausdorff) to fit two disjoint open neighborhoods around your two points, then use continuity of $\varphi$ to show that ${\varphi }^{-1}$ pulls those disjoint open neighborhoods back to make disjoint open neighborhoods of your two original points in $E/{\sim }_{X|E}$.

Hm, $E/{\sim }_{X|E}$ is a Hausdorff quotient of a compact metrizable space ($E$) and so is compact metrizable. So, in particular, any closed set $C$ must be compact, and using continuity of $\varphi$, $\varphi \left(C\right)$ is compact, and by Hausdorffness of ${\sim }_X\left(E\right)$, $\varphi \left(C\right)$ is closed. So, $\varphi$ maps closed sets to closed sets. This is equivalent to the preimage of a closed set being closed, according to the function ${\varphi }^{-1}$. So, ${\varphi }^{-1}$ is continuous too, and we have a homeomorphism. $\square$

 

 

Alright, where to go from here? Well, things go perfectly fine up until you hit Proposition 21.5, the "conditional history exists" result. We'll need to strengthen it to arbitrary unions and intersections for things from here on out to work properly. In particular, it means that you can just intersect all the sets of coordinates $C$ where  $C⊢X$, to get a unique minimal set of coordinates that generates $X$, and bam, that's a history, but for the infinite case. Perfectly well-defined, no problems whatsoever.

 

Proposition 5 (Reproof of Proposition 21.5, Infinite History Remix:) If $X$ is a permissible subpartition, and there's a bunch of sets $C_i\subseteq B$ where $\forall i:C_i⊢X$, then ${\bigcap }_i{C}_i⊢X$, and ${\bigcup }_i{C}_i⊢X$.

The proofs of these two results are extremely similar, just flipped around, so we'll provide the general proof framework for both cases.

Step 1 is to show it for the intersection of two sets of coordinates, or the union of two sets of coordinates. Step 2 is to show it for the intersection of a descending sequence of sets of coordinates, or the union of an ascending sequence of sets of coordinates. Step 3 is to use steps 1 and 2 and "there's only countably many coordinates" to prove the whole thing.

The proof of Step 1 perfectly follows the way it works in Scott's post, there's no meaningful differences going on, the exact same argument works.

For the proof of step 2, we'll given the argument for intersection (and for union in parentheses). Fix a sequence of sets $C_n$ s.t. $C_0\supseteq C_1\supseteq C_2...$ (or, for union, have $\subseteq$ instead).

Now, for any particular coordinate $b$, if $b\in {\bigcap }_n{C}_n$ (for union, $b\notin {\bigcup }_n{C}_n$), then it'll be in all the $C_n$ (none of the $C_n$), 

so for intersections we have $\left({\chi }_{{\bigcap }_n{C}_n}\right(s,t){)}_b=s_b={lim}_{n\to \infty }({\chi }_{C_n}(s,t){)}_b$

and for unions we have $\left({\chi }_{{\bigcup }_n{C}_n}\right(s,t){)}_b=t_b={lim}_{n\to \infty }({\chi }_{C_n}(s,t){)}_b$

now, if $b\notin {\bigcap }_n{C}_n$ (for union, $b\in {\bigcup }_n{C}_n$), then there's some finite $n$ where $C_n$ excludes $b$ (includes $b$), and then it never returns after that (always is present after that) because the $C_n$ get smaller (larger) as $n$ increases. So, again, for $b$ like that,

for intersections, we have $\left({\chi }_{{\bigcap }_n{C}_n}\right(s,t){)}_b=t_b={lim}_{n\to \infty }({\chi }_{C_n}(s,t){)}_b$

and for unions we have $\left({\chi }_{{\bigcup }_n{C}_n}\right(s,t){)}_b=s_b={lim}_{n\to \infty }({\chi }_{C_n}(s,t){)}_b$

So, since we have convergence in each individual coordinate, and there's only countably many coordinates, this means that ${\chi }_{{\bigcap }_n{C}_n}(s,t)={lim}_{n\to \infty }{\chi }_{C_n}(s,t)$ (for union, just switch the intersection to a union).

Now, since all the $C_n⊢X$, this means that all the ${\chi }_{C_n}(s,t)$ will land in $[s{]}_X$, which is a closed set (single points are closed in Hausdorff spaces, the preimage of a closed set through a continuous function is closed, so $[s{]}_X$ is closed). Thus, the limit point will also land in $[s{]}_X$, establishing that ${\bigcap }_n{C}_n⊢X$ (or ${\bigcup }_n{C}_n⊢X$)

Now for step 3. Again, the union argument is in parentheses. Given your collection of sets $C_i$, index the coordinates by $N$, there's only countably many coordinates. For coordinate $n$, if $n\in {\bigcap }_i{C}_i$ (or $n\notin {\bigcup }_i{C}_i$), then let $C_n$ be whatever set $C_i$ you want. If $n\notin {\bigcap }_i{C}_i$ (or $n\in {\bigcup }_i{C}_i$), then let $C_n$ be some $C_i$ which excludes (includes) the coordinate $n$, which must exist. Now, we can go

${\bigcap }_{i\in I}{C}_i={\bigcap }_{n\in N}{C}_n={\bigcap }_{n\in N}{\bigcap }_{m\le n}{C}_m$

(or for union) ${\bigcup }_{i\in I}{C}_i={\bigcup }_{n\in N}{C}_n={\bigcup }_{n\in N}{\bigcup }_{m\le n}{C}_m$

Basically, since our $C_n$ were picked to exclude (include) every coordinate it's possible to exclude (include), we can rewrite our big intersection (union) as a countable intersection (union). Then just rewrite a bit.

Now, for each $n$, we have ${\bigcap }_{m\le n}{C}_m⊢X$ (or ${\bigcup }_{m\le n}{C}_m⊢X$) because we proved the finite intersection (union) case and can use induction. And the sequence $C_0,C_0\cap C_1,C_0\cap C_1\cap C_2...$ (same thing but with $\cup$) is a descending (ascending) sequence of sets, so we can apply our proof from that case to establish that ${\bigcap }_{i\in I}{C}_i={\bigcap }_{n\in N}{\bigcap }_{m\le n}{C}_m⊢X$ (or  ${\bigcup }_{i\in I}{C}_i={\bigcup }_{n\in N}{\bigcup }_{m\le n}{C}_m⊢X$) and we're done! $\square$

 

 

Ok, now that that's taken care of... is there anything else on the list that may be particularly difficult? Well, our next spot of mild trouble is in Proposition 23, specifically, the part about showing that the history of a supremum of partitions is the union of the histories of the component parts.

 

Proposition 6 (Reproof of Proposition 23.2): Given $X_i$, a collection of subpartitions all with the same domain, we have $h(\bigvee X_i)={\bigcup }_{i\in I}h\left(X_i\right)$.

So, one direction of this, that $\forall j:h(\bigvee X_i)⊢X_j$ to show that the history of the supremum is as larger or larger than the union of all the other histories, is pretty easy. We have that $\bigvee X_i{\ge }_E{X}_j$ for all $j$, so the history of $\bigvee X_i$ manages to generate $X_j$, for all $j$, so all the $h\left(X_i\right)$ are a subset of the history of $\bigvee X_i$, establishing that $h(\bigvee X_i)\supseteq {\bigcup }_{i\in I}h\left(X_i\right)$.

  The other subset direction, which will be established by showing ${\bigcup }_{i\in I}h\left(X_i\right)⊢\bigvee X_i$, requires taking a bit more care. Our first order of business is showing that $\bigvee X_i{\le }_E{\bigcup }_{i\in I}h\left(X_i\right)|E$. Assume that two points, $s$ and $t$, both in $E$, fulfill $s{\sim }_{{\bigcup }_{i\in I}h\left(X_i\right)}t$. Then, we have $\forall i\in I:s{\sim }_{h\left(X_i\right)}t$. And since $h\left(X_i\right)⊢X_i$ for all $i$, and $s,t$ are both in $E$, this implies $\forall i\in I:s{\sim }_{X_i}t$. Which is equivalent to $s{\sim }_{\bigvee X_i}t$. And so, we have established that inequality.

But that isn't enough, the last piece we need to conclude the argument is that ${\chi }_{{\bigcup }_{i\in I}h\left(X_i\right)}(E,E)=E$. We'll do this by showing that for arbitrary $s,t\in E$, that ${\chi }_{{\bigcup }_{i\in I}h\left(X_i\right)}(s,t)\in E$. First off, we can go 

${\chi }_{{\bigcup }_{i\in I}h\left(X_i\right)}(s,t)={\chi }_{{\bigcup }_n{\bigcup }_{m\le n}h\left(X_m\right)}(s,t)={lim}_{n\to \infty }{\chi }_{{\bigcup }_{m\le n}h\left(X_m\right)}(s,t)$

The first inequality was the same sort of ascending/descending countable chain argument used to make a sequence of ever-larger sets in Proposition 6. Then, we just use the usual limit argument with that of "each coordinate individually converges, so we have overall convergence". Now, if we knew that each ${\chi }_{{\bigcup }_{m\le n}h\left(X_m\right)}(s,t)$ was in $E$, then by closure of $E$, we'd have that our desired point lands in $E$. So, we just have to show these finite stages land in $E$. We do this with an induction proof. Clearly, ${\chi }_{h\left(X_0\right)}(s,t)\in E$, because $h\left(X_0\right)⊢X_0$, so ${\chi }_{h\left(X_0\right)}(E,E)=E$. For the induction step, we go

${\chi }_{{\bigcup }_{m\le n+1}h\left(X_m\right)}(s,t)={\chi }_{h\left(X_{n+1}\right)}(s,{\chi }_{{\bigcup }_{m\le n}h\left(X_m\right)}(s,t\left)\right)\in E$

Where that last inclusion is because, by induction assumption, ${\chi }_{{\bigcup }_{m\le n}h\left(X_m\right)}(s,t)\in E$, and also $h\left(X_{n+1}\right)⊢X_{n+1}$.

And so, we have that ${\chi }_{{\bigcup }_{i\in I}h\left(X_i\right)}(E,E)=E$, and so we've established that ${\bigcup }_{i\in I}h\left(X_i\right)⊢\bigvee X_i$, establishing the other subset inclusion direction, and thus equality. $\square$

 

 

Alright, where is this heading? Well, the semigraphoid axioms, of course. The only roadblock left is that we have to reprove Lemma 2 from scratch. The old proof no longer suffices due to using impermissible partitions, and the old proof path cannot be repaired.

 

Proposition 7 (reproof of Lemma 2): Let $X,Y$ be subpartitions, and $E$ be their domain. Then $h(X\vee Y)=h\left(X\right)\cup {\bigcup }_{x\in X}h\left(Y|x\right)$.

Proof. Since $X{\le }_{E}X{\vee }_{E}Y$, we have $h\left(X\right)\subseteq h(X\vee Y)$. Symmetrically, for all $x\in X$, since $Y|x\subseteq X\vee Y$, we have $h\left(Y|x\right)\subseteq h(X\vee Y)$ by Proposition 23 in Scott's paper. Thus, $h(X\vee Y)\supseteq h\left(X\right)\cup {\bigcup }_{x\in X}h\left(Y|x\right)$. One direction down, one to go.

In order to begin attacking the reverse direction, our first order of business is taking a detour to establish that $h\left(X\right)\cup {\bigcup }_{x\in X}h\left(Y|x\right)⊢In{d}_E$, the indiscrete partition of $E$. In order to do this, we'll show that for any particular $x\in X$, $h\left(X\right)\cup h\left(Y|x\right)⊢In{d}_E$. Then, just yeet Proposition 5 (from this post) at that to show our desired result, that you can union everything together and it'll still generate $In{d}_E$.

So, let $x$ be arbitrary in $X$, and $r$ be an arbitrary point in $x$, and $s,t$ be arbitrary points in $E$.

${\chi }_{h\left(X\right)\cup h\left(Y|x\right)}(s,t)={\chi }_{h\left(X\right)}(s,{\chi }_{h\left(Y|x\right)}(s,t\left)\right)={\chi }_{h\left(X\right)}(s,{\chi }_{h\left(X\right)}(r,{\chi }_{h\left(Y|x\right)}(s,t)\left)\right)$

$={\chi }_{h\left(X\right)}(s,{\chi }_{h\left(Y|x\right)}({\chi }_{h\left(X\right)}(r,s),{\chi }_{h\left(X\right)}(r,t)\left)\right)$

And both ${\chi }_{h\left(X\right)}(r,s)$ and ${\chi }_{h\left(X\right)}(r,t)$ land in $[r{]}_X=x$, because $h\left(X\right)⊢X$ and $r,s,t$ are all in $E$.

Accordingly, ${\chi }_{h\left(Y|x\right)}\left({\chi }_{h\left(X\right)}\right(r,s),{\chi }_{h\left(X\right)}(r,t\left)\right)\in \left[{\chi }_{h\left(X\right)}\right(r,s){]}_Y\subseteq E$, because $h\left(Y|x\right)⊢Y|x$, and both of the chi thingies land in $x$. And then, since both $s$ and the long ${\chi }_{h\left(Y|x\right)}$ term land in $E$, ${\chi }_{h\left(X\right)}(s,stuff)$ lands in $E$. And so, since s and t were arbitrary in $E$, we have established that ${\chi }_{h\left(X\right)\cup h\left(Y|x\right)}(E,E)=E$, which is sufficient by itself to establish that $h\left(X\right)\cup h\left(Y|x\right)⊢In{d}_E$ for our arbitrary $x$. And then, by Proposition 5, $h\left(X\right)\cup {\bigcup }_{x\in X}h\left(Y|x\right)⊢In{d}_E$.

At this point, we can back out of the lemma and resume our work of showing that this batch of histories is capable of generating $X{\vee }_{E}Y$.

We'll be using the definition of generation where we try to show that if $s$ and $t$ lie in the appropriate set ($E$ in this case), then chimera-ing them together lands in the same equivalence class as $s$. We have

${\chi }_{h\left(X\right)\cup {\bigcup }_{x\in X}h\left(Y|x\right)}(s,t)={\chi }_{h\left(Y|\right[s{]}_X)}(s,{\chi }_{h\left(X\right)}(s,{\chi }_{h\left(X\right)\cup {\bigcup }_{x\in X}h\left(Y|x\right)}(s,t)\left)\right)$

Now, since we had previously derived that $h\left(X\right)\cup {\bigcup }_{x\in X}h\left(Y|x\right)⊢In{d}_E$, that means that ${\chi }_{h\left(X\right)\cup {\bigcup }_{x\in X}h\left(Y|x\right)}(s,t)\in E$. Moving out one layer, ${\chi }_{h\left(X\right)}(s,stuff)$ has both components landing in $E$, and $h\left(X\right)⊢X$, so that result will land in $[s{]}_X$.

Moving out another layer from that, ${\chi }_{h(Y,[s{]}_X)}(s,stuff)$ has both components landing in $[s{]}_X$, and $h\left(Y|\right[s{]}_X)⊢Y|[s{]}_X$, so the result will land in $[s{]}_{Y|[s{]}_X}$, aka $[s{]}_Y\cap [s{]}_X$, aka $[s{]}_{X\vee Y}$. And we're done! Our collection of histories generates $X\vee Y$. $\square$

 

 

But of course, all of this was just a warmup for showing the semigraphoid axioms, which... go suprisingly smoothly. Most of the aggrivation was concentrated in reproving Lemma 2.

 

Countably Factored Spaces: Polynomials and Probability

And then things go poorly right around here. Or at least, there's a big difficulty spike if you're trying to rescue all results. Apparently, for Daniel's "countable sets" case, since there can only be finitely many coordinates, you only have to deal with power series (generalization of polynomials) involving sums of countably many terms of finitely many variables each, which is a little tricky, but doable, and TurnTrout did it.

But here, when I tried, I wound up dealing with sums of uncountably many terms, consisting of countably many variables each. Which, apparently, don't work well at all. Now, an uncountable sum over infinitesimally small things is kinda like an integral, or taking the union of a bunch of points to make a set, and as it turns out, a whole bunch of the results in this section have analogues if you swap out the polynomial of a set for the set itself.

With this reframing, Proposition 26 becomes trivial, and Proposition 27 turns into the statement that chimera-ing sets together can be viewed as projecting them down to the appropriate coordinates, and then taking the product of those. 

Let's use $S_C$ as an abbreviation for ${\prod }_{b\in C}S/{\sim }_b$, basically, the space you get when you project down to the factors in $C$. Put another way, Proposition 27 is basically saying that, when $C_0$ and $C_1$ are disjoint sets of coordinates, then

$p{r}_{S_{C_0\cup C_1}}\left({\chi }_{C_0}\right(E_0,E_1\left)\right)=p{r}_{S_{C_0}}\left(E_0\right)\times p{r}_{S_{C_1}}\left(E_1\right)$

This can be trivially verified from understanding what the chimera function does. $p{r}_{S_{C_0}}\left(E_0\right)$ are the possible coordinate values for the coordinates in $C_0$ which are available for use by the chimera function, and $p{r}_{B/S_{C_0}}\left(E_1\right)$ are the possible coordinate values for the coordinates in $B/S_{C_0}$ which are available for use by the chimera function, and the chimera function can put these together however it wishes, making the set $p{r}_{S_{C_0}}\left(E_0\right)\times p{r}_{B/S_{C_0}}\left(E_1\right)$. Project out some extra coordinates, and you get the result.

Proposition 28 turns into the statement that, given a set $E\subseteq S$ that factorizes as $F\times G$, you can just let $C$ be the set of relevant coordinates for the set $F$, and write $F$ and $G$ as $p{r}_{S_C}\left(E\right)$ and $p{r}_{S_{B/C}}\left(E\right)$.

Propositions 29 and 30 turn into the statement that given some set $E$, there's a way to split it into as many factors as possible, until eventually you hit a batch of "irreducible pieces", sets of coordinates $C$ where $p{r}_C\left(E\right)$ just can't be factorized any further, it's an odd shape, and that these sets of coordinates partition $B$, and multiplying these things together makes $E$ again. The rough proof path for this is showing that given any way of factorizing $E$ in two different ways using coordinates $(C_0,B/C_0)$ in one way, and $(C_1,B/C_1)$ in another way, then $(C_0\cap C_1,B/(C_0\cap C_1\left)\right)$ is also a factorization of the set. Then we do our usual sort of argument with the countable descending chains to get that for any particular coordinate $b$, there's a minimal set of coordinates including $b$ that don't let you factor the set any more.

It's slightly tricky to show, but Lemma 3 carries over and shows an equivalence between $X\perp Y|Z$, and the statement "for all $x,y,$ and $z$, if you decompose $x\cap z$ and $y\cap z$ into irreducible pieces (be very sure to label all pieces with the coordinates they're pinning down,  to make the pieces distinguishable), and throw them into a multiset, it'll be the same as decomposing $z$ and $x\cap y\cap z$ into irreducible pieces and throwing those pieces into a multiset"

But, sadly, when we go to the Fundamental Theorem of Finite Factored Sets, it's just too hard (for me personally, you may be different) to show that probabilistic independence implies two multisets of irreducible pieces (labeled with coordinates) are identical.

But, it is pretty easy to get the other direction, where conditional orthogonality implies conditional independence. Well, kinda. I'd ideally like to strengthen it to talk about conditional probabilities (if it's very improbable to select any particular event $z$), but I only proved the unconditional probabilities version, though a slightly stronger version than was originally stated.

 

Proposition 7 (reproof of one direction of the fundamental theorem): Given any factorized probability distribution $\mu$, permissible partitions $X,Y,Z$ s.t. $X\perp Y|Z$, subsets $X^{\prime }\subseteq X$ and $Y^{\prime }\subseteq Y$, and $z\in Z$, then

$P_{\mu }({\bigcup }_{x\in X^{\prime }}x\cap z)\cdot P_{\mu }({\bigcup }_{y\in Y^{\prime }}y\cap z)=P_{\mu }({\bigcup }_{x\in X^{\prime }}x\cap {\bigcup }_{y\in Y^{\prime }}y\cap z)\cdot P_{\mu }\left(z\right)$

Proof: Since $X\perp Y|Z$, this means that for all $z\in Z$, we have $h\left(X|z\right)\cap h\left(Y|z\right)=\varnothing$. Use $C$ to abbreviate $h\left(X|z\right)$. Now, clearly, by the definition of $⊢$, we have ${\chi }_C(z,z)=z$, so we also have ${\chi }_{B/C}(z,z)=z$. Also, $h\left(Y|z\right)\subseteq B/C$, so $Y|z{\le }_{z}h\left(Y|z\right)|z{\le }_z\bigvee \left(B/C\right)|z$  and so this means that $B/C⊢Y|z$.

Since $C⊢X|z$ (remember, it's $h\left(X|z\right)$), we have that for all $x\in X$, ${\chi }_C(x\cap z,z)=x\cap z$. Rephrasing this somewhat, it's saying $p{r}_{S_C}(x\cap z)\times p{r}_{S_{B/C}}\left(z\right)=x\cap z$ for all $x$. Accordingly, we have

${\bigcup }_{x\in X^{\prime }}x\cap z={\bigcup }_{x\in X^{\prime }}\left(p{r}_{S_C}\right(x\cap z)\times p{r}_{S_{B/C}}(z\left)\right)$

$=\left({\bigcup }_{x\in X^{\prime }}\right(p{r}_{S_C}(x\cap z))\times p{r}_{S_{B/C}}\left(z\right)=p{r}_{S_C}({\bigcup }_{x\in X^{\prime }}x\cap z)\times p{r}_{S_{B/C}}\left(z\right)$

Also, since $B/C⊢Y|z$, we can run through similar arguments to get that

${\bigcup }_{y\in Y^{\prime }}y\cap z=p{r}_{S_{B/C}}({\bigcup }_{y\in Y^{\prime }}y\cap z)\times p{r}_{S_C}\left(z\right)$

And, since we have

${\chi }_C({\bigcup }_{x\in X^{\prime }}x\cap z,{\bigcup }_{y\in X^{\prime }}y\cap z)\subseteq {\chi }_C({\bigcup }_{x\in X^{\prime }}x\cap z,z)={\bigcup }_{x\in X^{\prime }}x\cap z$

and

${\chi }_C({\bigcup }_{x\in X^{\prime }}x\cap z,{\bigcup }_{y\in X^{\prime }}y\cap z)\subseteq {\chi }_C(z,{\bigcup }_{y\in X^{\prime }}y\cap z)={\chi }_{B/C}({\bigcup }_{y\in X^{\prime }}y\cap z,z)={\bigcup }_{y\in Y^{\prime }}y\cap z$

This means that we have

${\chi }_C({\bigcup }_{x\in X^{\prime }}x\cap z,{\bigcup }_{y\in Y^{\prime }}y\cap z)\subseteq {\bigcup }_{x\in X^{\prime }}x\cap {\bigcup }_{y\in Y^{\prime }}y\cap z$

But, hang on, those sets we're chimera-ing together are projections of sets as large or larger than the intersection of $X^{\prime },Y^{\prime }$, and $z$, so we must have equality there. 

Accordingly, we can use that factorization and get

${\bigcup }_{x\in X^{\prime }}x\cap {\bigcup }_{y\in Y^{\prime }}y\cap z=p{r}_{S_C}({\bigcup }_{x\in X^{\prime }}x\cap z)\times p{r}_{S_{B/C}}({\bigcup }_{y\in Y^{\prime }}y\cap z)$

and also, since we had ${\chi }_C(z,z)=z$, this means that $z=p{r}_{S_C}\left(z\right)\times p{r}_{S_{B/C}}\left(z\right)$

And so, throwing probabilities in the mix, we have

$P_{\mu }({\bigcup }_{x\in X^{\prime }}x\cap z)\cdot P_{\mu }({\bigcup }_{y\in Y^{\prime }}y\cap z)$

$=P_{{\mu }_C}\left(p{r}_{S_C}\right({\bigcup }_{x\in X^{\prime }}x\cap z\left)\right)\cdot P_{{\mu }_{B/C}}\left(p{r}_{S_{B/C}}\right(z\left)\right)+P_{{\mu }_{B/C}}\left(p{r}_{S_{B/C}}\right({\bigcup }_{y\in Y^{\prime }}y\cap z\left)\right)\cdot P_{{\mu }_C}\left(p{r}_{S_C}\right(z\left)\right)$

$=P_{\mu }({\bigcup }_{x\in X^{\prime }}x\cap {\bigcup }_{y\in Y^{\prime }}y\cap z)\cdot P_{\mu }\left(z\right)$

And we're done! $\square$

 

 

Best of luck on trying to show the reverse direction!

3 comments

Comments sorted by top scores.