cardinality of product modulo direct sum - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T04:04:01Z http://mathoverflow.net/feeds/question/11188 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11188/cardinality-of-product-modulo-direct-sum cardinality of product modulo direct sum Martin Brandenburg 2010-01-08T20:58:20Z 2010-01-09T14:20:55Z <p>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$.</p> <p>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|$.</p> <p>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).</p> <p>the general case struggles me.</p> http://mathoverflow.net/questions/11188/cardinality-of-product-modulo-direct-sum/11204#11204 Answer by François G. Dorais for cardinality of product modulo direct sum François G. Dorais 2010-01-09T02:03:22Z 2010-01-09T14:20:55Z <p>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.)</p> <p>Arrange the sets $X_i$ in nondecreasing order of size in a wellordered sequence <code>$(X_\alpha)_{\alpha&lt;\tau}$</code>. 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.</p> <p>I will show that then $|X| = |X/{\sim}|$ where $X = \prod_{\alpha&lt;\tau} X_\alpha$.</p> <p>Let $\kappa = \sup_{\alpha&lt;\tau} |X_\alpha|$. Since each ${\sim}$-equivalence class has size $|\tau|\cdot\kappa$ (see note) we have </p> <p>$|X| \leq |X/{\sim}|\cdot|\tau|\cdot\kappa = \max(|X/{\sim}|,|\tau|,\kappa).$ </p> <p>Since $|X| \geq 2^{|\tau|} > |\tau|$, we conclude that either $|X/{\sim}| = |X|$ or $|X/{\sim}| \leq |X| \leq \kappa$.</p> <p>Since $\tau$ is a limit ordinal, the diagonal embedding $d:\kappa \to \prod_{\alpha&lt;\tau} |X_\alpha|$, where </p> <p><code>$d_\alpha(\xi) = \begin{cases} \xi &amp; when\ \xi &lt; |X_\alpha| \\ 0 &amp; otherwise,\end{cases}$</code></p> <p>shows that $\kappa \leq |X/{\sim}|$. So, in the case $|X/{\sim}| \leq |X| \leq \kappa$, we in fact have $|X/{\sim}| = |X| = \kappa$.</p> <p>Note: The elements ${\sim}$-equivalent to a given $x \in X$ are obtained by selecting finitely many new values from the sets <code>$X_\alpha-\{x_\alpha\}$</code> to replace the corresponding value of the sequence $x$. There are at least <code>$\sum_{\alpha&lt;\tau} |X_\alpha-\{x_\alpha\}|$</code> and no more than $\left(\sum_{\alpha&lt;\tau} |X_\alpha|\right)^{&lt;\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&lt;\tau} |X_\alpha| = |\tau|\cdot\kappa$.</p>