Countable Factored Spaces

by Diffractor26 min read9th Sep 20211 comment

22

AI
Frontpage

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

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  be the intersection of all the sets  s.t. . 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 , then a partition  induces a function , which maps a point to the unique equivalence class it's in. Then, we just need to stick a topology on the set , which ends up being "put as many open sets in  as you can while keeping the function  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 

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 , if the quotient space  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  and Hausdorffness of , it's possible to show the intermediate result that, for every set  that's a union of equivalence classes and closed, you can take an open neighborhood of  and it will contain a smaller open neighborhood which remains open when shoved through . Using this ability to craft open neighborhoods that remain open even after applying , you can push enough open sets forward into the quotient space  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.  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  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.

 

Countable 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 , and a set of partitions  s.t. for all  is Hausdorff, the partition , defined by , has the property that  is Hausdorff.

Proof: Fix two distinct points in . These correspond to equivalence classes in , so we'll write them as  and  for some distinguished  and . From this point on, a superscript of  on an equivalence class like this means we'll be treating it as a point in a quotient space, a superscript of  means we'll be treating it as an subset of 

Our task is to find open neighborhoods for those two points in  which don't overlap. Since they're distinct points in the quotient, the corresponding equivalence classes in  are distinct,  and  are in different equivalence classes. There has to be some  s.t.  (because otherwise,  and  would be in the same equivalence class according to , which is impossible).

What now? Well, now that we've got a  that thinks that  and  are noticeably different, make a function  defined as . Basically, you can think of a point in  aka an equivalence class under , as being associated with one equivalence class for each , by how the intersection equivalence class is defined. And that tells you what point to map it to in .

Next up, we'll show that . This is easy, we just take some , and go:

Done. Alright, now that we've got enough setup out of the way, we can start building our disjoint open neighborhoods. The two points  and  are distinct in , because they correspond to the equivalence classes  and  in  which are distinct. So, they've got some disjoint open neighborhoods  and , in , since it's Hausdorff.

We will now let our disjoint open neighborhoods of  and  be   and . They're disjoint because the preimage of any two disjoint sets is disjoint. They contain the requisite points because , and the same for the other one. And they're open because their preimage under the quotient function  is open. To demonstrate this, we have

Because we proved that the functions compose like that, and also, since  is a continuous function , the preimage of an open is an open. And we're done! We got disjoint open neighborhoods for any two distinct points. 

 

 

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 factorizes 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  defined as  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  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  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."

 

Proposition 2: If the function  is a bijection between  (a compact metrizable space) and , then it's a homeomorphism.

We'll do this by showing that  is continuous, and then using the fact that  is a continuous bijection to show that  is continuous. We'll use  for a point in the product space, and  for the b'th coordinate.

First up, let's get a form for . The form of the inverse is . Map a batch of equivalence classes to their intersection. If there were multiple points in that intersection, then applying  would map them to the same point (they're in the same list of equivalence classes), contradicting injectivity of . And if there were no points in that intersection, then there'd be no point in  with that particular combination of equivalence classes, contradicting surjectivity of 

To show that  is continuous, take some base open set  for . By how the product topology works, there are finitely many  and open sets , s.t. .

By how  is defined, and the fact that the set  factorizes into the product of a bunch of other sets  for each of the coordinates, we have

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

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

