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
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!