User mike battaglia - MathOverflow

Average weighted value of a linear functional over increasing bounded subsets of Z^n

2012-11-22T15:44:48Z

Say you're working within the finite-dimensional free Z-module $\mathbb{Z}^n$, and you want to impose a "norm" on this module. By a "norm" I mean a function $\|·\|: \mathbb{Z}^n \to \mathbb{R}$ which obeys all of the axioms of a norm, but where the domain is the set of elements in the module rather than the set of vectors in a vector space. (I'm not going to keep putting "norm" in scare quotes after this because it's clear what I mean.)

I'm particularly interested in the case where our norm is an $\ell_p$ norm, but also desire to know a general solution to this problem for any arbitrary norm.

Now let $e$ be any element in $\mathbb{Z}^n$, and $f$ be any linear functional in the dual module $\mathbb{Z}^{n*} = Hom(\mathbb{Z}^n, \mathbb{Z})$. Then if we want to find

$\displaystyle \Theta(f) = \text{max} \left ( \left \lbrace \frac{\left|f(e)\right|}{\|e\|} : \|e\| \neq 0 \right \rbrace \right )$

then it's well-known that $\Theta$ itself has the structure of a norm, and is the dual norm on $\mathbb{Z}^{n*}$. If our norm on $\mathbb{Z}^n$ was an $\ell_p$ norm, this is $\ell_q$ norm dual to it.

Though it may seem odd, we can introduce a limit into the above expression, which leads to the following equivalent expression:

$\displaystyle \Theta(f) = \lim_{r\to\infty} \text{max} \left ( \left \lbrace \frac{\left|f(e)\right|}{\|e\|} : 0 \lt \|e\| \leq r \right \rbrace \right )$

However, what if rather than the supremum, we want to find the limit of the power mean of these increasingly large (but still finite) sets? That is, say for some real m, we want to find

$\displaystyle \mu^m(f) = \lim_{r\to\infty} \mu^m \left ( \left \lbrace \frac{\left|f(e)\right|}{\|e\|} : 0 \lt \|e\| \leq r \right \rbrace \right )$

where $\mu^m(S)$ for some finite set $S$ of non-negative reals is the power mean $\displaystyle \left ( \frac{1}{|S|} · \sum_{s \in S} s^m\right )^\frac{1}{m}$?

Given that, my questions are:

Is there some simple expression for $\mu^m(f)$ in general?
Will $\mu^m$ in general also have the structure of a norm?
If not, are there certain special choices of norm on $\mathbb{Z}^n$, and choice of m for $\mu^m$, for which $\mu^m$ does have the structure of a norm?
If the norm is an $\ell_p$ norm, are there certain special choices of p for which it holds?

Lastly, consider an embedding of $\mathbb{Z}^{n}$ in the obvious way into the vector space $\mathbb{R}^{n}$. This allows us to take $\mu$ and define a new, related function $\hat \mu^m(f) = \left(\frac{1}{\lambda(B_p)}\int_{B_p}\left(\frac{|f(v)|}{\|v\|}\right)^m dv\right)^\frac{1}{m}$, where $v \in \mathbb{R}^n$, $B_p = \left \lbrace v \in \mathbb{R}^n : 0 \lt \|v \| \leq 1 \right \rbrace$, and $\lambda$ is the Lebesgue measure on $\mathbb{R}^n$.

For any $f \in \mathbb{Z}^{n*}$ (and hence also $\in \mathbb{R}^{n*}$ via the embedding), does $\mu^m(f) = \hat \mu^m(f)$?
If not, what relationship might exist between $\mu^m(f)$ in the module and $\hat \mu^m(f)$ in the vector space?

Surreal numbers and large cardinals

2013-03-23T07:43:31Z

This is a question in two parts about the interaction of surreal numbers and large cardinals, in both cases just a request for references on the subject.

