A quick thought on Savage's theorem and measurability; also some news

[sniffnoy]

Sorry I haven't been posting here lately like I've intended! Anyway here's a quick note on Savage's theorem and measurability.

So! Savage's theorem, right? When Savage stated it he didn't talk about σ-algebras or anything but as a practical matter, uh, you kind of need that due to measurability issues, right? So, the set of events should be restricted to measurable sets of world-states, and the set of actions to measurable functions from world-states to outcomes.

Problem: What is a measurable function from world-states to outcomes? If the ordering on outcomes is induced from the ordering on actions, this doesn't make a lot of sense!

Fortunately, you can repair the problem by formulating things slightly differently; start with an ordering an outcomes, use that to define measurability, and then state that the decision on outcomes induced from the ordering on actions agrees with the original order. Slightly clunky, but it works and makes sense, without any serious philosophical problems. So, yay, that problem goes away.

Meanwhile in personal news: I'm going to Boston for MIT Mystery Hunt for my first time! Wooo! Been solving since 2009 but this is my first time not doing so remotely. I'm going to be on Plant again this year. Two other Plant members I know from OBNYC (Daniel and Emma) will also be there. (Daniel here is Daniel Speyer, brother of David Speyer...)

Also, I unfortunately have to retract this entry as the proof turned out to be wrong. But I'm hopeful that it can be fixed, if not in general than at least maybe for fairly short sequence lengths, like say less than ω^ω or so...

Also Nintendo is announcing the next Smash character tomorrow at 9 AM, oh boy do I wake up for that I think maybe I do @_@

Comments

Nash-Williams

[joshuazelinsky]

Can we give a quick explanation of what goes wrong in the attempted proof of Nash-Williams?

Re: Nash-Williams

[sniffnoy]

Sure. First I'd better explain my attempted proof though.

The idea was that, given a transfinite sequence taking values in a finite subset of a WPO X, we could write it as a finite concatenation of sequences whose equivalence classes take an understandable form.

So, let's say we're looking at transfinite sequences in X (with finite image) and length less than α we're just going to consider the case where α is a power of ω, say α=ω^γ. Let's let S be the set of all of these sequences.

The idea is that we can find a subset T⊆S such that every element of S can be written as a concatenation of finitely many elements of T; and moreover we want to pick T such that we can show that T (in the induced ordering) is a WQO (and get a bound on its type). Then T* would monotonically surject onto S, showing that S is a WQO, and getting us a bound on its type in terms of the type of T (the type of T* is a simple, known, function of the type of T, as determined by De Jong, Parikh, and Schmidt; this function is about double-exponential).

Specifically, I chose T to be the set of (nonempty) sequences s in S such that:
1. The length of s is a power of ω; (technically this condition is implied by the other two + nonemptiness but I'm including it for clarity)
2. Every element that occurs in s, occurs cofinally in s;
3. If an element occurs in s, the number of times it appears in s is a power of ω.

Note that this does include length 1 sequences.

So, is every element in S a finite concatenation of elements of T? Yes, it is! This is not too hard to show. The problem is that the set T is not as easy to understand as I thought.

Let's put it this way -- if we want to understand the order on T, the first question to ask is, what are the equivalence classes? Remember, we're in the world of quasi-orders now, with no antisymmetry, so to understand things we have to understand the equivalence classes.

In short, I thought that, for an element s of T, the equivalence class of s was purely a function (note: not injective) of how many times each element of X occurs in s. I believed -- and thought I had a proof of -- a stronger statement, describing the actual equivalence classes in more detail and the order on them, but let's just stick to the statement above.

So, this hypothesis turns out to be false.

Now, obviously, for s of length 1, well, these are just elements of X. So the statement is true, if trivial. Of course, just considering s of length 1 just gets you to ω which we already know how to handle.

For s of length ω, the statement still holds true. So, that's enough to prove things for α=ω², which is likely already publishable by itself, but obviously I wanted so much more!

Anyway. Where things go wrong is for s of length ω². Let's say X = {a, b} is an antichain. According to the hypothesis above, the sequences (ab)^ω² and (a^ωb^ω)^ω would be equivalent, since both consist of ω² occurrences of a and ω² occurrences of b.

But, they're not! The former is strictly greater!

So, can we fix this? Well, in order to fix the proof, I'd need to actually understand the order on T (I don't think finding a different T would work, although that is possibly also worth considering). Of course, for length ω, I already do understand it; my hypothesis is correct there! (Not just about the equivalence classes but about the order.) But for larger lengths, well, it's something I'll need to sit down and study when I have some time. I did already and I have some suspicions for ω², which might actually might work for less than ω^ω. That'd be nice, if I could get to ω^ω, but it's still tiny compared to what I thought I had (namely: all ordinals). But getting past ω^ω seems much more difficult...

It may be worth noting that historically, Nash-William's theorem was proven first for α=ω³ (by Rado) and then α=ω^ω (by Erdös and Rado) before it was proven for all ordinals. (OK, I suppose first it was proven for α=ω, but YKWIM.) I've never looked at those proofs; maybe I should just in case they resemble at all what I had in mind! In my case I've gotten to ω² and haven't quite gotten to ω³ yet... well, like I said, will have to try when I have time.