LBIT Proofs 3: Propositions 19-22

post by Diffractor · 2020-12-16T03:40:44.852Z · LW · GW · 0 comments

Contents

No comments

 

Lemma 3: If  is a continuous function of type , where  is the space of nonempty compact subsets of the space , then given any compact set  will be compact in .

Fix some compact set , and continuous function . We will operate by taking an arbitrary open cover of  and finding a finite subcover.

Let  be an open cover of . The  are subsets of . The topology compatible with Hausdorff distance on  (space of compact subsets of ) is the Vietoris topology, where the basis opens are given by finite collections of open sets in . You take the set of all compact subsets of  which are subsets of the union of your finite collection of open sets, and intersect every open set in your finite collection

Accordingly, let  (the set of all finite subsets of , the index set for our open cover), and fix a collection of open sets in . The sets  are defined as:

Now, all the  with  are compact ( produces compact sets as output), and they are all subsets of , so  is a cover of , and due to its compactness we can identify a finite subcover, and prune away every open st which doesn't intersect  is a subset of the union of those finitely many open sets, and intersects all of them, so the point  lies in the open set  induced by that finite cover of open sets.

This argument works for arbitrary  with , so the collection  is an open cover of . Also, because  is continuous and  is compact,  is compact, so we can identify a finite subcover from .

Then, consider the collection of open sets  where  for some  which is part of the finite cover of . This is finitely many opens, we're unioning together finitely many (finitely many  selected) finite sets of open sets (each  is associated with finitely many  that it was built from).

Now we just have to show that this collection covers , and we'll have made our finite subcover and shown that said set is compact. Assume our finite collection of opens doesn't cover the set. Then there's some  which wasn't covered completely. However, the point corresponding to  in  lies in some , and from its definition, the corresponding  manage to cover , and we have a contradiction. We're done.

Proposition 19:  is an infradistribution, and preserves all properties indicated in the diagram at the start of this section if  and all the  have said property.

To show this, we'll verify that it's well-defined at all, normalization, monotonicity, concavity, Lipschitzness, compact almost-support, and preservation of the properties.

Our first order of business is verifying that

is even a continuous function to be able to show that  can accept it as input.

For continuity, let  limit to , and we'll try to show that  limits to . Let  be the Lipschitz constant upper bound of .

Pick an , we'll show that there's some  where

First, note that  is a compact set because  limits to . Thus, by the compact-shared compact almost-support condition on an infrakernel, there must be some compact set  where all the  agree that functions  agreeing on  have values only  apart from each other.

Now, because f is a continuous bounded function , it's uniformly continuous when restricted to 

as this is the product of two compact sets and is compact. Due to the uniform continuity of  restricted to that set, there is some number  where points only  apart in that set have their values only differing by . Further, there is some number  where, for all .

Additionally, the maximum difference between  and  is .

Now that we know our number  we can pick an arbitrary  above it, and go:

And now, because these two functions restricted to  are only  apart, we can apply Lemma 2 to conclude that (since  and  work for all the )

This argument works for any , so we have:

Letting  in particular,

And for each \eps we can construct a m_0 in this way, concluding that

Also, from our pointwise convergence condition on infradistributions,

Therefore,

and so, we now know that

is a continuous function . For boundedness, upper and lower bounds on  are  (and the negative version of it). Due to the shared Lipschitz constant on the , an upper and lower-bound on  is  (and the negative version.) Thus, we can safely feed said function into the infradistribution , so the semidirect product is well-defined. We must still show that it makes an infradistribution.

For normalization,

For monotonicity, if ,

For concavity,

In order, this was the definition of the semidirect product, all the  being concave so splitting them up produces a lower value (and then monotonicity for ), then  being concave.

This leaves Lipschitzness and CAS. For Lipschitzness, given some  and , and letting  be the Lipschitz constant of , we have:

Thus, that final thing shows that there's a finite Lipschitz constant for .

This leaves compact almost-support. Pick any . This induces a compact set  which is an -almost-support for , and then this compact set induces a compact set  which an -almost-support for all the  where . Now, we can apply Lemma 2 to go:

