# Measure from outer measure

1. Jan 15, 2005

### phoenixthoth

Consider the heirarchy of sets
finite sets
N
P(N)
P(P(N))
...

And let V denote the class of all sets equipollent to a set in that list.

I want to turn V into a psuedo-probability space and I need help. I say pseudo because the underlying space isn't a set.

Let A be in V. Define o(A) to be 0 if A is finite and otherwise, o(A)=n where n is the number of times the power set was applied to N to get to a set on the above list which A is equipollent to.

Example, R is in V. R~P(N), so here n=1. Then o(R)=1. N is also in V and there, n=0; so o(N)=0.

o is an outer measure because:
1. o(Ø)=0 and
2. o(AuB)<=o(A)+o(B). To see this, first consider the case where AuB is finite. Then 0 <= anything, so we're done. Now consider the case when N<=AuB where that means there is a 1-1 map from N to AuB. Suppose A~P(...P(N)) where there are n_A power set operations and similarly there is a n_B for B. Then that index for AuB is max(n_A, n_B). Let's denote this by q. o(AuB)=q. o(A)=n_A and o(B)=n_B. It's pretty clear now that o(AuB)<=o(A)+o(B) because q equals either n_A or n_B.

I think the proof would still work for a countable collection (ie sigma-subadditivity), albiet some things would have to be changed.

The question is how can I construct from this an m that takes elements in V to [0,oo] such that sub-additivity is replaced by additivity. That is, for a pair of disjoint sets in V, m(AuB)=m(A)+m(B).

m will be some nontrivial function of o.

2. Jan 15, 2005

### Hurkyl

Staff Emeritus
It sounds like you want a function m such that:

|A| = |B| --> mA = mB
|A*B| = 0 --> m(A+B) = mA + mB

but that can't happen unless mX = 0 for all X. For any two disjoint infinite sets A and B of the same cardinality, you'd have:

|A+B| = |A| = |B|
mA = m(A+B) = mA + mB
mB = 0

3. Jan 15, 2005

### phoenixthoth

Is there a way to turn a class of sets into a probability space that isn't trivial?

4. Jan 16, 2005

### Hurkyl

Staff Emeritus
Well, I've proven that there is no mapping m to an additive group that has the properties:

|A| = |B| --> mA = mB
|A*B| = 0 --> m(A+B) = mA + mB

You could, of course, map into things that aren't additive groups... for instance, you could take m as the function that maps a set to its cardinality. That does satisfy these two axioms.

