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).

  • 1
    $\begingroup$ But the question is about subsets of $\mathbb Z$ not just of $\mathbb N$. $\endgroup$ Sep 2, 2020 at 16:48
  • 6
    $\begingroup$ 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. $\endgroup$ Sep 2, 2020 at 16:55
  • 1
    $\begingroup$ @Vepir: Condition 2 is not preserved by bijections. $\endgroup$ Sep 2, 2020 at 17:24
  • 1
    $\begingroup$ 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$. $\endgroup$
    – bof
    Sep 3, 2020 at 6:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – bof
    Sep 3, 2020 at 6:22

1 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.$

  • $\begingroup$ 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? $\endgroup$ Sep 8, 2020 at 2:52
  • $\begingroup$ @AlexanderPruss: yes, it generalizes to give a total preorder on the powerset of any abelian group $G.$ $\endgroup$
    – Harry West
    Sep 10, 2020 at 6:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.