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

share|cite|improve this question
Professor Rosinger: just a few suggestions to improve legibility of your post. (a) You don't need the double backslashes () to break a line as in LaTeX (b) instead of using tildes (~) for spaces you can use \qquad to pad the equation away from the label. (c) To get bold face text, instead of using the LaTeX syntax as you did above, try surrounding the text with double asterisks ( * ). (Single asterisks make Italic text.) – Willie Wong Jul 2 '10 at 12:23
Also, I removed the mathematics tag and added large-cardinals and logic. They perhaps are not the best for this question, maybe someone more familiar with the subject can suggest others. – Willie Wong Jul 2 '10 at 12:29

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

share|cite|improve this answer

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.