The n-Category Café

Well, apparently you can’t prove the existence of Lebesgue nonmeasurable sets with just DC, which also means things like Banach–Tarski are out. So maybe it’s only “pathological” results in analysis that need AC and not DC. Hmm, maybe I need to rethink my stance about intermediate forms of choice.

I think that Madeleine’s suggestion that DC might have become standard if it had been introduced before ZFC became entrenched is very plausible.

In the present context, to my taste the version of AC included in the ETCS axioms is the most natural-feeling one. Is there a similar formulation of DC that can be substituted in ETCS?

Okay, so no nonmeasurability from DC alone, which also means you can’t well-order $\mathbb{R}$. Of course, since DC is weaker than AC, you can’t prove that every vector space has a basis, and perhaps you can’t prove that every nontrivial vector space has nontrivial dual. But I’m still wondering what the most basic result is in non-functional analysis that can’t be proved with DC.

I’m sure Jonathan’s right that asking Asaf Karagila would be a way to find this out!

In the present context, to my taste the version of AC included in the ETCS axioms is the most natural-feeling one. Is there a similar formulation of DC that can be substituted in ETCS?

At this very instant, I don’t know any way of stating DC other than just stating it. But that’s a nice question. Sounds like a good one for me to think about on my walk back to the station this evening.

Here’s a statement equivalent to dependent choice and with an ETCS kind of flavour. It hasn’t got the simple appeal of “surjections split”, but maybe it’s a step in the right direction. Here it is:

For all sets and functions $p, q: X \to Y$ with $p$ surjective, and all $y \in Y$, there exists a function $f: \mathbb{N} \to X$ such that $p(f(0)) = y$ and $p f s = q f$.

Here $s: \mathbb{N} \to \mathbb{N}$ is the successor function. Another way to express the equation is $p(f(n + 1)) = q(f(n))$ for all $n \in \mathbb{N}$, where of course $n + 1$ means $s(n)$. And there’s a pentagonal commutative diagram for $p f s = q f$ that I’m not drawing here.

Let me call the statement above “DC2”, for reference.

DC2 looks rather like the natural numbers axiom. I think you could roll it and the natural numbers axiom into one, like this:

There exist a set $\mathbb{N}$, an element $0 \in \mathbb{N}$ and a function $s: \mathbb{N} \to \mathbb{N}$ with the following property: [DC2], and $f$ is unique if $p$ is invertible.

But this doesn’t seem very illuminating.

To show that DC implies DC2, define a relation $R$ on $X$ by $x R x' \iff q(x) = p(x')$, take some $x \in X$ such that $p(x) = y$, and turn the handle.