This shows that  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  is continuous, we'll show that  is. To do this, we'll show that the preimage of any closed set through  is closed (as that's equivalent to the preimage of any open set being open, ie, continuity.) The inverse of  is , so we need to show that for any closed set in , applying  produces a closed set in the product space, and we'll have a continuous inverse.

This holds because, for any closed set , since  is a compact metrizable space,  is compact. Also,  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  is closed.

Bam,  is continuous, and since we showed that  is, it's a homeomorphism. 

 

 

There's another result that I should mention now, because it's implicitly used in a lot of upcoming arguments.

 

Proposition 3: Any compact metrizable space  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  with  by Proposition 2, there's the same topology. All factors are nontrivial, so each space  has two distinct points in them. And all the  are Hausdorff. Since it's an uncountable product, we can call upon the power of MathOverflow to conclude that  isn't a first-countable space. But all compact metrizable spaces are first-countable, contradiction. 

 

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

 

Countable 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 , 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 , then  restricted to the closed set  is a permissible partition of . We'll actually show something considerably stronger, that the spaces  and  (as a subspace of ) are homeomorphic. In other words, it doesn't matter whether you slice  out first and then take a quotient of it, or take the quotient first and slice the image of  out of the quotient space, you'll get the same space. So, in particular, you can go " is compact-metrizable, and  happens to be closed if  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 , closed subset , and partition  s.t.  is Hausdorff, then  and  are homeomorphic.

Our attempted homeomorphism  will be mapping the point  (where ) to .

First off, we've gotta show injectivity. Let's say  and  are distinct in . Then , and similar for . If these two points were identical, , then the sets  and  would be identical in , and so , but , so , and so , but they're distinct points, contradiction.

Now for surjectivity. Fix some . Then there's some  where . So, in particular, . This point , due to being in , maps to the point . Then, we have  And bam, we found a point that maps onto it. Surjectivity is established. It's a bijection. 

The inverse of the bijection maps  to , where  is an arbitrary element of  where  (which must exist because  is taken from the image of ).

Now, let's show continuity of . Fix an arbitrary open set  in . By how the subspace topology works, , where  is some open in . We will attempt to show that , establishing that the preimage of  is open in  equipped with the subspace topology (intersection of  and the preimage of an open, ie, an open), which would show that  is open in  by how the quotient topology works, establishing the continuity of .

So, our proof goal switches to proving 

Let a point  lie in the first set. Then it must be in , and we must have that . Rewrite this a little bit as , and then, by applying  to both sides, we have , establishing that . So, we have one subset inclusion direction, 

For the other subset inclusion direction, let a point  lie in , and applying , we have . In particular, , so we have .

Now, for this , since it's in . So, it lies in the composition of preimages on the left side, and we have equality, which, by previous arguments, establishes that  is continuous.

Now, we'll show that  is Hausdorff. Take two distinct points in it, shove them through  to get two distinct points in , use Hausdorffness of (which happens because  is closed and so compact, and  is continuous, so  is compact, and  is compact metrizable, so  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  to show that  pulls those disjoint open neighborhoods back to make disjoint open neighborhoods of your two original points in .

Hm,  is a Hausdorff quotient of a compact metrizable space () and so is compact metrizable. So, in particular, any closed set  must be compact, and using continuity of  is compact, and by Hausdorffness of  is closed. So,  maps closed sets to closed sets. This is equivalent to the preimage of a closed set being closed, according to the function . So,  is continuous too, and we have a homeomorphism. 

 

 

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  where  , to get a unique minimal set of coordinates that generates , 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  is a permissible subpartition, and there's a bunch of sets  where , then , and .

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  s.t.  (or, for union, have  instead).

Now, for any particular coordinate , if  (for union, ), then it'll be in all the  (none of the ), 

so for intersections we have 

and for unions we have 

now, if  (for union, ), then there's some finite  where  excludes  (includes ), and then it never returns after that (always is present after that) because the  get smaller (larger) as  increases. So, again, for  like that,

for intersections, we have 

and for unions we have 

So, since we have convergence in each individual coordinate, and there's only countably many coordinates, this means that  (for union, just switch the intersection to a union).

Now, since all the , this means that all the  will land in , 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  is closed). Thus, the limit point will also land in , establishing that  (or )

Now for step 3. Again, the union argument is in parentheses. Given your collection of sets , index the coordinates by , there's only countably many coordinates. For coordinate , if  (or ), then let  be whatever set  you want. If  (or ), then let  be some  which excludes (includes) the coordinate , which must exist. Now, we can go

(or for union) 

