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.

  • 1
    $\begingroup$ Your second and third paragraphs are contradictory. (I believe the latter a lot more.) $\endgroup$ – Reid Barton Jan 8 '10 at 21:40
  • 1
    $\begingroup$ 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! $\endgroup$ – Mariano Suárez-Álvarez Jan 8 '10 at 22:14

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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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