1
$\begingroup$

After studying the axiom of dependent choice, I tried to think of a possible generalization of the axiom that would work in a similar way on infinite uncountable sets: by replacing the binary relation with a general set membership relation over ordinal-indexed elements, I finally obtained the axiom below.

Remark: in order to make the axiom easier to read, I use the notation $(\underbrace{y_0, y_1, \dots}_{\alpha})$ to denote a map of elements indexed over an ordinal $\alpha$.

Generalized Axiom of Dependent Choice: given a set $X$, an element $x_0\in X$, a limit ordinal $\beta$, and a set $R$ containing elements of $X$ indexed over any $\alpha\in\beta$, suppose that the following two relations hold:
$ (a)\quad \forall \alpha\in\beta\,:\,(\underbrace{y_0, y_1, \dots}_{\alpha})\in R\,\,\Rightarrow\,\,\exists z\in X : (\underbrace{y_0, y_1, \dots, z}_{\alpha+1})\in R $
$(b)\quad$ if $\sigma$ is a sequence of elements of $X$ indexed by a limit ordinal $\gamma\in\beta$ such that each initial segment of $\sigma$ is an element of $R$, then $\sigma$ is an element of $R$.
Then there exists a function $f\,:\,\beta\,\mapsto\,X$ s.t. $f(0)=x_0$ and $$ \forall\alpha\in\beta\,:\,(\underbrace{f(0), f(1), \dots}_{\alpha})\in R $$

Do you think this is a valid and sound generalization? I found simple proofs of the following facts:

  1. if $\beta=\omega$ (i.e. the first infinite ordinal), then the generalized version is equivalent to the axiom of dependent choice with fixed first element.

  2. the generalized axiom of dependent choice implies the axiom of choice on the ordinals (although it is not clear if they are also equivalent)

  3. although inherently non-constructive, the generalized axiom hints to a 'method' for building the function $f\,:\,\beta\,\mapsto\,X$: choose $x_0$ as the first element, then randomly select the following elements $x_1, x_2,\dots$ in such a way that the sequence $(x_0,x_1,x_2,\dots)$ is still in $R$. This seems to be an intuitive process

  4. if we replace the condition $\cdots\Rightarrow\,\,\exists z\in X\cdots$ with the condition $\cdots\Rightarrow\,\,\exists ! z\in X\cdots$ (where the existing element $z\in X$ is also unique) then the function $f\,:\,\beta\,\mapsto\,X$ is provably unique. Although the changed version may seem to be provable in ZF, it is not a consequence of the axiom schema of replacement, nor it is definable via transfinite recursion - in other words, I suspect it is independent of ZF.

I would like to receive some feedback from other logicians: does this look like a valid generalization? Do you think it may be worth of a publication, and in case, in which journal?

Please share your thoughts about this, thank you in advance and have a great day!

Kind regards,
Gianluca Calcagni

$\endgroup$

2 Answers 2

1
$\begingroup$

The axiom you propose is inconsistent: take $\beta=\omega2$, and consider the set $R(\langle y_\eta\rangle_{\eta<\alpha})\iff \alpha<\omega$. Then certainly $R(\langle x_0\rangle)$ (regardless of what $x_0$ is), and $R(\langle y_0, y_1, . . . \rangle)$ implies $R(\langle y_0, y_1, . . . , z\rangle)$ (since appending an additional term to a finite string yields a finite string).

The problem is that the property $R$ above is sensitive to the "gap" between the finite ordinals and the infinite ones; in general, this is why Dependent Choice is defined as it is.

$\endgroup$
1
  • $\begingroup$ Thanks Noah, you indeed pointed out an inconsistency in the "axiom". It seems to me that the issue is due to the fact that the set $R$ has no relation with the ordinal $\beta$; moreover, the axiom does not take care of the limit ordinals. I added a second condition in the original formulation, that would make it (at least) consistent: I will check again if the new formulation does imply the axiom of choice, although it may not be the case. $\endgroup$ Aug 9, 2015 at 15:56
0
$\begingroup$

Noah gave a nice example why this generalization does not work. But there is in fact a generalization of $\sf DC$ to larger [$\aleph$] cardinals, due to Azriel Levy.

$\sf DC_\kappa$ is the statement that, whenever $S$ is a non-empty set, and $R$ is a relation on $S^{<\kappa}\times S$ with domain $S^{<\kappa}$, then there is a function $f\colon\kappa\to S$ such that $f\restriction\alpha\mathrel{R}f(\alpha)$ for all $\alpha<\kappa$.

Namely, if we have a relation $R$ such that for every $\alpha<\kappa$ and every $f\colon\alpha\to S$, there is some $z\in S$ such that $f\mathrel{R}z$, then there is a function from $\kappa$ which satisfies the wanted conclusion.

As a side note, this is equivalent to saying that every $\kappa$-closed tree without leaves has a branch of length $\kappa$; and that Zorn's lemma holds for chains of order type $<\kappa$ (namely, if $P$ is a partial where every chain of order type $<\kappa$ has an upper bound, then $P$ has a maximal element).

Let me finish by saying that this sort of gap is the reason that these two proofs cannot be generalized immediately to accommodate $\sf DC_\kappa$ for uncountable $\kappa$:

  1. If for every ordinal $\alpha$, $\sf AC_\alpha$ holds, then $\sf DC$ holds.
  2. If $M$ is a structure for a finite language, then $M$ has an elementary submodel of size $\leq\kappa$ if and only if $\sf DC+AC_\kappa$.

Both proofs work because for $\kappa=\aleph_0$ we can readily approximate things with finite steps, but we cannot bridge the obvious gap of limit ordinals.

$\endgroup$
2
  • $\begingroup$ Thank you Asaf, I was not aware of the generalization of Azriel Levy. I like the way the relation $R$ was extended, it is simple and it makes sense. I see that there was quite some work on this topic, do you know any paper or any book I can read to find out more about it? Thanks in advance! $\endgroup$ Aug 9, 2015 at 16:03
  • $\begingroup$ The generalization goes back to the late 1950s or early 1960s. I asked him once (he was in the audience when I gave a talk related to this), but I don't recall his exact reply. I think he didn't remember the exact year. $\endgroup$
    – Asaf Karagila
    Aug 9, 2015 at 16:06

You must log in to answer this question.

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