You could take another approach -- instead of trying to work with all sets, you could try just sets within the superstructure. We can equip N with a measure (but it isn't translation invariant) which assigns a value to each element of P(N). But then you have to work out how to extend this measure to the higher power sets. I don't think it would be possible to always have |A| < |B| --> mA < mB, though. One such example would be that mX is simply the measure of the set of all natural numbers it recursively contains.

It might be fruitful to think of sets as trees (pun intended!). One can model sets as rigid trees, which have the property that no node can have two equal children. You get multisets simply by removing this restriction.

For example, the set {{}, {{}}} corresponds to the tree
Code (Text):

*
/  \
0   *
|
0

Where I've used 0 to denote leaves, aka the empty set. One could generalize this to allow the leaves to be urelements.

Maybe looking at sets like this would help. Remember that each node can have any number of children -- even uncountably many.

5. Jan 16, 2005

### phoenixthoth

Let's fix a set X whose cardinality is no smaller than the cardinality of P(R). I would prefer to develop a probability measure on X; but any measure would be fine.

I think I want an m memorable enough to not forget everything but the cardinality of a set. So I don't want |A|=|B| --> mA=mB. Cuz then, mA=m(AuB)=mA+mB-->mB=0.

Yes, I suspected that when I looked at the measurable sets from my outer measure; the only measurable sets were the null sets.

I just had an idea. For my purposes, I *think* I can assume that X is a metric space. Can I use the hausdorff measure? Can you give me some intuition on the hausdorff measure and if a probability measure can be derived from it somehow?

Thanks again!!!

6. Jan 16, 2005

### phoenixthoth

I know mA/(1+mA) doesn't turn m into a probability measure, but something like that. Is there a standard trick for turning a measure into a probability measure?

I had another idea. I think Hausdorff measure will help with some generality. I think that if we look at the hierarchy
N
R
P(R)
P(P(R))
...

Let's label these sets as X_0, X_1, X_2, ..., where the subscript indicates how many times the power set operation has been applied. I want to employ the Hausdorff measure on all of these spaces. I have some semblance of an idea how to do that.

You have a metric on R, say the |b-a| metric. Then you can define a function r so that if A and B are elements of P(R), r(A,B)=inf {|b-a|: a in A, b in B}. This is not a metric though. Damn. Well maybe moding out the sets such that r=0. Yes... Yess.... Say ~ is an equivalence relation on P(R) such that A~B iff r(A,B)=0 and let X_1=P(R)/~. I think this is a metric space. The metric would have to be proved to be well defined but I'd say that r([A],) should be inf{r(A,B) : A in [A], B in }.

Then do a similar thing to X_1.

Let G and H be subsets of X_1 (okay so G and H don't resemble elements of P(P(R))). Then define r'(G,H)=inf{r(g,h):g in G and h in H}.

Arg. I thought P(R) could be a metric space! Damn

7. Jan 16, 2005

### Hurkyl

Staff Emeritus
Unfortunately, all subsets of R are equivalent:

Given any sets A and B, if A~B isn't already true, then let C = R \ (A + B). Then, A ~ C and C ~ B...

I wonder if looking for topologies on P(R) (or, maybe just on the set of open sets of R) would be useful...

In that vein, to step back to topos theory... One of the subjects I've been meaning to look at, but haven't, is that of Grothendieck Topoi. These are supposed to be topology related, but I wonder if and how the connection between the relation to topology and the relation to set theory can be exploited. I'm not confident that this will be fruitful, though.

8. Jan 16, 2005

### phoenixthoth

Ok, then let's take P(R) to be a pseudo metric space. I'm not sure if it's pseudo or quasi that has the relaxed assumption of d(x,y)=0 does not imply x=y. So let's not mod out by anything and say D(A,B)=inf{d(a,b):a in A and b in B}. I'm wondering if that's even a pseudo metric...

Is there any nice metric on P(X) given X? (X=a metric space, or R to be specific)

What's the difference between a pseudo-metric space and a metric space; I mean, what does not hold true in pseudo metric spaces (besides the defining relaxation)?

Last edited: Jan 16, 2005
9. Jan 17, 2005

### Hurkyl

Staff Emeritus
Doesn't satisfy the triangle inequality:

Let A = [0, 1], B = [2, 3] and C = [4, 5]. Then,

d(A, B) + d(B, C) = 2
d(A, C) = 3

You could break the definition of metric in a different way -- change the target set. For instance, you could use P(R) itself as the target set, and define:

d(X, Y) = {d(x, y) | x in X, y in Y}

And I think this satisfies an appropriate modification of the triangle inequality. Maybe it's:

sup d(A, B) + sup d(B, C) >= sup d(A, C)

though that last sup might have to be an inf.

e.g.

sup d([0, 1], [2, 3]) = 3
sup d([2, 3], [4, 5]) = 3
sup d([0, 1], [4, 5]) = 5 <= 3 + 3

However, you have the problem that d(X, X) is not a constant in X.

I wonder if there isn't some clever logic that would make this particularly nice.

10. Jan 17, 2005

### phoenixthoth

Thanks, Hurkyl. I will consider adjusting the target of the function d to other than the interval [0,oo]; maybe to a boolean ring P(R).

To make the question as simple as possible:
We want to metrize the space P(X) given that (X,d) is a metric. We want to find a metric d' such that (P(X),d') is a metric space such that:
d'({x},{y})=d(x,y) and
d' is not trivial.

11. Jan 17, 2005

### phoenixthoth

Given (X,d) we want to metrize P(X) with a metric d' such that d'({x},{y})=d(x,y) for all x,y in X.

As you said, basically, we let d'(A,B)=sup{d(a,b):a &isin; A, b &isin; B} IF A!=B and IF A=B we set d'(A,B)=0.

Note that if d'(A,B)=0, then d(a,b)=0 for all a &isin; A and b &isin; B; so a=b for all a &isin; A and b &isin; B. Hence A=B. So we have d'(A,B)=0 iff A=B.

Clearly, d'(A,B)=d'(B,A).

d'({x},{y})=d(x,y).

Last but not least, the triangle inequality. Let A, B, and C be subsets of X (ie points in P(X)) and consider d'(A,B), d'(A,C), and d'(C,B).

*Waves hands:

Let a, b, c be arbitrary elements of A, B, and C. As (X,d) is a metric space, d(a,b) <= d(a,c) + d(c,b).

This last sum is less than or equal to sup{d(a,c)}+d(c,b) and that is at most sup{d(a,c)}+sup{d(c,b)}=d'(A,C)+d'(C,B).

Now since d(a,b) <= d'(A,C)+d'(C,B) for all a, b in A, B, d'(A,C)+d'(C,B) is an upper bound for the set {d(a,b)}; hence the least upper bound is at most as big:
sup{d(a,b)} <= d'(A,C)+d'(C,B); so
d'(A,B) <= d'(A,C)+d'(C,B).

12. Jan 17, 2005

### Hurkyl

Staff Emeritus
That seems pretty interesting. It would appear to recurse to higher power sets as well. The only problem is the empty set.

13. Jan 17, 2005

### phoenixthoth

So our d' is a metric?!? Cool.

Let's see... What is the deal with the empty set. Ø is a point in P(X). d'(Ø,Ø)=0 by definition. Remember that d'(A,B):=0 whenever A=B. Let's see what happens when B!=Ø...

d'(Ø,B)=sup{d(a,b): a ∈ Ø and b ∈ B}.

Well then we're supping an empty set, right? IE, {d(a,b): a ∈ Ø and b ∈ B}=Ø. And the least upper bound of Ø is -oo. Rats. That's the problem.

Could we *define* d'(Ø,B) to be diam(B)=sup{d(b,b') : b,b' ∈ B}?

