Finite ultraproduct

Question

I stucked when trying to prove:

If $A_\xi$ are domains of models of first order language and $|A_\xi|\le n$ for $n \in \omega$ for all $\xi$ in index set $X$ and $\mathcal U$ is ultrafilter of $X$ then $|\prod_{\xi \in X} A_\xi / \mathcal U| \le n$.

My tries:

If $X$ is finite set then $\mathcal U$ is principal. Then singleton $\{x\}\in \mathcal U$ and $|\prod_{\xi \in X} A_\xi / \mathcal U| = |A_x|$. If $\mathcal U$ is not principal then for $x \in X$ there is $S_x \in \mathcal U$ with $x \notin S_x$. Then for every $k \in \omega$ there exists equivalence class corresponding to $S_{x_1} \cap \dots \cap S_{x_k}$ with size greater $|A_1|\cdot \dots \cdot |A_k|$.

Can there be said anything about a structure of the ultrafilter if $X$ is infinite? And how to prove it?

Answer 1

The statement you are trying to prove is a consequence of Łoś's theorem - if every factor satisfies "there are no more than $n$ elements", then the set of factors that satisfy it is $X$, which is in $\mathcal{U}$, so by Łoś's theorem the ultraproduct will satisfy that sentence as well. Note that "there are no more than $n$ elements" is the sentence $$ (\exists x_1)\cdots(\exists x_n)(\forall y)[ y = x_1 \lor \cdots \lor y = x_n] $$

Thus one way to come up with a concrete proof of the statement you want is to examine the proof of Łoś's theorem and specialize it to the situation at hand.

As a side note, if every factor is finite, but there is no bound on the sizes of the factors, then the ultraproduct will not be finite. The difference is that there is no longer a single sentence of interest that is true in all the factors, because finiteness is not definable in a first-order language.

---

I assume that the OP figured out the hint, so let me spell out the answer for reference. Because $|A^\xi| = k$ for all $\xi \in X$, we can write $A^\xi = \{a^\xi_1, \ldots, a^\xi_k\}$ for each $\xi$. For $1 \leq i \leq k$ define $\alpha_i$ by $\alpha_i(\xi) = a^\xi_i$. Then every $\beta$ in the ultraproduct is equal to $\alpha_i$ for some $1 \leq i \leq k$. Proof: For $1\leq i \leq k$ let $B_i = \{\xi : \beta(\xi) = a^\xi_i\}$. Then $$X = B_1 \cup B_2 \cup\cdots\cup B_k.$$ Because $\mathcal{U}$ is an ultrafilter, one of the sets $B_i$ must be in $\mathcal{U}$, and if $B_i \in \mathcal{U}$ then $\beta = \alpha_i$ in the ultraproduct, QED. Thus we can explicitly name the $k$ elements of the ultraproduct: $\alpha_1, \alpha_2, \ldots, \alpha_k$.

Answer 2

For $k=1,2,3,\dots, n$, let $X_k$ be the set of all $\xi\in X$ such that $|A_{\xi}|=k$.

Since $X$ is the finite disjoint union $X_1\cup X_2\cup \cdots \cup X_n$, there is precisely one value of $k$ such that $X_k\in \mathcal{U}$. The ultrapower then has $k$ elements.

Why does it have $k$ elements? We can think in terms of sentences: the assertion that there are precisely $k$ elements is true "almost everywhere" modulo $\mathcal{U}$.

The following is a perhaps somewhat more concrete reason, if the word concrete can be applied to ultrafilters. Work over the $X_k$ which is in $\mathcal{U}$. For $\xi\in X_k$, we can assume that $A_{\xi}$ consists of the numbers $1,2,\dots,k$. Then any element of the product $\prod A_{\xi}$ is almost everywhere (modulo $\mathcal{U}$) equal to one of the sequences of all $1$'s, all $2$'s, and so on up to all $k$'s.