Skip to main content
3 of 4
edited to make non-trivial

Comparing sizes of sets of integers

Is there a total preorder $\lesssim$ on the power set of the integers 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).