Proofs Section 1.1 (Initial results to LF-duality)

by Diffractor20 min read27th Aug 2020No comments

3

Infra-BayesianismLogic & Mathematics AI
Frontpage

Fair upfront warning: This is not a particularly readable proof section (though much better than Section 2 about belief functions). There's dense notation, logical leaps due to illusion of transparency since I've spent a month getting fluent with these concepts, and a relative lack of editing since it's long. If you really want to read this, I'd suggest PM-ing me to get a link to MIRIxDiscord, where I'd be able to guide you through it and answer questions.

 

Proposition 1: If  then  is a positive functional on .

Proof Sketch: We just check three conditions. Linearity, being nonnegative on , and continuity.

Linearity proof. Using  for constants,

So we have verified that  and we have linearity.

Positivity proof: An sa-measure , writeable as  has  uniquely writeable as a pair of finite measures  (all the positive regions) and a  (all the negative regions) by the Jordan Decomposition Theorem, and . So,

The first  by , so the expectation of  is positive and  is negative so taking the expectation of 1 is more negative. The second  is by the condition on how  relates to .

Continuity proof: Fix a sequence  converging to . Obviously the  part converges, so now we just need to show that  converges to . The metric we have on the space of finite signed measures is the KR-metric, which implies the thing we want. This only works for continuous , not general .

 

Theorem 1: Every positive functional on  can be written as , where , and 

Proof Sketch: The first part is showing that it's impossible to have a positive functional where the  term doesn't matter, without the positive functional being the one that maps everything to 0. The second part of the proof is recovering our  by applying the positive functional to Dirac-delta measures , to see what the function must be on point .

Part 1:  Let's say  isn't 0, ie there's some nonzero  pair where , and yet  (which, by linearity, means that  for all ). We'll show that this situation is impossible.

