Return to Answer

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

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

Let me treat the case where the underlying set is infinite. These answers reveal that the question is likely to be much more interesting in the finite case, and so it should probably be regarded (and perhaps re-tagged) as a question of finite combinatorics.

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

Finally, let me mention that 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.

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

Let me treat the case where the underlying set is infinite. These answers reveal that the question is likely to be much more interesting in the finite case, and so it should probably be regarded (and perhaps re-tagged) as a question of finite combinatorics.

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

Finally, let me mention that 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 by Dr. Strangechoice that $\kappa$ can actually be strictly larger than $\alpha$! 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.

Let me treat the case where the underlying set is infinite. These answers reveal that the question is likely to be much more interesting in the finite case, and so it should probably be regarded (and perhaps re-tagged) as a question of finite combinatorics.

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

Finally, let me mention that 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.