10
$\begingroup$

Is the following statement provable in $\mathsf{ZF}$?

For every family $\mathcal{A}$ of sets, if $\mathcal{A}$ is closed under unions of chains and $\bigcup\mathcal{A}$ is well-orderable, then $\mathcal{A}$ has a $\subseteq$-maximal member.

$\endgroup$
2
  • $\begingroup$ @VilleSalo There might be no distinguished way to add the smallest individual, though. (E.g. if $x$ is the smallest thing addable to $X\in\mathcal{A}$, we might not have $X\cup\{x\}\in\mathcal{A}$.) $\endgroup$ Commented 9 hours ago
  • $\begingroup$ I guess I was showing that there is a set in A to which you cannot add a single element, but of course it's not the same. $\endgroup$
    – Ville Salo
    Commented 9 hours ago

2 Answers 2

10
$\begingroup$

No, this principle implies $\mathrm{DC}(\mathbb{R}).$ Suppose $T$ is a tree on $\mathbb{R}^{<\omega}$ with no leaves or branches. Let $\mathcal{A}$ consist of all $A \subset \omega \times \omega$ such that for some $\langle r_i: i<n \rangle \in T,$ $$A=\{(2i, j): i < n, j \in r_i\} \cup \{(2i+1, k): i<n, k \not \in r_i\}.$$

Then $\mathcal{A}$ has no infinite chains or maximal elements.

This generalizes to proving $\mathrm{DC}_{\kappa}(\mathcal{P}(\kappa))$ for all $\kappa,$ so, over a base theory of ZF - Foundation, this proves the pure axiom of choice, i.e. that the well-founded universe satisfies AC. In fact, the principle is equivalent to pure choice since it lives inside the well-founded universe.

$\endgroup$
1
  • 1
    $\begingroup$ I had a good hunch that this proof might go through. Thanks for confirming it! $\endgroup$
    – Asaf Karagila
    Commented 8 hours ago
6
$\begingroup$

Suppose that there is a Dedekind-finite set of reals, $A$. Enumerate the rational numbers as $\{q_n\mid n<\omega\}$, and for each $a\in A$ let $D_a\subseteq\omega$ be a recursively chosen subset such that $\{q_n\mid n\in D_a\}$ is a monotone sequence converging to $a$ from below in the interval $(a-1,a)$. Then $\{D_a\mid a\in A\}$ is an almost disjoint family.

Let $\cal A$ be all the finite unions of these $D_a$s, trivially $\bigcup\cal A$ is well-orderable. Easily, there is no maximal element in $\cal A$, since any finite union is missing out on "most" integers.

But I claim that it is closed under unions of chains. Simply because $\cal A$ is Dedekind-finite and well-founded under $\subseteq$. To see this, note that we can identify from any given $X\in\cal A$ which real numbers were involved in creating it, so there is a bijection between $X$ and $[A]^{<\omega}$, which itself is Dedekind-finite since $A$ can be linearly ordered.

$\endgroup$
2
  • $\begingroup$ Nice - I was working my way towards this, but you beat me to it! $\endgroup$ Commented 9 hours ago
  • $\begingroup$ I was going to let it be, because I have a deadline to meet this week, but I just couldn't. It feels good to not worry about this for now. $\endgroup$
    – Asaf Karagila
    Commented 9 hours ago

You must log in to answer this question.

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