Part 1 is about foundations. Much of the research that I've seen on the surreal numbers typically treats the foundational issues by either working in NBG set theory (Ehrlich's work) or formulating everything in ZFC and tiptoeing around a formal treatment of proper classes (Conway's work). Also, some authors, again such as Conway, prefer to de-emphasize (though not completely ignore) the foundational issues that arise and assume that the reader will work in a set theory "that can handle it."

I have yet to see any work that focuses on using Grothendieck universes/strongly inaccessible cardinals as part of the growing arsenal of tools used to handle surreal numbers. I'm especially interested in this approach for its potential benefits in studying topology and analysis over the surreals, as well as making it easier to talk about this stuff in the sort of ordinary set-theoretic terms that mathematicians already know about. So,

Question 1: Does anyone have any good references that deal with using ZFC + the Axiom of Universes (ZFC+AU) in working with surreal numbers?

I'm particularly curious to know what foundational issues may arise in ZFC+AU that don't arise in other formal systems like NBG. I'm also very curious to know how well theorems from one foundation can be translated to theother, such as translating Ehrlich's results from NBG to ZFC+AU, and vice versa. General references on the interplay between NBG and ZFC+AU are also welcome; working with surreals requires me to learn a bit more logic!

Part 2 is about the fact that large cardinals can be fun to think about, in a kind of mystical set-theoretic way, and they carry over to the surreals by giving you new and exotic surreal numbers. I'm very interested to see if anyone's studied these "large surreals," some of which I suspect will have very interesting properties. I'm pretty sure that however interesting you think your favorite large cardinal is, the set of surreals generated by it on that birthday has to be at least twice as interesting, and there's a whole zoo of large cardinals to look at. Measurable surreals sound particularly interesting to me. So,

Question 2: Does anyone have any good references that deal with the interaction of various large cardinal axioms on the field of surreal numbers, as well as the interesting properties some of these "large surreals" might have?

Many thanks, and I'd much appreciate any references to useful literature on this topic! I've read Conway's ONAG, Knuth's book, and many of Ehrlich's papers, and I'd like some guidance on what references to turn to next, particularly with respect to the topics listed here.

Semiring naturally associated to any monoid?

2013-02-21T13:00:04Z

For any monoid $M$, we can naturally construct a semiring $S$ as follows:

Let the additive monoid of $S$ be the free commutative monoid on $M$
Let the multiplicative monoid of $S$ be $M$

Then, if you make multiplication distribute over addition, you get a semiring.

This has an extremely simple interpretation: the underlying additive monoid can be interpreted as the set of finite multisets over the elements of $M$, with addition being just union of multisets. Then, semiring multiplication between multisets $A$ and $B$ is simply the multiset you get if you apply the original binary operation of $M$ pairwise to all elements in $A \times B$.

This construction is rather natural. Does it have a name, or is it well-known? I've found it interesting because it's arisen organically in music theory, where the semifield associated with a certain free abelian group representing musical intervals has the beautifully clear interpretation of being a semifield of musical chords.

There are a few nice variations on this idea:

You can instead force the free commutative monoid to be idempotent, so that it now has a natural interpretation as the set of finite subsets of $M$, rather than the set of finite multisets over it.
Given any semiring $S'$, you can use this construction on each of its monoids, giving you an algebraic structure with three operators that are totally ordered with respect to distributivity.

Do any of these things have names, and/or are they well-known?

Skeleton category of the category of skeleton categories?

2013-02-08T23:52:23Z

A category is a skeleton if, roughly speaking, no two distinct objects within the category are isomorphic. To every category is associated a skeleton, and two categories are categorically "equivalent" if and only if their skeletons are isomorphic. A fuller definition can be found here.

Consider the subcategory of $\bf{Cat}$ which takes as objects those categories which are skeletons, and morphisms the functors between them; I will call this $\bf{{Cat}_{Skel}}$. Note that this is not the skeleton of $\bf{Cat}$ itself, but a subcategory of $\bf{Cat}$ in which the objects are skeletal categories.

Within this subcategory of skeletal categories, there are a number of objects which are, themselves, isomorphic. So we can take the skeleton of this category, hence obtaining a new category, which I will call $\bf{Skel({Cat}_{Skel})}$. (I don't care which skeleton you take; pick one.)

This category is noteworthy in that it contains one object for each equivalence class of categories in $\textbf{Cat}$, making it perhaps more useful than looking at $\bf{Skel({Cat})}$ itself, which only contains one object for each isomorphism class of categories. My questions are:

Does $\bf{Skel({Cat}_{Skel})}$ have a name?
Has this category been studied in any detail, and if so, can someone please reference me towards any research that's been done on its structure?
Is there an essentially equivalent construction which might be defined more simply than the way I've laid it out here?
Are there any useful areas of study in which this category naturally arises?

Lastly, I've glossed over the usual foundational issues which arise when considering $\bf{Cat}$, mostly because I don't care whether you use Grothendieck universes, or a class-set theory, or only look at small categories, or some other way of solving the problem. Feel free to use any foundational approach that you want which makes $\bf{Skel({Cat}_{Skel})}$ to be consistent.

What's the difference between ZFC+Grothendieck, ZFC+inaccessible cardinals and Tarski-Grothendieck set theory?

2012-07-22T00:38:00Z

Say that "U" is the axiom that "For each set x, there exists a Grothendieck universe U such that x $\in$ U", where Grothendieck universes are defined in the usual way (or, if that's unclear, in this way). Also, say that "Ca" is the axiom that "For each cardinal κ, there is a strongly inaccessible cardinal $\lambda$ which is strictly larger than κ."

It's known that ZFC+U and ZFC+Ca are completely equivalent and prove the same sentences. A sentence is a theorem of ZFC+U iff it's a theorem of ZFC+Ca.

In addition to the above, there's also Tarski-Grothendieck set theory, which can be found here. The axioms of TG are

The axiom stating everything is a set
The axiom of extensionality from ZFC
The axiom of regularity from ZFC
The axiom of pairing from ZFC
The axiom of union from ZFC
The axiom schema of replacement from ZFC
Tarski's axiom A

Tarski's axiom A states that for any set $x$, there exists a set $y$ containing, $x$ itself, every subset of every member of $y$, the power set of every member of $y$, and every subset of $y$ of cardinality less than $y$.

These three axioms from ZFC are then implied as theorems of TG:

The axiom of infinity
The axiom of power set
The axiom schema of specification
The axiom of choice

My question is as follows: is TG also completely equivalent to ZFC+U and ZFC+Ca, equivalent in the same sense that something is a theorem of TG iff it's a theorem of the other two? Is TG just an axiomatization of ZFC+U/ZFC+Ca which removes redundant axioms and allows them to just be theorems? Or is there some subtle difference between TG and ZFC+U/ZFC+Ca, in that there's some sentence which TG proves that's undecidable in ZFC+U/ZFC+Ca or vice versa?

In other words, instead of typing ZFC+Grothendieck, can I just type TG and be referencing a different axiomatization of the exact same thing?

Are Conway's omnific integers the Grothendieck group of the ordinals under commutative addition?

2012-07-25T00:41:57Z

This is a question in two parts.

Say that $\mathbf{On}$ is the proper class of all ordinal numbers in ZFC. We can define a binary operator over $\mathbf{On}$ which corresponds to the commutative version of ordinal addition; this has been called "Hessenberg addition" and "natural addition" before. It's also the operation you get by restriction of the $+$ operation from Conway's surreals to the subchain of ordinals (e.g. surreals with empty right set). I'll use the $+$ symbol for this operation over the ordinals.

$\langle\mathbf{On},+\rangle$ is a commutative monoid, which hence admits the notion of constructing a Grothendieck group $\mathrm{K}(\mathbf{On})$. The group $\langle\mathrm{K}(\mathbf{On}),+\rangle$ hence adds expressions such as $\omega$, $\omega-1$, $\omega^\omega - \omega^2 + 5$, etc. to the ordinals.

Question 1: is $\mathrm{K}(\mathbf{On})$ equivalent to Conway's "omnific integers" $\mathbf{Oz}$? In Conway's "On Numbers and Games," he defines an omnific integer $x$ as one which can be represented as a surreal number $\left \{ x-1 \mid x+1 \right \}$. Are these two classes isomorphic to one another?

It's also noteworthy that the field of fractions $Quot(\mathbf{Oz})$ is the full field $\mathbf{No}$ of surreal numbers. We can further turn $\mathrm{K}(\mathbf{On})$ into a ring $\langle\mathrm{R}(\mathbf{On}),+,\times\rangle$ by defining a new commutative operation called $\times$, called the "Hessenberg product", "Haussdorff product" or "natural product" of ordinals, which is commutative, associative, has an identity of 1, and distributes over the Conway normal form of the ordinal. A good definition for the Hessenberg product can be found on pages 24-25 of Ehrlich 2006.

Question 2: even if $\mathrm{K}(\mathbf{On})$ isn't isomorphic to $\mathbf{Oz}$, is $Quot(\mathrm{R}(\mathbf{On}))$ isomorphic to $\mathbf{No}$?

I'm tempted to answer in the negative for #1, as $\sqrt{\omega}$ is in $\mathbf{Oz}$, but is it in $\mathrm{R}(\mathbf{On})$? That is, given $\mathrm{K}(\mathbf{On})$ and ordinary commutative multiplication, is it the case that $\omega$ becomes a perfect square?

_{(Also, a last note - I'm aware that $\mathbf{On}$ is a proper class. I'm not sure what foundational issues arise specifically in the above question, but I don't care how you want to handle them - NBG set theory, Grothendieck universes, whatever.)}

Answer by Mike Battaglia for How do you compute the dual norm of an induced norm on a subspace of a finite-dimensional Lp-normed vector space?

2012-07-25T06:41:19Z

An exact solution can be found here using the Hahn-Banach Theorem: http://math.unl.edu/~s-bbockel1/928/node25.htm

Using this, you can show that $V^∗_S$ is isometrically isomorphic to $V^∗/S$°, where $S°$ is the subspace in V∗ for which $s(t)=0$ for $s$ in $S°$ and $t$ in $S$. – Mike Battaglia Jul 21 at 4:06

How do you compute the dual norm of an induced norm on a subspace of a finite-dimensional Lp-normed vector space?

2012-07-18T20:34:25Z

Say you have a finite-dimensional vector space $V$ with an $L^p$ norm on it. In general, the norm induced on a subspace $V_s$ of doesn't have to be another $L^p$ norm, so the unit sphere in $V_s$ using this induced can be some strange shape.

Given $V_s$ and a norm $||·||$ induced this way on it, how can one compute an expression for the dual norm $||·||_*$ on $V_s^*$, the dual space of linear functionals on $V_s$?

I understand that this norm must satisfy the relationship $||w||_* = \text{sup }\frac{w(v)}{||v||}$ for $v$ in $V_s$ and $w$ in $V_s^*$, and that this means I need to find the intersection of the unit sphere in $V_s$ with the direction specified by $w$. However, I'm not sure what a good strategy might be to actually find an expression for the dual norm in this way. I thought that some implication of Hahn-Banach might help to pave the way forward, but after some research I still haven't seen anything obvious.

I do have a hunch that for the case where the norm on $V$ is $L^1$ or $L^\infty$, and hence where the unit sphere for induced norm on $V_s$ is some sort of polytope, that the unit sphere on $V_s^*$ will be the dual polytope exchanging faces and vertices.

Generalized Grassmannians that parameterize the submodules of a module

2012-06-21T08:53:50Z

I'm looking for something like a Grassmannian, but which parameterizes the submodules of a module rather than the subspaces of a vector space. Most specifically, I'm looking for something which parameterizes the submodules of specifically $\mathbb{Z}^n$. So another way to say it is that I'm looking for a space parameterizing for the subgroups of a free abelian group. (A moduli space?)

I've seen some references to the concept of a "Grassmannian of submodules" here and there (like the papers on the first page of https://www.google.com/search?q=%22grassmannian+of+submodules%22) but can't figure out if this handles modules like $\mathbb{Z}^n$ or not.

Does anyone know if such an object exists and if so, how to construct it? Where I can get more information on this?

EDIT: to give a bit more info, the only specific application I really care about is parameterizing the free subgroups of a free abelian group, or the "lattices" in the $\mathbb{Z}$-module $\mathbb{Z}^n$, etc. A solution which works only for that, but which doesn't handle more exotic modules would be fine for my purposes. (And if it doesn't work out for all free abelian groups in general, then having a solution for at least finitely generated free abelian groups would even be a great start.)

I framed the question in terms of the "submodules of a module" in general just because I saw some references to there being a "Grassmannian of submodules" before, so I thought such a construction might be widely known.

Comment by Mike Battaglia

2013-03-26T02:23:07Z

Andreas, with respect to your last point, I think it would be a good exercise for me, since I haven't delved this deeply into the issue of NBG and universes. Can you recommend Hatcher's book as a good reference about this general topic then, for me to do this exercise?

Comment by Mike Battaglia

2013-03-26T02:21:41Z

Hi Andreas - the thing about $\omega$ was just an example to highlight a situation where a nonstandard model of ZFC is constructed in another theory T, and then one of the things from the model (e.g. that $\omega$ is well-founded) doesn't translate correctly in the "naive" way back to T (e.g. if you use T's $\in$-relation instead of the model's). By analogy, I was curious if things about NBG might get "lost in translation" when modeling the theory with a universe. But, if I understand correctly, it seems like things really should work out nicely in this case. Thanks for responding.

Comment by Mike Battaglia

2013-03-25T16:18:34Z

Sergei: OK, thanks. That's very useful and helps to solve the rest of my problem. If you want to resubmit your comment as an answer, I'll accept it and give you the bounty.

Comment by Mike Battaglia

2013-03-24T16:58:39Z

Integral #1 is $\mu^m(f)$, treated as an $L^m$ norm, and integral #2 is $\hat \mu^m(f) = \left(\frac{1}{\lambda(B_p)}\int_{B_p}\left(\frac{f(v)}{\|v\|}\right)^m dv\right)^\frac{1}{m}$. You're saying that the way you envision treating $\mu^m(f)$ as an $L^m$ norm makes $\mu^m(f) = \hat \mu^m(f)$, right? Note that this is the "fixed" $\hat \mu^m(f)$ integrating $\frac{f(v)}{\|v\|}$.

Comment by Mike Battaglia

2013-03-24T10:06:36Z

Also, so I understand correctly, are you saying that $\mu^m(f)$, treated as an $L^m$ norm on a function space, approaches the integral of the (with fixed denominator) $\hat \mu^m(f)$ in the limit? Are the two integrals (the $L^m$ norm and the $\hat \mu^m(f)$ one) exactly the same as formalized, now that I've put $\|e\|$ back in the denominator?

Comment by Mike Battaglia

2013-03-24T10:01:54Z

Oh no, sorry Sergei, your initial interpretation of my denominator was right! I wrote the wrong thing but changed it now. But yes, I've thought of this exact homothety before: instead of expanding r, we hold r at 1 and interpolate between points on the lattice. I wasn't sure if this would converge to the same thing as the integral, but your idea to treat this as a Riemannian integral sum is good.

Comment by Mike Battaglia

2013-03-24T09:43:16Z

Lastly, I phrased this question specifically in terms of work that's been done on the surreals, but it sounds like from your response that there's a large body of work relating NBG and Grothendieck universes in general. If you have a good text I could read on that subject, I'd much appreciate it. (If there are well-known general results from logic and model theory on this subject which could be easily adapted to the surreals, I might go back to stackexchange to ask more about it.)

Comment by Mike Battaglia

2013-03-24T09:37:01Z

This is what I'm worried about when "translating" results about NBG in ZFC+AU, because I don't want to continue using the perspective of NBG. Instead, I just want to create a universe $U$ large enough to contain all of the surreals that I care about, and then I want to prove theorems about $U$ in terms of the language of ZFC+AU instead. So how do I ensure that, for instance, Ehrlich's isomorphism between the "maximal" $\mathbb{R^\ast}$ and $\mathbf{No}$ in NBG holds for the universe in ZFC+AU itself, not just from the interpreted perspective of $U$ as a model of NBG?

Comment by Mike Battaglia

2013-03-24T09:11:07Z

Thanks. A question though, about "translating" things from NBG to ZFC+AU: consider models of ZFC with ill-founded $\omega$. The model never "knows" that $\omega$ is ill-founded, but the ambient theory does. Thus, the theorem "$\omega$ is well-founded" doesn't "translate" correctly from the perspective of the model of ZFC to the perspective of the ambient theory in which the model is constructed. (cont'd)

Comment by Mike Battaglia

2013-03-23T04:46:08Z

Sorry, I'm getting all screwed up here. You're talking about Cantor normal form, and my example uses Conway normal form. OK, it all makes sense now.

Comment by Mike Battaglia

2013-03-23T03:34:06Z

Typo - that's $… + \omega^5*2 + \omega^3*2 + \omega*2$ we're subtracting; the ellipsis on the right hand side should have been gone. But you get the point; we end up with $\sum_{n\in\mathbb{N}} \omega^n(-1)^n$. So something's gotta give: either the ring isn't an ordered ring (which I think it should be) or the Grothendieck group + commutative operations don't play nice with the Cantor normal form.

Comment by Mike Battaglia

2013-03-23T03:29:14Z

What element in the ring is this - is it positive or negative? And also, if you expect that multiplication distributes over addition, then multiplication by $\omega + 1$ gives you $1$. I didn't realize this when I made my initial post, but I'm not sure if this means that somehow, despite $\mathbf{On}$ being well-ordered, that $K(\mathbf{On})$ isn't - or if Cantor normal form doesn't extend as well to the Grothendieck group as you might expect.

Comment by Mike Battaglia

2013-03-23T03:22:56Z

Will: I see I missed a post of yours mid-type. I'll deal with the divisibility thing in a second, but first, I don't see how you're expecting Cantor normal form to work here, either with the Grothendieck group or the commutative operations. Perhaps the easiest way to demonstrate this is to give you the example of the ordinal $… + \omega^2 + \omega + 1$, where the exponents in the sum go through all natural numbers. Now say that we subtract the ordinal $… + \omega^5*2 + \omega^3*2 + \omega*2 + …$ from it. We're left with the ordinal $… + \omega^4 - \omega^3 + \omega^2 - \omega + 1$.

Comment by Mike Battaglia

2013-03-23T02:30:50Z

(contd) Or maybe not, since ZFC isn't strong enough to say if large cardinals exist, and hence if these elements are in the ring to begin with (and if they are, whether they'd be in the ideal you mention). So while it's true that $\sqrt{\omega}$ isn't in $K(\mathbf{On})$ iff the quotient by this enormous ideal doesn't contain $\sqrt{\omega}$, the foundational issues here leave a lot of lee-way for what exactly is in that ideal. That being said, I wonder if the existence of $\sqrt{\omega}$ could be undecidable.

Comment by Mike Battaglia

2013-03-23T02:18:14Z

The suggestion was the instead to mod by the ideal generated by $\omega^n$ for all ordinals $n > 1$. But that's definitely not a trivial statement - this has to be one of the strangest ideals in all of ring theory. There are things like ordinal-linear combinations of measurable cardinals, minus a few Mahlo cardinals each to the power of aleph-aleph-aleph-three, and if you're lucky you can then perhaps divide by the Church-Kleene ordinal and subtract the first uncountable ordinal, squared. (cont'd)