Comparing sizes of sets of integers

Question

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

1. $A<B$ 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).

Answer 1

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 $[0]$ 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)=[0].$

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/[0],$ 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.$