Or could we define d'(A,B), when A!=B, to be
max(0,sup{d(a,b): a ∈ A and b ∈ B}).

Or could we just give up and say that P(X)\{Ø} is metrizable?

Which option do you prefer?

EDIT: The next step is to try and find the Hausdorff measure on the hierchy of spaces (R, ||), (P(R), ||'), etc.... And then hopefully turn the measure into a probability measure somehow so that "mutual information" can be defined on these sets, including "Self-information."

Last edited: Jan 17, 2005
14. Jan 18, 2005

### Hurkyl

Staff Emeritus
It might be -- I haven't worked through a proof, but it looks good.

One thing to note, though, is that the set of all sets with two or more elements forms a discrete space. Maybe that's fine for you, but I don't like it.

Maybe you could define e'(A, B) = d'(A, B) - min{diam A, diam B}. If this satisfies the triangle inequality, I like this one much better, because we have that:

e'([0, 1], [0, 1 + h]) = h, so it converges to 0 as h goes to 0.

15. Jan 18, 2005

### phoenixthoth

How would the case when min{diamA, diamB}=oo be handled?

16. Jan 18, 2005

### Hurkyl

Staff Emeritus
Very carefully...

Actually, one common way of doing that sort of thing is to define anything infinite as a sup. I.E. for A or B infinite, define:

e'(A, B) = lim sup e'(A intersect [-x, x], B intersect [-x, x])

(I think you'll get the same value if you let the two endpoints vary independently)

17. Jan 21, 2005

### phoenixthoth

How about d(A,B)=diam(A XOR B), if A != B, and d(A,B)=0 if A=B?

If this is a metric,
d([0,1],[0,1+h])=h.

Is there a neat way to prove or disprove that this is a metric?

Symmetric difference sucks.

18. Jan 22, 2005

### phoenixthoth

Ok so this isn't a metric. For example, C=[0,1]+[3,4], A=[0,1], B=[3,4]. d(A,B)=4, d(A,C)=1, d(C,B)=1. 4 !< 1+1.

So now I'm turning back to d(A,B) = sup (A OR B) but this doesn't have the property that d([0,1],[0,1+h])=h. In fact, d([0,1],[0,1+h])=1+h.