# The ultraproduct $\mathbb{N}^\mathbb{N} / \mathcal{F}$ is uncountable

I have to prove:

Let $\mathcal{F}$ be a non-trivial ultrafilter on $\mathcal{P}(\mathbb{N})$. Prove that the ultraproduct $\mathbb{N}^* = {\mathbb{N}^{\mathbb{N}}}/{\mathcal{F} }$ (I don't know if this is standard notation) is uncountable.

HINT: Prove there exist a function $F:\mathbb{N}^\mathbb{N} \rightarrow \mathbb{N}^\mathbb{N}$ such that for all $f,g \in \mathbb{N}^\mathbb{N}$, if $f \neq g$: $\exists n \forall m > n[(F(f))(m) \neq (F(g))(m)]$

-
Something about that hint doesn't pass compilation. Too many $f$'s. – Asaf Karagila Jan 30 '13 at 16:51
Note that if you just want uncountability, you can get it more easily by showing that there is a function $F:\omega_1\to{}^{\Bbb N}\Bbb N$ such that if $\alpha<\beta<\omega_1$, then $\exists m\forall n\ge m\Big(\big(F(\alpha)\big)(n)\ne\big(F(\beta)\big)(n)\Big)$. – Brian M. Scott Jan 30 '13 at 18:51

In the hint, the first $f$ should be $F$ to match the notation later. I suggest you define $F$ so that, for each function $f\in\mathbb N^{\mathbb N}$ and each natural number $n$, $F(f)(n)$ encodes the finite sequence $\langle f(0),f(),\dots,f(n)\rangle$.
Shouldn't the assumed axiom system be made explicit? According to Herrlich's AC, in ZF+AD there are no nontrivial ultrafilters on $\mathbb{N}$. Are there any on the powerset? Also are there any in other systems, eg ZF, ZFU, NBG? What about with reverse math systems? (Note: Herrlich writes "free" ultrafilters, but prof. Bergman consulted with colleagues @UCB and they seem to agree it means the same as nonprincipal). – alancalvitti Jan 30 '13 at 18:53
Thanks. I have a function $F$ with the desired property now. But how can I prove the ultraproduct uncountable? I see: $f \neq g \rightarrow$ not $F(f) \sim_{\mathcal{F}} F(g)$, but then? – natural Feb 1 '13 at 14:48
@natural: Then you’re done! Your $F$ is an injection from $\Bbb N^{\Bbb N}$ to $\Bbb N^{\Bbb N}/\mathscr{F}$, and it’s immediate that $$\left|\Bbb N^{\Bbb N}/\mathscr{F}\right|\ge\left|\Bbb N^{\Bbb N}\right|\;.$$ – Brian M. Scott Feb 1 '13 at 20:43