-4
$\begingroup$

Nested Selection: For every infinite set $G$ of pairwise disjoint infinite sets such that any two distinct elements $x,y$ of $G$ either "$y$ is a set of proper supersets of elements of $x$ and each element of $x$ has a proper superset of it in $y$" or "$x$ is a set of proper supersets of elements of $y$ and each element of $y$ has a proper superset of it in $x$"; there exists a set $cG$ that is a choice set on $G$ (i.e. $cG$ is a subset of $\bigcup G$ that has exactly one element from each element of $G$, among its elements) and such that for any two elements $a,b$ of $cG$ we have $a$ subset of $b$ or $b$ subset of $a$.

Is Nested selection equivalent to $AC$?

The formal capture is a little bit messy. It is:

$\forall G: \operatorname {infinite} (G) \land \forall h \in G (\operatorname {infinite}(h)) \land \\ \forall k,l \in G (k \neq l \to k \cap l = \emptyset) \land \\ \forall x,y \in G (\forall z \in y [x] \exists u \in x [y] (z \supsetneq u) \land \\ \forall v \in x[y] \exists w \in y[x] (w \supsetneq v) ) \\ \implies \\ \exists cG: cG \subseteq \bigcup G \land \\\forall g \in G \exists! m (m \in g \land m \in cG) \land \\\forall a,b \in cG: a \subseteq b \lor b \subseteq a$

If the above nested selection is too particular theme to pace with Choice.Then is the following general form equivalent to choice?

Define $\begin{align} Y \text { is } \Phi\text{-image of } X \iff &\forall a \in X \exists b \in Y: \Phi(a,b) \land \\ &\forall b \in Y \exists a \in X: \Phi(a,b)\end{align}$

General Nested Selection: If $\Phi$ is a transitive asymmetric binary relation, then if $G$ is an infinite set of pairwise disjoint infinite sets such that every two distinct sets $X,Y \in G$ either $ Y \text { is } \Phi\text{-image of } X $ or $ X \text { is } \Phi\text{-image of } Y$; then there exists a choice set $C$ on $G$ such that for any two distinct elements $a,b \in C$ either $ \Phi(a,b)$ or $\Phi(b,a)$.

By $C$ being a choice set on $G$ it means that $C \subseteq \bigcup G$ and $C$ shares exactly one element with each element of $G$.

$\endgroup$
16
  • 1
    $\begingroup$ Nested selection is false. If $G$ is a set of $\subseteq$-comparable sets, then there is no choice set $cG$ because if $x,y \in cG$ and $x \in A \in G$, $y \in B \in G$, then either $x,y \in A$ or $x,y \in B$ since either $A \subseteq B$ or $B \subseteq A$. $\endgroup$ Commented Feb 18, 2023 at 10:36
  • 1
    $\begingroup$ @MonroeEskew, $G$ must have all its elements being pairwise disjoint, I missed putting that. Thanks! $\endgroup$ Commented Feb 18, 2023 at 11:01
  • 1
    $\begingroup$ I don't understand your definition. Please clarify what you mean by "$y$ is a proper supersets of elements of $x$". Do you mean that for some $z \in x$, $y \supseteq x$? $\endgroup$ Commented Feb 18, 2023 at 11:26
  • 1
    $\begingroup$ @MonroeEskew, you missed reading "set", "$y$ is a "set" of proper supersets of elements of $x$". It means every element of $y$ is a proper superset of an element of $x$ and every element of $x$ has some proper superset of it in $y$. $\endgroup$ Commented Feb 18, 2023 at 11:30
  • 1
    $\begingroup$ @ZuhairAl-Johar: If that’s what you mean, then the phrasing is very misleading! I would have understood “$y$ is a set of proper supersets of elements of $x$” to mean “for each $z \in y$, there’s some $u \in x$ such that $z \supsetneq u$”, or possibly with a different order of quantification; but generally “$y$ is a set of [somethings]” is always only claiming something about the elements of $y$ — it really can’t be taken to include something like the second half of what you say you mean by it, “every element of $x$ has some proper superset of it in $y$”. $\endgroup$ Commented Feb 18, 2023 at 17:57

1 Answer 1

3
$\begingroup$

For a counterexample to Nested Selection, construct sets $A_\alpha\subseteq\omega$ ($\alpha\lt\omega_1$) so that, for $\alpha\lt\beta\lt\omega_1$, we have $|A_\alpha\setminus A_\beta|\lt\aleph_0=|A_\beta\setminus A_\alpha|$. Let $\mathcal S_\alpha=\{X\subseteq\omega:|X\triangle A_\alpha|\lt\aleph_0\}$ and let $G=\{\mathcal S_\alpha:\alpha\lt\omega_1\}$. A choice set for $G$ which was totally ordered by inclusion would be a chain of length $\omega_1$ in $\mathcal P(\omega)$, which doesn't exist.

P.S. To construct the sets $A_\alpha$, first partition $\omega$ into infinitely many disjoint infinite sets $N_i$ ($i\lt\omega$), and then define $A_\alpha$ recursively for $\alpha\lt\omega_1$ so that $|A_\alpha\cap N_i|\lt\aleph_0$ for each $i\lt\omega$ and $|A_\beta\setminus A_\alpha|\lt\aleph_0=|A_\alpha\setminus A_\beta|$ for each $\beta\lt\alpha$.

$\endgroup$
2
  • $\begingroup$ are the $\mathcal S_\alpha$ sets pairwise disjoint? $\endgroup$ Commented Feb 19, 2023 at 15:22
  • $\begingroup$ Yes, since $A_\alpha\triangle A_\beta$ is infinite when $\alpha\ne\beta$. $\endgroup$
    – bof
    Commented Feb 19, 2023 at 17:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .