Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)] $

share|cite|improve this question
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$.

share|cite|improve this answer
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
@alancalvitti: No. Context makes it obvious that we’re dealing with ZFC or something similar enough to make no difference (e.g., NBG). – Brian M. Scott Jan 30 '13 at 20:17
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
@BrianM.Scott Actually, one could also weasel out by saying that if there are no non-trivial ultrafilters, then the proposition is vacuously true... – Zhen Lin Feb 1 '13 at 15:43
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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