MathOverflow is a question and answer site for professional mathematicians. 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

let $(X_i)_{i \in I}$ be an infinite family of sets with $|X_i| \geq 2$. we define an equivalence relation on $X = \prod_{i \in I} X_i$ by $x \sim y \Leftrightarrow \{i : x_i \neq y_i\}$ is finite. what is the cardinality of $X/\sim$? we may endow the $X_i$ with group structures and write this set as $\prod_{i \in I} X_i / \oplus_{i \in I} X_i$.

it is easy to see that $\min_i |X_i| \leq |X/\sim|$ and $|X| \leq |X/\sim| * \max_i |X_i|$. in particular, if $|X_i|$ is constant, $|X/\sim| = |X|$.

if all the $X_i$ are finite, it can be shown $|X/\sim|=2^{|I|}$. the same equation holds, if every $X_i$ satisfies $\aleph_0 \leq |X_i| \leq |I|$ (I'll add the proofs if needed).

the general case struggles me.

share|cite|improve this question
Your second and third paragraphs are contradictory. (I believe the latter a lot more.) – Reid Barton Jan 8 '10 at 21:40
You are asking for the cardinal of a reduced product with respect to the filter of cofinite sets. You'll find relevant information Chen Chung Chang, H. Jerome Keisler, Model theory, for example. It appears to be quite complicated in general! – Mariano Suárez-Alvarez Jan 8 '10 at 22:14
up vote 5 down vote accepted

The cardinality of the reduced product is always the same as that of the product, modulo omitting finitely many unusually large $X_i$'s. (Even when $I$ is finite, in which case all $X_i$'s should be omitted.)

Arrange the sets $X_i$ in nondecreasing order of size in a wellordered sequence $(X_\alpha)_{\alpha<\tau}$. We may assume that $\tau$ is a limit ordinal. Otherwise, the last coordinate $\tau-1$ (like any single coordinate) contributes nothing to the reduced product. Omit $X_{\tau-1}$ and repeat as long as necessary.

I will show that then $|X| = |X/{\sim}|$ where $X = \prod_{\alpha<\tau} X_\alpha$.

Let $\kappa = \sup_{\alpha<\tau} |X_\alpha|$. Since each ${\sim}$-equivalence class has size $|\tau|\cdot\kappa$ (see note) we have

$|X| \leq |X/{\sim}|\cdot|\tau|\cdot\kappa = \max(|X/{\sim}|,|\tau|,\kappa).$

Since $|X| \geq 2^{|\tau|} > |\tau|$, we conclude that either $|X/{\sim}| = |X|$ or $|X/{\sim}| \leq |X| \leq \kappa$.

Since $\tau$ is a limit ordinal, the diagonal embedding $d:\kappa \to \prod_{\alpha<\tau} |X_\alpha|$, where

$d_\alpha(\xi) = \begin{cases} \xi & when\ \xi < |X_\alpha| \\ 0 & otherwise,\end{cases}$

shows that $\kappa \leq |X/{\sim}|$. So, in the case $|X/{\sim}| \leq |X| \leq \kappa$, we in fact have $|X/{\sim}| = |X| = \kappa$.

Note: The elements ${\sim}$-equivalent to a given $x \in X$ are obtained by selecting finitely many new values from the sets $X_\alpha-\{x_\alpha\}$ to replace the corresponding value of the sequence $x$. There are at least $\sum_{\alpha<\tau} |X_\alpha-\{x_\alpha\}|$ and no more than $\left(\sum_{\alpha<\tau} |X_\alpha|\right)^{<\omega}$ ways of doing this. Since $\tau$ is infinite and the $X_\alpha$'s all have two or more elements, these two bounds are equal to $\sum_{\alpha<\tau} |X_\alpha| = |\tau|\cdot\kappa$.

share|cite|improve this answer
why does every equivalence class has size $\sum_{\alpha < \tau} |X_\alpha|$? – Martin Brandenburg Jan 9 '10 at 11:09
I've clarified that fact in the end note. – François G. Dorais Jan 9 '10 at 14:17

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.