Comparing sizes of sets of integers

Is there a total preorder $$\lesssim$$ on the power set of $$\mathbb Z$$ such that:

1. $$A if $$A\subset B$$ (proper subsets are smaller)

2. $$1+A\lesssim 1+B$$ iff $$A\lesssim B$$ (where $$1+C = \{1+c:c\in C\})$$ (shift invariance)

3. if $$A\cap C=B\cap C=\varnothing$$, then $$A\lesssim B$$ iff $$A\cup C\lesssim B\cup C$$ (additivity)?

The answer is positive if (3) is dropped or if (2) is dropped (easiest way for me to see it is by using an ultrafilter to create a hyperreal-valued finitely additive strictly positive measure on $$\mathbb Z$$). The answer is trivially positive with $$\mathbb N$$ in place of $$\mathbb Z$$: just use lexicographic ordering on the indicator functions.

If one adds reflection invariance ($$-A\lesssim -B$$ iff $$A\lesssim B$$), the answer is easily seen to be negative.

It's easy to show that such a comparison would have various weird properties, such as that it says that there are more positive odd numbers than positive even numbers, and that either: (a) $$(-\infty,a]\cap\mathbb Z < [b,\infty)\cap\mathbb Z$$ for all $$a,b$$ (it is biased to the right), or (b) $$(-\infty,a]\cap\mathbb Z > [b,\infty)\cap\mathbb Z$$ for all $$a,b$$ (it is biased to the left).

• But the question is about subsets of $\mathbb Z$ not just of $\mathbb N$. Sep 2 '20 at 16:48
• Interesting: I've never heard of "integers" as used for anything but $\mathbb Z$. I always say "naturals" for $\mathbb N$. I never heard "relative integers" before, but there are 6660 google hits for it, so it's a real phrase. Sep 2 '20 at 16:55
• @Vepir: Condition 2 is not preserved by bijections. Sep 2 '20 at 17:24
• Interesting question. I have no idea about the answer, but I think condition (3) could be stated more neatly: $A\lesssim B$ iff $A\setminus B\lesssim B\setminus A$.
– bof
Sep 3 '20 at 6:11
• Without (2) I think the easiest way is to take an ultrafilter $\mathcal U$ on the set $S$ of all finite subsets of $\mathbb Z$ with the property that $\{F\in S:a\in F\}\in\mathcal U$ for every $a\in\mathbb Z$, and decree that $A\lesssim B$ iff $\{F\in S:|A\cap F|\le|B\cap F|\}\in\mathcal U$. Maybe that's the same as what you said, which I didn't actually understand.
– bof
Sep 3 '20 at 6:22

Yes, there is such a preorder. I will argue that there is a preorder on the space of bounded functions $$\mathbb Z\to\mathbb R$$ so that comparing indicator functions in this space does the job. A vector space preorder can be constructed from a suitable "positive cone", the set of non-negative elements, so the main task is to construct this cone.

Let $$M$$ be the set of non-negative, not identically zero, finitely-supported functions $$\mathbb Z\to\mathbb R.$$ Let $$B$$ be the real vector space of bounded functions $$\mathbb Z\to\mathbb R.$$ Let $$a*\phi$$ denote convolution of a function $$a\in B$$ by a function $$\phi\in M.$$ Define $$a\sim b$$ for $$a,b\in B$$ to mean that $$a*\phi=b*\psi$$ for some $$\phi,\psi\in M.$$ This is an equivalence relation because $$M$$ is a (commutative) monoid under convolution. The $$\sim$$-equivalence class $$$$ of zero is a linear subspace of $$B.$$

Define a good cone to be a set $$C\subset B$$ such that

• C1. $$y\in C\iff z\in C$$ whenever $$y\sim z,$$ and
• C2. $$C$$ is a convex cone ($$x,y\in C\implies \lambda x+\mu y\in C$$ for $$\lambda,\mu\geq 0$$), and
• C3. $$C\cap (-C)=.$$

Define $$C_0$$ to be the set of $$x\in B$$ such that $$x\sim y$$ for some non-negative function $$y\in B.$$ Because non-negative functions are closed under convolution by any $$\phi\in M,$$ the definition of $$C_0$$ simplifies slightly to $$x*\phi$$ being non-negative for some $$\phi\in M.$$ The set $$C_0$$ satisfies the good cone conditions: (C1) is obvious, for (C2) if $$x*\phi$$ and $$y*\psi$$ are non-negative and $$\lambda,\mu\geq 0$$ then $$(\lambda x+\mu y)*\psi*\psi$$ is non-negative, and for (C3) if $$x*\phi$$ is non-negative and $$x*\psi$$ is non-positive, then $$x*\phi*\psi$$ is identically zero so $$x\sim 0.$$ By Zorn's lemma there is a maximal good cone $$C$$ containing $$C_0.$$

Consider $$x\in B\setminus C.$$ Define $$C_x$$ to be the set of $$y\in B$$ such that $$y*\phi= x*\psi+c$$ for some $$\phi\in M$$ and $$\psi\in M\cup\{0\}$$ and $$c\in C.$$ By maximality of $$C,$$ the set $$C_x$$ is not good. (C1) holds: whenever $$y*\eta=z*\zeta$$ and $$y*\phi= x*\psi+c$$ we have $$z*\zeta*\phi=x*\psi*\eta+c*\eta,$$ which implies $$z\in C_x.$$ (C2) holds: if $$y*\phi= x*\psi+c$$ and $$y'*\phi'= x'*\psi'+c'$$ and $$\lambda,\mu\geq 0$$ then $$(\lambda y+\mu y')*\phi*\phi'=x*(\psi*\phi'+\psi'*\phi)+(c*\phi'+c'*\phi).$$ So (C3) fails: some $$y\not\sim 0$$ satisfies $$y*\phi= x*\psi+c$$ and $$y*\phi'=-x*\psi'-c'.$$ But then $$-x*\psi'*\phi-c'*\phi=y*\phi*\phi'=x*\psi*\phi'+c*\phi'$$ which implies $$x*(\psi*\phi'+\psi'*\phi)+(c*\phi'+c'*\phi)=0.$$ If $$\psi$$ and $$\psi'$$ are both zero, then $$c*\phi=-c'*\phi$$ is in $$C\cap (-C)$$ contradicting $$y\not\sim 0.$$ So $$\psi$$ and $$\psi'$$ are not both zero, which means $$-x\sim c*\phi'+c'*\phi\in C.$$ In other words $$x\in -C.$$

We have shown that $$C\cup (-C)=B.$$ The cone $$C$$ defines a total vector order on $$B/,$$ but to answer the question we just need to define $$S\lesssim T\iff 1_T-1_S\in C.$$ Your condition 1 comes from $$C_0\subset C$$ and (C3). Your condition 2 comes from (C1) - shifting is convolution by a delta function. Your condition 3 comes from $$1_{T\cup U}-1_{S\cup U}=1_T-1_S$$ whenever $$S\cap U=T\cap U=\emptyset.$$

• Am I right in thinking that this generalizes to any abelian group $G$ in place of $\mathbb Z$, with (2) replaced by $x+A\lesssim x+B$ iff $A\lesssim B$ for all $x\in G$? Or is there some step that fails? Sep 8 '20 at 2:52
• @AlexanderPruss: yes, it generalizes to give a total preorder on the powerset of any abelian group $G.$ Sep 10 '20 at 6:09