One thing I'd like to know is that, for any finite set D of positive integers, there is a unique "biggest" set S_0 of non-negative integers no two of whose elements differ by an element of D, and that moreover S_0 is an eventually periodic set. (E.g., if D = {3,5}, the "biggest" set of nonnegative integers with forbidden differences 3 and 5 is S_0 = {0,2,4,6,...}.) Here I am using the Grandi-Abel partial ordering on the power set of {0,1,2,...}; even though this not a total ordering on the whole power set of {0,1,2,...}, I still believe that {0,2,4,6,...} dominates every set with forbidden differences 3 and 5. One thing that frustrates me about this theory is that I can't figure out how to do compactness arguments. For instance, even leaving aside the issue of uniqueness, how can I show that there exists AT LEAST ONE maximal set? That is: Given a finite set D of positive integers, let X_D be the collection of sets of nonnegative integers no two of which differ by an element of D. Given S and S' in X_D, say S dominates S' iff there exists some epsilon > 0 such that |S|_q is greater than or equal to |S'|_q for all q in the interval (1-epsilon,1). Say S strictly dominates S' iff S dominates S but not vice versa. Must X_D contain a set S such that X_D does not contain a set that strictly dominates S? Normally this kind of claim (existence of an extremum) would follow trivially from compactness, but I don't see how to put a topology on X_D and on R(q) that would make this work out. In this connection I should mention how the Ross-Littlewood Paradox plays out in my theory. The set {0} is strictly dominated by the set {1,2,...,10}, which is strictly dominated by the set {2,...,20}, which is strictly dominated by the set {3,...,30}, and so on; but when we take the limit of these sets of integers (which is the empty set of integers!), we don't get a set of integers that dominates all of them, because the intervals (1-epsilon,1) get shorter and shorter, and their intersection is the empty interval. Jim Propp On Mon, Jan 30, 2017 at 12:30 PM, James Propp <jamespropp@gmail.com> wrote:
If S is an eventually-periodic subset of {0,1,2,...}, then |S|_q, defined as the sum of q^n as n ranges over S, is a rational function. The map from S to |S|_q is a finitely-additive measure ("valuation" is probably a better word to use) taking its values in the ring of rational functions in q. If we order that ring "at 1", we get a way to compare sizes of sets of natural numbers. In fact, it is a total ordering (though not a well-ordering) of the set of eventually-periodic subsets of {0,1,2,...}.
This may remind some of you of the ordered fields that you get by adjoining to R a formal infinitesimal or a formal infinity. In both cases, you've got the field R(x), and all that differs is the ordering you put on it. My proposal is similar, except that I'm ordering the field at 1 rather than 0 or infinity.
Writing |S|_q as A / (1-q) + B + lower order terms, we can focus on just A and B. A measures the density of S, and B captures finer information. The first thing to notice about B is that it's sensitive to perturbations that don't affect the density; if you add an element to S, you increase B by 1, and if you remove an element from S, you decrease B by 1 (even though A doesn't change).
But B conveys subtler information too:
For instance, compare {0,2,4,...} with {1,3,5,...}; the former has B = 1/4 while the latter has B = -1/4. Informally, we say that sliding the set of even nonnegative integers over the right by 1 reduces the "size" of the set by 1/2. And that makes sense, because if you slide it over to the right again, "losing" half an element again, you get {2,4,...}, which is missing precisely 1/2 + 1/2 = 1 of the elements of {0,2,4,...}.
(Yeah, this way of measuring sets is not translation-invariant. But you gain something nice in return: a proper subset of a set is always strictly smaller than the set.)
I recently learned that Ilya Chernykh has been exploring the same circle of ideas (see http://mathoverflow.net/questions/215762/non-standard- numbers-and-exponential-form-of-zeta-function), but I don't know of anyone else who's fished in these waters. (You could argue that analytic number theorists know all this already and don't think it's interesting.)
Anyway, the map that sends S to (A,B) should I believe be called a "Grandi valuation", since it gives a rigorous framework for making sense of Grandi's formula 1 - 1 + 1 - 1 + ... = 1/2. (Indeed, Bernoulli's formula 1 + 0 - 1 + 1 + 0 - 1 + ... = 2/3 can be understood in the same way: {0,3,6,...} exceeds {2,5,8,...} by 2/3 of an element, if we measure size using this valuation.)
More precisely one might call the map the "Grandi-Abel valuation", since it uses Abel regularization of the summation of the indicator function of S. Anyway, other ways of taming divergent series exist, so there will be other Grandi valuations. And maybe the term should also be applied to the non-truncated valuation (the one that takes values in the ordered field R(q)), which gives the sets {0,3,4,7,8,11,...} and {1,2,5,6,9,10,..} different "sizes" (the former is infinitesimally larger). In the non-truncated valuation, we get a translation-covariance property that might console us for the loss of translation-invariance: shifting a set corresponds to multiplication by q.
One can try to extend the Grandi valuation to sets that aren't eventually periodic, as I do in my MathOverflow post, and to some extent this works. However, one can construct sets that are incomparable, so if you're a fan of number systems that satisfy trichotomy, it's important not to overreach.
I haven't given a definition of what a Grandi valuation is in general, but a hallmark is that a Grandi valuation should assign to any eventually periodic set S a value in some module from which the quantity I called "B" can be derived.
Anyway, I have a bit of a crush on this notion, and I'd like to put it to some sort of use. My current target is a general uniqueness theorem in the context of one-dimensional packing.
Jim
P.S. It has occurred to me that when we measure infinite sets in this way, a cute name for this kind of generalized cardinality would be "grandiosity". But I think it's prudent to avoid introducing this term until I have a better idea for how it should be defined!