Then,  by our starting assumption, and Jordan decomposition of , along with linearity of positive functionals. Now,  because positive functionals are linear, and everything in that above equation is an sa-measure (flipping a negative measure makes a positive measure, which doesn't impose restrictions on the  term except that it be ).  And so, by nonnegativity of positive functionals on sa-measures, . Using this, we get

Another use of linearity was invoked for the first  in the second line, and then the second  made use of our assumption that  for all .

At this point, we have derived that . Both of these are positive measures. So, there exists some positive measure  where .

Now, observe that, for all 

Let b be sufficiently huge to make  into an sa-measure. Also, since , which is impossible because positive functionals are nonnegative on all sa-measures. Contradiction. Due to the contradiction, if there's a nonzero positive functional, it must assign , so let  be our  term.

Proof part 2: Let's try to extract our f. Let  This is just recovering the value of the hypothesized  on  by feeding our positive functional the measure  that assigns 1 value to  and nothing else, and scaling. Now, we just have to verify that this  is continuous and in .

For continuity, let  limit to . By the KR-metric we're using,  limits to . By continuity of  limits to . Therefore,  limits to  and we have continuity.

For a lower bound, , because  is a ratio of two nonnegative numbers, and the denominator isn't 0.

Now we just have to show that . For contradiction, assume there's an  where . Then , so , and in particular, .

But then, , so 

However,  is an sa-measure, because , and must have nonnegative value, so we get a contradiction. Therefore, .

To wrap up, we can go:

And , and , so we're done.

 

Lemma 1: Compactness Lemma: Fixing some nonnegative constants  and , the set of sa-measures where , is compact. Further, if a set lacks an upper bound on  or on , it's not compact.

Proof Sketch: We fix an arbitrary sequence of sa-measures, and then use the fact that closed intervals are compact-complete and the space  is compact-complete to isolate a suitable convergent subsequence. Since all sequences have a limit point, the set is compact. Then, we go in the other direction, and get a sequence with no limit points assuming either a lack of upper bounds on , or a lack of upper bounds on .

Proof: Fix some arbitrary sequence  wandering about within this space, which breaks down into , and then, since all measures are just a probability distribution scaled by the constant , it further breaks down into . Since  must be bounded in .

Now, what we can do is extract a subseqence where  ,, and  all converge, by Tychonoff's Theorem (finite product, no axiom of choice required) Our three number sequences are all confined to a bounded interval, and our two probability sequences are wandering around within  which is a compact complete metric space if  is. The limit of this subsequence is a limit point of the original sequence, since all its components are arbitrarily close to the components that make up  for large enough n in our subsequence.

The limiting value of  and  both obey their respective bounds, and the cone of sa-measures is closed, so the limit point is an sa-measure and respects the bounds too. Therefore the set is compact, because all sequences of points in it have a limit point.

In the other direction, assume a set  has unbounded  values. Then we can fix a sequence  where  increases without bound, so the a-measures can't converge. The same applies to all subsequences, so there's no limit point, so  isn't compact.

Now, assume a set  has bounded  values, call the least upper bound , but the value of  is unbounded. Fix a sequence  where  is unbounded above. Assume a convergent subsequence exists. Since  must be bounded in . Then because , and the latter quantity is finite,  must be unbounded above. However, in order for the  to limit to some , which results in a contradiction. Therefore, said convergent subsequence doesn't exist, and  is not compact.

Put together, we have a necessary-and-sufficient condition for a closed subset of  to be compact. There must be an upper bound on  and , respectively.

 

Lemma 2: The upper completion of a closed set of sa-measures is closed.

Proof sketch: We'll take a convergent sequence  in the upper completion of  that limits to , and show that, in order for it to converge, the same sorts of bounds as the Compactness Lemma uses must apply. Then, breaking down  into , where , and  is an sa-measure, we'll transfer these Compactness-Lemma-enabling bounds to the sequences  and , to get that they're both wandering around in a compact set. Then, we just take a convergent subsequence of both, add the two limit points together, and get our limit point , witnessing that it's in the upper completion of .

Proof: Let  limit to some . A convergent sequence (plus its one limit point) is a compact set of points, so, by the Compactness Lemma, there must be a  and  that are upper bounds on the  and  values, respectively.

Now, for all n, break down  as , where , and  is an sa-measure.

Because , we can bound the  and  quantities by . This transfers into a  lower bound on  and , respectively.

Now, we can go:

Using worst-case values for  and , we get:

So, we have upper bounds on  and  of , respectively.

Due to the sequences  and  respecting bounds on  and  ( and  respectively), and wandering around within the closed sets  and  respectively, we can use the Compactness Lemma and Tychonoff's theorem (finite product, no axiom of choice needed) to go "hey, there's a subsequence where both  and  converge, call the limit points  and . Since  and  are closed, , and ."

Now, does ? Well, for any , there's some really large n where , and . Then, we can go:

So, regardless of , so . So, we've written  as a sum of an sa-measure in  and an sa-measure, certifying that , so  is closed.

 

Proposition 2: For closed convex nonempty ,

Proof sketch: Show both subset inclusion directions. One is very easy, then we assume the second direction is false, and invoke the Hahn-Banach theorem to separate a point in the latter set from the former set. Then we show that the separating functional is a positive functional, so we have a positive functional where the additional point underperforms everything in , which is impossible by the definition of the latter set.

Easy direction: We will show that 

This is because a , can be written as . Let  be our  of interest. Then, it is indeed true that for all 

Hard direction: Assume by contradiction that

Then there's some  where  and  is the upper completion of a closed set, so by the Compactness Lemma, it's closed, and since it's the Minkowski sum of convex sets, it's convex.

Now, we can use the variant of the Hahn-Banach theorem from the Wikipedia article on "Hahn-Banach theorem", in the "separation of a closed and compact set" section. Our single point  is compact, convex, nonempty, and disjoint from the closed convex set . Banach spaces are locally convex, so we can invoke Hahn-Banach separation.

Therefore, there's some continuous linear functional  s.t. 

We will show that this linear functional is actually a positive functional!

Assume there's some sa-measure  where . Then we can pick a random , and consider , where  is extremely large.  lies in , but it would also produce an extremely negative value for \phi which undershoots  which is impossible. So  is a positive functional.

However, , so . But also,  fulfills the condition , because of the set it came from. So, there must exist some  where . But, we have a contradiction, because .

So, there cannot be any point in  that isn't in . This establishes equality.

 

Lemma 3: For any closed set  and point , the set  is nonempty and compact.

Proof: It's easy to verify nonemptiness, because  is in the set. Also, it's closed because it's the intersection of two closed sets.  was assumed closed, and the other part is the Minkowski sum of  and , which is closed if  is, because it's just a shift of  (via a single point).  is closed because it's -1 times a closed set.

We will establish a bound on the  and  values of anything in the set, which lets us invoke the Compactness Lemma to show compactness, because it's a closed subset of a compact set.

Note that if , then , so . Rewrite this as 

Because , we can bound  and  by . This transfers into a  lower bound on  and . Now, we can go:

Using worst-case values for  and , we get:

So, we have an upper bound of  on , and an upper bound of  on . Further,  was arbitrary in , so we have our bounds. This lets us invoke the Compactness Lemma, and conclude that said closed set is compact.

 

Lemma 4: If  is a partial order on  where  iff there's some sa-measure  where , then

Proof: 

Also, 

Also, 

Putting all this together, we get

And we're halfway there. Now for the second half.

Also, 

Putting this together, we get

And the result has been proved.

 

Theorem 2: Given a nonempty closed set , the set of minimal points  is nonempty and all points in  are above a minimal point.

Proof sketch: First, we establish an partial order that's closely tied to the ordering on , but flipped around, so minimal points in  are maximal elements. We show that it is indeed a partial order, letting us leverage Lemma 4 to translate between the partial order and the set . Then, we show that every chain in the partial order has an upper bound via Lemma 3 and compactness arguments, letting us invoke Zorn's lemma to show that that everything in the partial order is below a maximal element. Then, we just do one last translation to show that minimal points in  perfectly correspond to maximal elements in our partial order.

Proof: first, impose a partial order on , where  iff there's some sa-measure  where . Notice that this flips the order. If an sa-measure is "below" another sa-measure in the sa-measure addition sense, it's above that sa-measure in this ordering. So a minimal point in  would be maximal in the partial order. We will show that it's indeed a partial order.

Reflexivity is immediate. , so .

For transitivity, assume . Then there's some  and  s.t. , and . Putting these together, we get , and adding sa-measures gets you an sa-measure, so .

For antisymmetry, assume  and . Then , and . By substitution, , so . For all positive functionals, , and since positive functionals are always nonnegative on sa-measures, the only way this can happen is if  and  are 0, showing that .

Anyways, since we've shown that it's a partial order, all we now have to do is show that every chain has an upper bound in order to invoke Zorn's lemma to show that every point in  lies below some maximal element.

Fix some ordinal-indexed chain , and associate each of them with the set , which is compact by Lemma 3 and always contains .

The collection of  also has the finite intersection property, because, fixing finitely many of them, we can consider a maximal , and  is in every associated set by:

Case 1: Some other  equals , so  and .

Case 2: , and by Lemma 4, .

Anyways, since all the  are compact, and have the finite intersection property, we can intersect them all and get a nonempty set containing some point  lies in , because all the sets we intersected were subsets of . Also, because  for all  in our chain, then if , Lemma 4 lets us get , and if , then . Thus,  is an upper bound for our chain.

By Zorn's Lemma, because every chain has an upper bound, there are maximal elements in , and every point in  has a maximal element above it.

To finish up, use Lemma 4 to get: 

 

Proposition 3: Given a , and a  that is nonempty closed, 

Direction 1: since  is a subset of , we get one direction easily, that

Direction 2: Take a . By Theorem 2, there is a  s.t. . Applying our positive functional  (by Proposition 1), we get that . Because every point in  has a point in  which scores as low or lower according to the positive functional,

And this gives us our desired equality.

 

Proposition 4: Given a nonempty closed convex  and 

Proof: First, we'll show . We'll use the characterization in terms of the partial order  we used for the Zorn's Lemma proof of Theorem 2. If a point  is in , then it can be written as , so . Since all points added in  lie below a preexisting point in  (according to the partial order from Theorem 2) the set of maximals (ie, set of minimal points) is completely unchanged when we add all the new points to the partial order via upper completion, so .

For the second part, one direction is immediate. , so . For the reverse direction, take a point . It can be decomposed as , and then by Theorem 2,  can be decomposed as , so , so it lies in , and we're done.

 

Theorem 3: If the nonempty closed convex sets  and  have , then there is some  where 

Proof sketch: We show that upper completion is idempotent, and then use that to show that the upper completions of A and B are different. Then, we can use Hahn-Banach to separate a point of  from  (or vice-versa), and show that the separating functional is a positive functional. Finally, we use Theorem 1 to translate from a separating positive functional to different expectation values of some 

Proof: Phase 1 is showing that upper completion is idempotent. . One direction of this is easy, . In the other direction, let . Then we can decompose  into , where , and decompose that into  where , so  and .

Now for phase 2, we'll show that the minimal points of one set aren't in the upper completion of the other set. Assume, for contradiction, that this is false, so  and . Then, by idempotence, Proposition 4, and our subset assumption,

Swapping the A and B, the same argument holds, so , so .

Now, using this and Proposition 4, .

But wait, we have a contradiction, we said that the minimal points of  and  weren't the same! Therefore, either , or vice-versa. Without loss of generality, assume that .

Now for phase 3, Hahn-Banach separation to get a positive functional with different inf values. Take a point  in  that lies outside . Now, use the Hahn-Banach separation of  and  used in the proof of Proposition 2, to get a linear functional  (which can be demonstrated to be a positive functional by the same argument as the proof of Proposition 2) where: . Thus, , so 

Said positive functional can't be 0, otherwise both sides would be 0. Thus, by Theorem 1,  where , and . Swapping this out, we get:

and then this is  So, we have crafted our  which distinguishes the two sets and we're done.

 

Corollary 1: If two nonempty closed convex upper-complete sets  and  are different, then there is some  where 

Proof: Either , in which case we can apply Theorem 3 to separate them, or their sets of minimal points are the same. In that case, by Proposition 4 and upper completion,  and we have a contradiction because the two set are different.

 

Theorem 4: If  is an infradistribution/bounded infradistribution, then  is concave in , monotone, uniformly continuous/Lipschitz, , and if 

Proof sketch:  is trivial, as is uniform continuity from the weak bounded-minimal condition. For concavity and monotonicity, it's just some inequality shuffling, and for  if ,, we use upper completion to have its worst-case value be arbitrarily negative. Lipschitzness is much more difficult, and comprises the bulk of the proof. We get a duality between minimal points and hyperplanes in , show that all the hyperplanes we got from minimal points have the same Lipschitz constant upper bound, and then show that the chunk of space below the graph of  itself is the same as the chunk of space below all the hyperplanes we got from minimal points. Thus,  has the same (or lesser) Lipschitz constant as all the hyperplanes chopping out stuff above the graph of .

Proof: For normalization,  and  by normalization for . Getting the uniform continuity condition from the weak-bounded-minimal condition on an infradistribution  is also trivial, because the condition just says  is uniformly continuous, and that's just  itself.

Let's show that  is concave over , first. We're shooting for . To show this,

And concavity has been proved.

Now for monotonicity. By Proposition 3 and Proposition 1,

Now, let's say . Then:

And we're done. The critical inequality in the middle came from all minimal points in an infradistribution having no negative component by positive-minimals, so swapping out a function for a greater function produces an increase in value.

Time for . Let's say there exists an  s.t. . We can take an arbitrary sa-measure , and consider , where  is the point measure that's 1 on , and  is extremely huge. The latter part is an sa-measure. But then,