Pretty much, that first part is the " is an -almost-support for " piece, and the second piece is the "hey, these two functions may be a bit different on said compact set, we've gotta multiply that by the Lipschitz constant" piece. So, let's work on unpacking these two distances. For the first one, we can go:

Substituting this back in produces:

Time to go after the second distance piece. We have:

And, because  and  agree on , we have  and  agreeing on , which is an -almost-support for all the  where , so we have:

Substituting this back in produces:

And regrouping this and recapping means that we have:

So we have crafted a compact -support for , and we can make  arbitrarily small, so the semidirect product has compact almost-support, which is the last condition we needed.

Time for property verification.

Homogenity:

1-Lipschitz: We showed in the Lipschitz section that an upper bound on the Lipschitz constant of  is the product of the Lipschitz constants of the kernel and the original infradistribution, so  and 1-Lipschitzness is preserved.

Cohomogenity:

C-additivity:

Crispness: Both homogenity and C-additivity are preserved, so crispness is too.

Sharpness:

Our task now is to show that  is compact, which will take a fair amount of topology work. Our first piece that we'll need is that if  limits to , then  limits to  in Hausdorff-distance.

To show this, we'll split it into two parts. First, we'll assume that there is an  where, infinitely often, there is a point in  that is  away from  and disprove that. Second, we'll assume there is an  where, infinitely often, there is a point in  that is  away from , and disprove that.

For the first part, assume that there is an  where, infinitely often, there is a point in  that is  away from . Craft the continuous function

What this does is it's 1 on the set , and 0 on anything more than  away from it. One of our conditions on an infrakernel was that , so:

The latter term is 1 because  is 1 over . However, because we're assuming that infinitely often, there's a point in  that is  away from , the sequence on the left-hand side is infinitely often 0, so it doesn't converge and we have a contradiction.

For the second part, assume there is an  where, infinitely often, there is a point in  that is  away from . By compactness of , we can find finitely many points  in it s.t. every point in  is only  away from one of the  (cover  with -size open balls centered on points in it and take a finite subcover). Now, for each of these, we can craft a function

So, this is 0 at the point , and 1 at any distance  or more away from it.

One of our conditions on an infrakernel was that , and there are finitely many , so there's some time where all of them nearly converge, ie:

However, infinitely often there's a point  that is  away from  is  away from some , so that  can't be closer than  to . (if it was closer, then we could pick some point in  that's closer than  to , and then since it's only  away from , we'd have that the distance from  to  is below , an impossibility).

Because the distance from  to any point in  is above , then

This is because  and attains a value of 0 according to , while  stays away from  and all its points must have a value of 1. This situation happens infinitely often, which leads to a contradiction with

Because infinitely often, one of these  has very different values, so the sequence is 1 infinitely often and can't limit to 0.

So, we've ruled out that there is an  where, infinitely often, there is a point in  that is  away from . And we've ruled out that there is an  where, infinitely often, there is a point in  that is  away from . Fixing any , in the tail of the sequence,  and  are  distance or closer in Hausdorff distance because you can't find points in either set which are far away from the other set. So,  limits to  in Hausdorff-distance when  limits to , and we know that  is a continuous function .

This lets us show that the set

is closed, because if  limits to  and  and  limits to , we have that  because  limits to  in Hausdorff distance, so we've got closed graph.

Also, by invoking Lemma 3, we know that

is compact.

Time to wrap this all up. We know that  is closed in  from our Hausdorff limit argument. This set is also a subset of:

Which is a product of two sets known to be compact, and is compact. It's a closed subset of a compact set, so it's compact. Therefore, 

is a compact set, and from way back,

And we've shown that set is compact, so  where  and all the  are sharp can be written as minimizing over a compact set, so  is sharp. Thus, semidirect product preserves all the nice properties, and we're finally done with this proof.

Proposition 20: If all the  are C-additive, then .

This is because, since  doesn't depend on , it acts as a constant inside  and C-additivity lets us pull it out.

Proposition 21: If  are a sequence of infrakernels of type  , and  is an infradistribution over , then  can be rewritten as  where  is an infrakernel of type , recursively defined as  and 

So, for our inductive definition,

Our task is to show that these are all infrakernels, by induction, and that for any infradistribution ,

For the base case, we observe that  is an infrakernel because it equals , which is an infrakernel, and that 

Time for the induction step. We'll assume that  is an infrakernel, and show that  is. Further, we need to show that . This will show the result.

Our first requirement is showing that for all  is an infradistribution. 

By our induction assumption,  is an infradistribution as  is an infrakernel. Further,  is an infrakernel because  is and we're just restricting it to a subset of its domain, so it keeps being an infrakernel. And we know from earlier that the semidirect product of an infradistribution and an infrakernel is an infradistribution. So that's taken care of.

Now, we must show a common Lipschitz constant, pointwise function convergence, and compact-shared compact almost-support for  to certify that it's an infrakernel.

Starting with common Lipschitz constant, we can just note that, in our proof of Proposition 19, we saw that the Lipschitz constant of the semidirect product was upper-bounded by the product of the Lipschitz constants of the starting infradistributions and the kernel. Assuming that  is an infradistribution, we have that the Lipschitz constant of any  is upper-bounded by some  Lipschitz constant. Also, the Lipschitz constant of  is upper-bounded by some  Lipschitz constant. Thus,  is an upper-bound on the Lipschitz constant of any

infradistribution, which is exactly , witnessing that  has a uniform upper bound on its Lipschitz constants.

Time to move onto the second one, compact-shared compact almost-support.

For this one, we're trying to prove:

This is the sentence that says that  has compact-shared compact almost-support.  and  have type signature .

Now, this is going to be quite complicated, so pay close attention. Fix an arbitrary compact , and an arbitrary . Let  be the Lipschitz constant for the infrakernel , and  be the Lipschitz constant for the infrakernel .

Due to compact-shared compact-almost-support for  which exists by our induction assumption, your set  induces a compact -almost-support for the family of infradistributions  where . Call said almost-support .

Further, due to compact-shared compact-almost-support for  , the set

induces a compact -almost-support for the family of infradistributions  where 

Call said almost-support 

And now let your shared -almost-support for  where  be:

We must show that said set is indeed a shared -almost-support for  where . So, let  and  agree on said set. Then, we have:

This is just unpacking the definition of the iterated semidirect product, no issues here. Now, we use Lemma 2 and the fact that  is a -almost-support for  when , to get:

Ok, this is a mess. Let's try to unpack

first. What we can do is use that, regardless of what is picked in the supremum, we have:

So this means that

is a -almost-support for . Further, because  and  are identical on

and  was being selected from the former of those, then the functions  (and the same for ) agree on , the almost-support. So, the supremum is upper-bounded by

Substituting this back in, we get:

Now let's try to unpack 

We don't have much leverage on it, besides using the basic Lipschitz constant upper bound, so let's try that.

And substituting this back in, we get:

And so we've shown that the functions are only  times their distance apart, so the compact set we cooked up is indeed an -almost-support for  whenever , and because  and  was arbitrary, we have compact-shared compact-almost-support for .

Time to move onto the third one, pointwise convergence. If  limits to , we want  to limit to . As usual, we use  for the Lipschitz constant of  and  for the Lipschitz constant of .

To begin with, fix an arbitrary  and bounded continuous function , and note that  is a compact subset of . Because  is assumed to be an infrakernel by induction,  acts as a compact set for it. So, by compact-shared compact-almost-support for , we can find a compact set  which is a -almost-support for .

Also, it is important to note that 

Is a continuous function (as it must be for semidirect products with  to have the functions on the inside be continuous). Accordingly, this means that the function:

must be uniformly continuous when restricted to the set 
And so, by uniform continuity, given any , there is some  difference in inputs which gives rise to a  difference in output.

Now, here's what we'll be doing. We'll attempt to show the result that

Straight off the bat, we can apply Lemma 2 to decompose this difference into "starting Lipschitz constant times the difference of the inner functions on the compact set of interest" and "level of almost-support times the difference of the two functions", yielding:

Time to start breaking this down. First, to break down

we can realize that the maximum value of one of these would be , and the minimum possible value of one of these is , from Lipschitzness of , producing an upper bound of:

Substituting this back in, we have:

And now, we can use the fact that there is always some  difference in inputs which gives rise to a  difference in output of the function

when restricted to the set 
in order to find some  where all future  have  being within  of .

This tiny difference means that the values

and

will only differ by  for all  which lie in

Therefore, we have that for all  past 

And substituting this back in, we have:

And  was arbitrary. Therefore we have our desired result that, regardless of bounded continuous function ,

Therefore,

These two things limit increasingly close to each other. Further,

By pointwise convergence for  which is an infrakernel by our induction assumption. Putting these two parts together, we have:


so

so

And we're done, we showed pointwise convergence for  which is the last condition necessary to show it's an infrakernel, and the induction proof goes through to show that all the  are infrakernels.

Now all that's left is to show that

using induction, we have the base case set up. We can go:

And we're done. Because 

and we know that , this means that


Proposition 22:  is an infrakernel (C-additive, specifically) if all the  are C-additive infrakernels. It is unchanged by altering the  sequence of compact sets. In addition, if all the  are homogenous/cohomogenous/crisp/sharp, then  will be so as well.

So,  is defined as: Fixing an arbitrary sequence of compact sets ,

Is it an infrakernel?

This is going to suck unbelievably much, we're gonna need a ton of results. The game plan is:

Part 1: Show that the functions you're feeding into those infrakernels are guaranteed to be continuous, to make some progress towards showing that  is well-defined.

Part 2: Show that all the  are 1-Lipschitz, and also preserve all nice properties we'd want if all the  do (homogenity, cohomogenity, C-additity, crispness, sharpness).

Part 3: Show that if a function only depends on the first n coordinates of the input, then all the  start agreeing on the expectation value of the function.

Part 4: Give a general procedure for taking a compact subset of the space  and making a compact subset of the space  with nice properties related to compact almost-support, that preserves its nice properties when projected down to any finite stage.

Part 5: Use parts 2, 3, 4, and a complicated chain of reasoning to get a result which implies that it doesn't matter which  sequence you pick, the limit will exist and be same for all of them, so  actually exists and is well-defined.

Part 6: Using parts 2 and 5, clean up the normalization, monotonicity, concavity, and C-additivity properties of . Showing that all the  are C-additive trivially nets the bounded Lipschitz constant property to show that  is an infrakernel and  is an infradistribution.

Part 7: Use our trick from Part 4 and our freedom of picking our compact set sequence from Part 5 to show compact-shared compact almost-support for , netting us the second infrakernel property, and the compact almost-support property for all the individual components of kernel, verifying the last condition we need to conclude that  is an infradistribution.

Part 8: We recap one of the arguments for part 5, and it lets us get uniform convergence for a certain limit on any compact set, which is a critical lemma for Part 9.

Part 9: We use our result from Part 8 to invoke the Moore-Osgood theorem in order to show pointwise convergence for , wrapping up the last condition for it to be an infrakernel.

Part 10: Show that if all the  have some nice property, then the limit  inherits it too.

The proofs will proceed in a strange way to keep track of all the moving parts in places. We'll first present the thing we're trying to prove, and repeatedly go "we could prove it if we could prove this other thing", and keep chaining back until we get something that's easy to show.

Proof Part 1: Our desired result is whether the function 
is continuous. So, letting  limit to , our task is to show that:

Now, what we can do is consider the compact subset of  to be

And then  must be uniformly continuous on it, so given any , there is some  where points only  away lead to only an  differ in value. You can consider  to be big enough to guarantee that all future values of  are within  of , and then this gets that the function values can only differ by  between  and  if , which it is. This ensures that the worst-case function values are only  apart. This works for all , showing

And so, all the functions we're feeding into the  are continuous.

Proof Part 2: Desired result is "if all the  have a nice property, then all the  have it too".

This can be simply addressed by noting that, for the base case, because  and we're assuming all the  have (C-additivity/cohomogenity/homogenity/crispness/sharpness),  trivially fulfills it.

And for the induction step, if we assume that  is 1-Lipschitz, note that:

And, by our results on semidirect products preserving nice properties, if  has the nice property (by induction assumption) and  does, then we get that  preserves the same property, and it holds all the way up the .
And we can move on to Part 3.

Part 3: Showing that, if we go far enough out in the , the value assigned to functions which only depend on finitely many inputs stabilizes. The result that we'd like to show at this point is:

Admittedly, f is not of the proper type signature to be evaluated by , but we're abusing notation so that we can feed it in anyways and it just ignores all the coordinates it doesn't need. Accordingly, fix an arbitrary  and our proof target will now be:

Proving this would let you apply induction, because we have a base case where . Let  be arbitrary. Then, we can go:

And then, since the function doesn't depend on the choice of , it's a constant and C-additivity of  lets us pull it out, yielding

And we're done.

Part 4: Our desired result here is:

This is a bit complicated. It's saying that if you pick any compact subset of , you can make a compact subset of  where the projection of it to coordinates 1 through  acts as a compact -almost-support for all the  infradistributions when  lies in your compact subset of . Regardless of what  is.

Accordingly, fix some  and . Now, we can recursively build up compact subsets of all the  in the following way.

 is a -almost-support for all the  where . So, basically, we're recursively building up compact subsets of  by taking products of earlier compact subsets (with your base case being ), and then going "that's a compact subset of the input to , we must be able to find a compact subset of  that's a -almost-support for all the  where  lies in our compact subset of input, because of the compact-shared almost-support condition for all the " to go to the next compact set.

To establish some notation to make this a bit easier, let

(the i'th compact set in the sequence, defined with  to start building your sequence), and let

(the product of compact sets 1 through , which is compact)

And let

This is the product of all the compact sets, and is compact.

Note the dependence of these on the starting compact sets. Notice that the projection of  to coordinates 1 through  is exactly .

Now that this is established, our proof target is (using our new notation):

This structure naturally suggests an induction proof, so for the base case, let our number be 0. Our proof target then turns into:

Using that  and that  and  our proof target is now:

However, we constructed  to be a -almost-support for all the  where , so this statement is just true, and we're done with our base case.

Now, for the induction step, our proof target is:

implies

Accordingly, assume

And our task is to prove

Therefore let  be arbitrary, and remember that they have the indicated properties, and that  agree with each other on the indicated set . Our proof target is now:

Unpacking the definition of  and rewriting the thing on the end, this is equivalent to (we now take this as the proof target)

We can apply the Lemma 2 decomposition, to split this into "level of support of compact set x distance of functions + distance of functions on compact set x lipschitz constant of infradistribution". So, theoretically, if we had the following two results:

and

then applying Lemma 2 would get us

Which is exactly what we need. This works because  is an -almost-support for  by our induction assumption, our 2 assumptions,  be a 1-Lipschitz infrakernel, and Lemma 2. Accordingly, let's try to show our two proof targets we need to wrap up this result. We'll start with

Now, we know that  and  agree on  by assumption, which is a set that factorizes as , and we have a promise that , so  equals  on the set , which is a -almost-support for all the  where  (which is the case by assumption) and  (also the case), so we have our result.

Now for the other branch,

Due to 1-Lipschitzness of  regardless of  and , we could prove it if, regardless of ,

which is the case, so we have our result.

That's everything wrapped up, so our induction proof goes through, yielding our result of:

Now to begin our fifth part.

Part 5: Our aim here is to show that no matter what sequence of compact sets you have, they all limit to the same result, so our limit is going to be well defined. In order to do this, we'll have to show the result (letting  being your first sequence of nonempty compact sets to attempt to define the limit and  being your second sequence of nonempty compact sets, and abbreviating  as the product of the  from  to ) that,

In words, this is saying that for any two sequences of compact sets, there exists some threshold where if you pick any value of the defining sequence for  associated with using  as your compact sets, and the sequence associated with using  as your compact sets (as long as they're both past some shared threshold), they'll be close. If you have both sequences being identical, then this result is basically saying that the sequence used to define  is Cauchy (never varies too far from itself after a finite time), and thus the limit exists. And if you have the sequences being different, then this can be used to show that they limit to each other, so  is well-defined and you always get the same result no matter which particular sequence of compact sets you fix.

This is going to be rough. Fix our  (input value, closeness parameter, two sequences of compact sets, function), and now we'll find our  to make

true. Do it in the following way. Use  as your compact seed set to invoke the technique in part 4 to construct your sequence , and then consider the set:

A finite union of compact sets is compact, and the product of compact sets is compact. If we restrict f to this set, it's uniformly continuous. In particular, using the standard product metric (which metrizes the product topology), defined as:

We can conclude that two sequences which agree up till time  must be, at most, distance  apart. Since  restricted to our compact set of interest is uniformly continuous, there is some  difference inputs that only leads to an  difference in values. Now we can define our  as .

Now that we've picked our , let  and  be arbitrary. Our goal is to now prove:

We can break up the distance between these two quantities as:

The distances group into three "chunks". What we'll do is show that chunks 1 and 3 have value upper-bounded by , and chunk 2 has a value of 0, producing our net  upper-bound, and we'd be done. So, let's try to show the first one, that: 

This one is perfectly symmetric to the third distance chunk, so disposing of this will also deal with showing

The way we'll deal with this one is by using our good old Lemma 2, where we split up the difference of the two quantities into "how much of a support is this set times how different are the two functions" and "how close are the two functions on this set times the Lipschitz constant of the infradistributions". We'll be picking the set , which is an -almost-support for  by our discussions in Section 4. Because the infrakernels are always 1-Lipschitz because of C-additivity, the maximum/minimum expectation value the functions

and

can have is  (or ) respectively. This produces a  bound on the value of that piece produced via Lemma 2. All that remains is to prove that

(because of 1-Lipschitzness of the infrakernel) And we'll be done. We can reformulate this proof objective as:


Accordingly, let  be arbitrary in said set, so our objective is now:

We'd be able to prove this if we could show:

Accordingly, let  and  be selected from the appropriate sets, and our goal is now:

At this point, we should remember that if you have a promise that your input to  will be within the set 

then knowing the first n coordinates fully pins down the value of your function  to within , by how we picked our . And then we can notice something interesting. By how they were selected,

And also, 

So, the two inputs are both in the relevant compact set, and agree on the first  coordinates, so they agree to within  value, and our desired result is the case. We've showed

Which symmetrically establishes

By pretty much exactly the same line of argument. That leaves one last distance equality to establish. All we need now is to show that

Which is the same as the proof target:

However, this inner function only depends on the inputs from 1 to , so by our Part 3, both of these equal the value

And so, we're done.

So, our entire result goes through, as we've shown all our proof targets, and we have:

As a result. Let's clean this up a little bit. It can be cleaned up into the equivalent form:

By shifting the  to the front and using that  is finite so we can just let the old  be small enough.

And now this gets interesting. Let  and  be arbitrary, specialize to , and , and abbreviate  as . Then this turns into:

Ie, this is pretty much saying that, regardless of your series of compact sets, the sequence in n given by:

is Cauchy (and therefore must converge to a particular value, regardless of which choice of compact sets is made). So, when we defined  as

The limit does indeed exist. But, we can actually get something even stronger. All these limits must be the same. Given the thing we showed, 

We can let and  be arbitrary, and  to get:

Ie, no matter which sequence of compact sets is selected, the two convergent sequences get arbitrarily close to each other, so our definition of  doesn't just have the limit being well-defined, it has it being the same regardless of which sequence of compact sets  was selected.


With this, now we can let the compact sequence be whatever is most convenient for arguments, as it always produces the same limit no matter what. (continued in next post)

0 comments

Comments sorted by top scores.