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
Putting all this together, we get
And we're halfway there. Now for the second half.
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,. Since , and is extremely huge, this is extremely negative. So, since there's sa-measures that make the function as negative as we wish in by upper-completeness,