Basically, since our  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 , we have  (or ) because we proved the finite intersection (union) case and can use induction. And the sequence  (same thing but with ) is a descending (ascending) sequence of sets, so we can apply our proof from that case to establish that  (or  ) and we're done! 

 

 

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 , a collection of subpartitions all with the same domain, we have .

So, one direction of this, that  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  for all , so the history of  manages to generate , for all , so all the  are a subset of the history of , establishing that .

  The other subset direction, which will be established by showing , requires taking a bit more care. Our first order of business is showing that . Assume that two points,  and , both in , fulfill . Then, we have . And since  for all , and  are both in , this implies . Which is equivalent to . And so, we have established that inequality.

But that isn't enough, the last piece we need to conclude the argument is that . We'll do this by showing that for arbitrary , that . First off, we can go 

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  was in , then by closure of , we'd have that our desired point lands in . So, we just have to show these finite stages land in . We do this with an induction proof. Clearly, , because , so . For the induction step, we go

Where that last inclusion is because, by induction assumption, , and also .

And so, we have that , and so we've established that , establishing the other subset inclusion direction, and thus equality. 

 

 

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  be subpartitions, and  be their domain. Then .

Proof. Since , we have . Symmetrically, for all , since , we have  by Proposition 23 in Scott's paper. Thus, . 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 , the indiscrete partition of . In order to do this, we'll show that for any particular . 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 .

So, let  be arbitrary in , and  be an arbitrary point in , and  be arbitrary points in .

And both  and  land in , because  and  are all in .

Accordingly, , because , and both of the chi thingies land in . And then, since both  and the long  term land in  lands in . And so, since s and t were arbitrary in , we have established that , which is sufficient by itself to establish that  for our arbitrary . And then, by Proposition 5, .

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 .

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

Now, since we had previously derived that , that means that . Moving out one layer,  has both components landing in , and , so that result will land in .

Moving out another layer from that,  has both components landing in , and , so the result will land in , aka , aka . And we're done! Our collection of histories generates 

 

 

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.

 

Countable 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  as an abbreviation for , basically, the space you get when you project down to the factors in . Put another way, Proposition 27 is basically saying that, when  and  are disjoint sets of coordinates, then

This can be trivially verified from understanding what the chimera function does.  are the possible coordinate values for the coordinates in  which are available for use by the chimera function, and  are the possible coordinate values for the coordinates in  which are available for use by the chimera function, and the chimera function can put these together however it wishes, making the set . Project out some extra coordinates, and you get the result.

Proposition 28 turns into the statement that, given a set  that factorizes as , you can just let  be the set of relevant coordinates for the set , and write  and  as  and .

Propositions 29 and 30 turn into the statement that given some set , 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  where  just can't be factorized any further, it's an odd shape, and that these sets of coordinates partition , and multiplying these things together makes  again. The rough proof path for this is showing that given any way of factorizing  in two different ways using coordinates  in one way, and  in another way, then  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 , there's a minimal set of coordinates including  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 , and the statement "for all  and , if you decompose  and  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  and  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 ), 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 , permissible partitions  s.t. , subsets  and , and , then

Proof: Since , this means that for all , we have . Use  to abbreviate . Now, clearly, by the definition of , we have , so we also have . Also, , so   and so this means that .

Since  (remember, it's ), we have that for all . Rephrasing this somewhat, it's saying  for all . Accordingly, we have

Also, since , we can run through similar arguments to get that

And, since we have

and

This means that we have

But, hang on, those sets we're chimera-ing together are projections of sets as large or larger than the intersection of , and , so we must have equality there. 

Accordingly, we can use that factorization and get

and also, since we had , this means that 

And so, throwing probabilities in the mix, we have

And we're done! 

 

 

Best of luck on trying to show the reverse direction!

AI2
Frontpage

22

1 comments, sorted by Highlighting new comments since Today at 5:55 AM
New Comment

Note that the title is misleading. This is really countable dimension factored spaces, which is much better, since it allows for the possibility of something kind of like continuous time, where between any two points in time, you can specify a time strictly between them.