To show that DC2 implies DC, take a total relation $R$ on a set $Y$ and an element $y \in Y$. Define $p, q: R \to Y$ to be the two projection functions, sending a pair $(y, y')$ of $R$-related elements to $y$ and $y'$ respectively, and again, follow your nose.

I’m sure I’m reinventing the wheel.

Nice! And it’s a pleasingly simple exercise to prove DC2 from the natural numbers axiom and “surjections split”. Whereas I tend to find proofs of equivalent or weaker forms of AC from the traditional formulation to be annoyingly fiddly.

I woke up in the middle of the night and realized there’s a simpler way. The following statement — call it DC3 — is also equivalent to the axiom of dependent choice:

for all sets $X$, elements $a \in X$, and surjections $p: X \to X$, there exists a function $f: \mathbb{N} \to X$ such that $f(0) = a$ and $p(f(n + 1)) = f(n)$ for all $n \in \mathbb{N}$.

In other words, for any surjection from our set to itself and any given starting point $a$, there exists a backwards trajectory

$$\cdots \mapsto x_2 \mapsto x_1 \mapsto a.$$

DC implies DC3: given $X$, $a$ and $p$ as above, define a relation $R$ on $X$ by $x R y \iff x = p(y)$. Then $R$ is total as $p$ is surjective, and follow your nose.

DC3 implies DC: take a total relation $R$ on a set $Y$ and an element $b \in Y$. Let $X$ be the set of finite sequeces $(y_0, \ldots, y_n)$ in $Y$ such that $y_0 R y_1 R \ldots R y_n$, including the empty sequence $\varepsilon$. Define $p: X \to X$ by $p(y_0, \ldots, y_n, y_{n + 1}) = p(y_0, \ldots, y_n)$ for $n \geq 0$, and $p((y_0)) = p(\varepsilon) = \varepsilon$. Then $p$ is surjective as $R$ is total. Also, we have an element $(b)$ of $X$ (a sequence of length $1$). Applying DC3 gives a sequence

$$(b), (b, y_1), (b, y_1, y_2), (b, y_1, y_2, y_3), \ldots$$

of elements of $Y$, and then $b, y_1, y_2, \ldots$ is a sequence in $Y$ with $b R y_1 R y_2 R \ldots$, as required.

I like this! It feels like one can almost phrase it in terms of a universal property of a pointed set with a surjective endomorphism, with the natural numbers pointed by 0 and with the predecessor map (taking the predecessor of 0 to be 0). So the equation is $p(f(n)) = f(\mathrm{pred}(n))$ — but this highlights a small wrinkle: your $p$ doesn’t have $a$ as a fixed point! Perhaps it could be phrased in terms of a surjective endomorphism with a fixed point? The trick would be to convert an arbitrary surjective endomorphism of $X$ with a point $a\in X$ to an endo where $a$ is fixed, and which is still surjective.

In any case this version feels close to the version of DC that talks about how a “pruned” tree with $\omega$-many levels has a branch, that is, an injective “tree-function” from the linear tree $\mathbb{N}$. The “pruned” condition says that there are no finite branches.

The Wikipedia page confusingly mentions how a tree with a branch is non-well-founded, which I realised meant that the partial ordering is the reverse of the one I thought of, namely higher up a branch is lower in the partial order. In this respects it’s like taking a membership tree of a pure set.

Your $p$ is like taking the parent of a node in the tree, and the surjectivity means that the tree is pruned (there are no nodes that are the ‘end’ of a branch, with no children). And the element $a$ is like the root node, though of course it has no parent (compare the wrinkle noted above). Of course, it may well be that you have a pointed forest instead of a tree, where the point may occur anywhere, not necessarily at the root node. But you are getting a branch that grows up out of $a$, regardless of what is happening sideways from or below $a$. Needless to say, the proof on Wikipedia takes a different approach.

Perhaps this is how you thought of it in the first place?

Perhaps this is how you thought of it in the first place?

No, I was just trying to simplify my initial rather clumsy attempt (“DC2”) to ETCS-ify dependent choice.

While I’m commenting, I might as well record a slight variant of the version of dependent choice I stated above, DC3. To recap, DC3 says, a bit informally:

For any set $X$, element $a \in X$, and surjection $p: X \to X$, there exists an infinite backwards trajectory $\cdots \mapsto x_1 \mapsto x_0 = a$ ending at $a$.

The variant, which I guess I’m going to call DC4, says:

For any nonempty set $X$ and surjection $p: X \to X$, there exists an infinite backwards trajectory $\cdots \mapsto x_1 \mapsto x_0$.

Obviously DC3 implies DC4. The converse is proved by considering the set of finite backwards trajectories ending at $a$, together with the surjection that removes the first step of a trajectory.

DC4 is shorter, but it feels a bit show-offy, somehow. DC3 is the one I like best.

The authors of a recent preprint expressed dependent choice structurally in the following manner:

Given an $\mathbb{N}$-indexed family of sets $A_n$ and an $\mathbb{N}$-indexed family of surjections $f:A_{n + 1} \to A_n$, the projection function to $A_0$ from the sequential limit $\underset{\leftarrow}\lim A_n$ of the aforementioned diagram is a surjection.

Oh, I like it. Very nice.

I wouldn’t want to use this formulation of DC as an axiom, as it would require too much stuff to be set up beforehand. But it’s definitely a useful, quite concrete everyday principle.

Asking Asaf Karagila will get you a long way in understanding equivalences of various forms of choice.