cardinal of a quotient space - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T04:45:01Z http://mathoverflow.net/feeds/question/30298 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/30298/cardinal-of-a-quotient-space cardinal of a quotient space Elemer E Rosinger 2010-07-02T12:09:14Z 2010-07-03T07:52:42Z <p>Let $X$ be a nonvoid set of cardinal $\alpha$. Let $\cong$ be an equivalence relation on $X$. Let $\beta$ be the cardinal of the set</p> <p>(1)&nbsp;&nbsp;&nbsp;&nbsp; <code>$D = \{ \, ( x, y ) \in X \times X ~|~ x \ncong y \, \}$</code></p> <p>Let any family $( x_i )_{i \in I}$, with $I$ a nonvoid index set, and $x_i \in X$, for $i \in I$. We call such a family a <em>chain</em>, iff</p> <p>(2)&nbsp;&nbsp;&nbsp;&nbsp; $x_i \ncong x_j,~~ i, j \in I,~ i \neq j$</p> <p>We denote by</p> <p>(3)&nbsp;&nbsp;&nbsp;&nbsp; $\kappa$</p> <p>the smallest cardinal which is at least as large as the cardinal of any index set $I$ of a chain (2).</p> <p>Clearly, we shall have</p> <p>(4)&nbsp;&nbsp;&nbsp;&nbsp; $car ( X / {\cong} ) = \kappa$</p> <p><strong>Problem 1</strong></p> <p>Find, in terms of the cardinals $\alpha, \beta$, the cardinal $\kappa$.</p> <p><strong>Problem 2</strong></p> <p>Given the cardinal $\alpha$, and given an upper bound</p> <p>(5)&nbsp;&nbsp;&nbsp;&nbsp; $\beta \leq \gamma$</p> <p>find, in terms of the cardinals $\alpha, \beta, \gamma$, an upper bound for the cardinal $\kappa$.</p> <p><strong>Problem 3</strong></p> <p>Given the cardinal $\alpha$, and given a lower bound </p> <p>(6)&nbsp;&nbsp;&nbsp;&nbsp; $\beta \geq \gamma$</p> <p>find, in terms of the cardinals $\alpha, \beta, \gamma$, a lower bound for the cardinal $\kappa$. </p> http://mathoverflow.net/questions/30298/cardinal-of-a-quotient-space/30308#30308 Answer by Joel David Hamkins for cardinal of a quotient space Joel David Hamkins 2010-07-02T13:39:44Z 2010-07-02T17:39:01Z <p>Let me first treat the case where the underlying set is infinite. </p> <p>In the infinite case, your cardinal $\beta$ is either $0$ or equal to $\alpha$, depending on whether all points are equivalent or not. The reason is that if the relation is not trivial, then every point is inequivalent to some other point, so $\alpha\leq\beta$, and conversely $\beta\leq\alpha\cdot\alpha=\alpha$ by infinite cardinal arithmetic.</p> <p>For question 1, the answer is therefore that $\kappa$ is not determined by $\alpha$ and $\beta$. As you observed, $\kappa$ is the number of classes, and the same infinite set of size $\alpha$ can be partitioned into any number $\kappa$ of classes, provided $1\leq\kappa\leq\alpha$.</p> <p>For question 2, when $\alpha$ is infinite, then since $\beta=\alpha$ (unless there is only one class, in which case $\beta=0$), the bound $\gamma$ is not very helpful. But the largest $\kappa$ can be is $\alpha$. (This is under AC; without AC, then it is possible that $\kappa$ could be strictly larger than $\alpha$, as I expain at the bottom.)</p> <p>Similarly, for question 3, the smallest $\kappa$ can be is $1$, when $\beta=0$, and otherwise, $\kappa=2$ is possible, since you can divide $\alpha$ into $2$ classes, each of size $\alpha$.</p> <p>In the infinite case, there are some interesting issues that arise with the Axiom of Choice in this question. Your observation that the quotient has size $\kappa$ seems to rely on AC, since the chains are essentially choice functions. More generally, it was observed in <a href="http://mathoverflow.net/questions/22927/why-worry-about-the-axiom-of-choice/22935#22935" rel="nofollow">a previous MO answer by Dr. Strangechoice</a> that $\kappa$ can actually be strictly larger than $\alpha$! That is, one can partition a set into strictly more classes than there are points! For example, consider the relation $E$ on the reals, where $xEy$ if $x=y$ or if both $x$ and $y$ code a well order on the natural numbers having the same order type. This is an equivalence relation on the reals, but it is consistent with ZF that there is no $\omega_1$-sequence of reals, and in this case there can be no injection from the $E$-classes into the reals, since this would provide such an $\omega_1$-sequence. But there is a converse injection, since we can injectively map reals to reals that don't code well-orders. So this is a situation where the number of equivalence classes is a strictly larger cardinality than the underlying set.</p> <hr> <p><em>Update.</em> In the finite case, I happened to observe that again $\kappa$ is not a function of $\alpha$ and $\beta$. To see this, let $\sim_1$ and $\sim_2$ be two relations on 6 points, the first partitioning it as $2+2+2$, with three classes, and the second partitiioning it as $3+1+1+1$, with four classes. In each case, we have $\alpha=6$. But unless I have made a counting mistake, it seems we also have $\beta=24$ in each case, since each equivalence relation adds 3 equivalent (unordered) pairs beyond the identity pairs, making for 12 equivalent pairs (a,b), and hence $\beta=36-12=24$ inequivalent pairs in each case. But the first relation has $\kappa=3$ and the second has $\kappa=4$; so $\kappa$ is not determined by $\alpha$ and $\beta$.</p>