Inverting the Furstenberg correspondence

Given a sequence of sets An⊆{0,…,n−1}, the Furstenberg correspondence principle provides a shift-invariant measure on2N that encodes combinatorial information about infinitely many of the An's. Here it is shown that this process can be inverted, so that for any such measure, ergodic or not, there are finite sets whose combinatorial properties approximate it arbitarily well. The finite approximations are obtained from the measure by an explicit construction, with an explicit upper bound on how large n has to be to yield a sufficiently good approximation.

We draw conclusions for computable measure theory, and show, in particular, that given any computable shift-invariant measure on 2N, there is a computable element of 2N that is generic for the measure. We also consider a generalization of the correspondence principle to countable discrete amenable groups, and once again provide an effective inverse.