cardinal of a quotient space

2010-07-02T12:09:14Z

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

(1) $ D = \{ \, ( x, y ) \in X \times X ~|~ x \ncong y \, \} $

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 chain, iff

(2) $ x_i \ncong x_j,~~ i, j \in I,~ i \neq j $

We denote by

(3) $ \kappa $

the smallest cardinal which is at least as large as the cardinal of any index set $I$ of a chain (2).

Clearly, we shall have

(4) $ car ( X / {\cong} ) = \kappa $

Problem 1

Find, in terms of the cardinals $\alpha, \beta$, the cardinal $\kappa$.

Problem 2

Given the cardinal $\alpha$, and given an upper bound

(5) $ \beta \leq \gamma $

find, in terms of the cardinals $\alpha, \beta, \gamma$, an upper bound for the cardinal $\kappa$.

Problem 3

Given the cardinal $\alpha$, and given a lower bound

(6) $ \beta \geq \gamma $

find, in terms of the cardinals $\alpha, \beta, \gamma$, a lower bound for the cardinal $\kappa$.

Answer by Joel David Hamkins for cardinal of a quotient space

2010-07-02T13:39:44Z

Let me first treat the case where the underlying set is infinite.

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.

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

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

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

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 previous MO answer by Dr. Strangechoice 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.

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

cardinal of a quotient space - MathOverflow

cardinal of a quotient space

Answer by Joel David Hamkins for cardinal of a quotient space