-2
$\begingroup$

Let $\phi$ be a formula defining an equivalence relation.

Definitions:

  • The $\phi$-cardinality of a set $X$ be the cardinality of $X/\phi$. That is, the cardinality of the set of all equivalence classes of elements of $X$ under equivalence relation $\phi$.
  • A set is $\phi$-discriminative if and only if no two distinct elements of it fulfill $\phi$.

Discriminative Choice: For any family $F$ of pairwise disjoint nonempty sets, if the cardinality of $F$ is smaller than or equal to the $\phi$-cardinality of each of its elements, then there is a $\phi$-discriminative set $X$ that shares exactly one element with each element of $F$.

Is discriminative choice provable in $\sf ZFC$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Yes. Enumerate $F$ as $\langle F_\alpha : \alpha<\kappa\rangle$, where $\kappa$ is a cardinal. Inductively pick $x_\alpha \in F_\alpha$ such that $x_\alpha$ is not $\phi$-equivalent to any $x_\beta$, $\beta<\alpha$. This is possible because there are at least $\kappa$-many inequivalent elements of $F_\alpha$, so there are many equivalence classes that haven’t yet been touched.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Nice. The point is that $\kappa$ must actually be the cardinality of $F$. If $\kappa$ is not a cardinal, then this method fails. $\endgroup$
    – Zuhair Al-Johar
    Commented Jun 14 at 13:05
  • $\begingroup$ Is it equivalent to $\sf AC$ over $\sf ZF$? $\endgroup$
    – Zuhair Al-Johar
    Commented Jun 14 at 17:00
  • 2
    $\begingroup$ @ZuhairAl-Johar Yes. Let $\phi$ be the equality relation. For all collections $F$ of pairwise disjoint sets, replace each member $f \in F$ with $f \times F$ to meet the cardinality requirement. A choice function for this family gets a choice function for the original one. $\endgroup$
    – Monroe Eskew
    Commented Jun 15 at 4:12

Not the answer you're looking for? Browse other questions tagged or ask your own question.