# Cardinality of ultraproduct

Let $\mathcal{U}$ be a non-principal ultrafilter on $\omega$. Let $S:\omega\rightarrow\omega$ be monotone and unbounded. Let $T_{\mathcal{U},S}=\prod\limits_{\mathcal{U}}S(n)$ the ultraproduct as set. What is the supremum and infimum of $|T_{\mathcal{U},S}|$ as $\mathcal{U}$ and $S$ change.

Trivially, $\aleph_{0}\leq|T_{\mathcal{U},S}|\leq 2^{\aleph_{0}}$. That's all I can do, don't know how to proceed. I am guessing that these are indeed infimum and supremum, but can't prove neither.

(I added the context, but apparently some people still think it is not a good question, so whatever)

Also, to add in the comment above, apparently the new bound is $\aleph_{1}\leq|T_{\mathcal{U},S}|\leq 2^{\aleph_{0}}$ now. Thanks.

I proved the bound of $\aleph_{1}$, can this question be reopened or not? I can't figure out what would make you people happy now.

(this is not a homework question) Also, I solved it, the answer is that the only possibility is $2^{\aleph_{0}}$.

• What have you tried? Where did you get stuck? Don't just ask us to do your homework for you. Sep 1, 2015 at 23:50
• You can improve that lower bound: recursively construct a family of $\omega_1$ pairwise almost disjoint functions in $\prod_nS(n)$. Sep 2, 2015 at 5:57
• Saharon Shelah. On the cardinality of ultraproduct of finite sets, J. Symbolic Logic, 35 (1), (1970), 83-84. Sep 3, 2015 at 3:55
• (The specific case in this exercise is easier than the result in Shelah's paper. A proof and references can be found in the monograph by Comfort and Negrepontis.) Sep 4, 2015 at 23:48
• Relaying a comment from an anonymous user who tried to post it as an edit: "@Adres Caicedo: I looked up the paper on JSTOR, and I am not sure why this is any easier than the one on JSTOR (and assuming that I am correct in my proof, I got stronger result). I can't look up the one in the other monograph, so I don't know what result was proved there. Can you clarify for me the difference between the one here, the one in the paper, and the one in the monograph? (sorry I can't post comment)" Sep 5, 2015 at 2:21

I saw the following answer once in a post of Andres E Caicedo, but I could not find it this time.

If $M=\prod_\mathcal{U} M_i$ is an ultraproduct of finite structures with $|M_i|\rightarrow_{\mathcal{U}} \infty$, then $|M|=2^{\aleph_0}$

Note that $$\left|\prod_\mathcal{U}M_i\right|\leq \left|\prod_{i\in I} M_i\right|\leq |\mathbb{N}^{\mathbb{N}}|=|\mathbb{R}|,$$

so it suffices to show that $|\mathbb{R}|\leq|\prod_\mathcal{U} M_i|.$

We will need the following combinatorial lemma:

There exists a family $\mathcal{F}$ of functions $f:\mathbb{N}\rightarrow\mathbb{N}$ such that:

1. $|\mathcal{F}|=2^{\aleph_0},$
2. For any $f\in\mathcal{F}$ and any $n\in\mathbb{N}$, $f(n)<2^n$,
3. If $f\neq g$ are in $\mathcal{F}$, then $\{n\in \mathbb{N}: f(n)=g(n)\}$ is finite.

Proof of the lemma: Given a set $A\subseteq \mathbb{N}$ let $f_A:\mathbb{N}\rightarrow\mathbb{N}$ be given by $$f_A(n)=\sum_{k<n}\chi_A(k)2^k,$$ where $\chi_A$ is the characteristic function of $A$. Then the family $\mathcal{F}=\{f_A:A\subseteq \mathbb{N}\}$ satisfies the three conditions. End of proof of Lemma

Let $A_n=\{k\in\mathbb{N}:2^n\leq |M_k|<2^{n+1}\}$, so the sets $A_n$ are all finite and partition $\mathbb{N}$. For each $k\in A_n$ let $\{a_{k,j}: j<2^n\}$ be a list of $2^n$ distinct elements of $M_k.$

Let $\mathcal{F}$ be a family as in the Lemma. For $f\in \mathcal{F}$, let $h_f: \mathbb{N}\rightarrow\bigcup_k M_k$ be given by $h_f(k)=a_{k,f(n)},$ where $n$ is such that $k\in A_n.$

Note that if $f\neq g$ are in $\mathcal{F}$, then

$$\{k\in\mathbb{N}: h_f(k)=h_g(k)\}=\bigcup\{ A_n: n\in\mathbb{N},f(n)=g(n)\}$$

is a finite union of finite sets and therefore finite. Hence, $[h_f]_\mathcal{U}\neq [h_g]_\mathcal{U},$ and we are done.