## Amenability and ultrafilters

Among hundreds of equivalent definitions of amenability (for discrete, countable, groups), I would like to discuss two which are most common:

A1. A group $G$ is amenable if it admits a Folner sequence.

A2. A group $G$ is amenable if it admits an invariant mean.

However, proofs of equivalence that I know (even for $G={\mathbb Z}$) require either axiom of choice or, at least, existence of a nonprincipal ultrafilter on ${\mathbb N}$.

Question: Is there a proof that A1 $\iff$ A2 which uses only ZF axioms? Or, maybe $A1\iff A2$ implies existence of nonprincipal ultrafilters, maybe in a weakened form?

This question was discussed a bit in http://mathoverflow.net/questions/12169/why-are-abelian-groups-amenable and http://mathoverflow.net/questions/93897/why-groups-that-admit-folner-sequences-are-amenable but not in the above form.

Note: I am not a logician, but a geometric group-theorist and I frequently use ultrafilters. As the result I am often asked if the results could be proven without ultrafilters. For most proofs my answer usually is: "Yes, if you work much harder and write ugly and long proofs." However, I do not know the answer in the context of amenable groups.

-
Simon's answer is more complete, but an easy way to see that A1 does not imply A2 in ZF is to work in a model of ZF + all sets of reals have the property of Baire. Certainly the integers will have a Folner sequence in this model, but a straightforward Baire category argument shows that no shift-invariant finitely additive probability measure on the integers is Baire measurable (as a function from $2^\mathbb{Z}$ to $\mathbb{R}$). – Clinton Conley Apr 19 2012 at 17:49
In the previous comment I really meant ZFDC + BP to avoid silly pathologies. – Clinton Conley Apr 19 2012 at 19:32
@Clinton: Thank you for the answer. I am probably missing something simple, but how do you show non-existence of a finitely-additive Baire measurable probability measures on $2^{\mathbb Z}$? – Misha Apr 20 2012 at 19:28
Misha, Here's a sketch of the argument I have in mind. Let $f:2^\mathbb{Z} \to \mathbb{R}$ be our putative Baire measurable measure. By generic ergodicity of the shift of $\mathbb{Z}$ on $2^\mathbb{Z}$, $f$ is constant on a comeager set. Moreover, since complementation (in $\mathbb{Z}$, viewed as an automorphism of $2^\mathbb{Z}$) is a homeomorphism, WLOG we may assume this constant equals $1/2$. Now fix dense open sets $U_n \subseteq 2^\mathbb{Z}$ whose intersection is contained in the $f$-preimage of $1/2$. [cont.] – Clinton Conley Apr 21 2012 at 4:19
Inductively build finite binary strings $u_n$, $v_n$, $w_n$ in $2^{[-k_n,k_n]}$ for some large $k_n$ such that (a) $u_n$, $v_n$, $w_n$ have disjoint supports, (b) the basic open neighborhood determined by $u_n$ (and $v_n$ and $w_n$) is contained in $U_n$, and (c) $u_{n+1}$ extends $u_n$ (and $v$ and $w$). In the end, you've built strings $u$, $v$, $w$ in $\bigcap_n U_n$ of disjoint support, and thus three disjoint subsets of $\mathbb{Z}$ each with measure $1/2$, a contradiction. – Clinton Conley Apr 21 2012 at 4:24
Of course, $ZF$ is enough to prove that $\mathbb{Z}$ has a Folner sequence. But, as you point out, $ZF$ is not enough to prove that $\mathbb{Z}$ has an invariant mean. Thus $ZF$ does not prove the equivalence of A1 and A2.
On the other hand, the Hahn-Banach Theorem is enough to prove the equivalence of A1 and A2 for countable discrete groups and Pincus-Solovay have constructed a model of $ZF$ in which the Hahn-Banach Theorem is true but there are no nonprincipal ultrafilters on $\mathbb{N}$. Hence the equivalence of A1 and A2 for countable groups does not imply the existence of nonprincipal ultrafilters on $\mathbb{N}$.
 @Simon: Yes, I know that Hahn-Banach theorem implies $A1\iff A2$ (I did not know though of the model where Hahn-Banach holds but Ultrafilter lemma does not). Did anybody actually prove that $A1\iff A2$ does not follow ZF only? It does not seem obvious to me... – Misha Apr 19 2012 at 17:36 Solovay constructed a model of ZF in which $\mathbb{Z}$ does not have an invariant mean. But, of course, $\mathbb{Z}$ has a Folner sequence in this model. – Simon Thomas Apr 19 2012 at 19:09