I can't remember where, but I seem to remember hearing that if you present an algorithm in a proof, the algorithm must have at most countably iterations. Is this the case?

For instance, in showing the claim that every open set $O$ in $\mathbb R$ (in the Euclidean topology) is a disjoint union of open intervals, we can note first that $\cup_{x\in O}B_x=O$, where $B_x$ is some open ball containing $x$ and contained in $O$. Next, if $x\neq y$ and $B_x\cap B_y\neq\emptyset$, then $B_x\cup B_y=\biggr(\inf B_x\cup B_y,\sup B_x\cup B_y\biggr)$, so in the union, we can replace $B_x$ and $B_y$ with this new open interval. Since we can do this for every pair $x,y\in O$, the union can be written as a disjoint union.

But this last step takes possibly uncountably many iterations. Is the proof fine as is, or does this violate some rule of proof-writing?

Thanks in advance.

  • $\begingroup$ It's fine; you can iterate up to any ordinal if you want, for instance. That's how one proof of Zorn's lemma goes (from the axiom of choice). $\endgroup$ – Patrick Stevens Aug 23 '17 at 22:16

Your proof sketch is not valid, I'm afraid. It could probably be made precise using transfinite recursion, but that's overkill: If $O \subseteq \mathbb{R}$ is open just define $\mathcal{C}$ to be set of connected components of $O$ in the subspace topology.

These are disjoint by definition, and cover $O$. They are also open (as $\mathbb{R}$ is locally connected) and so each is an open interval or an open (unbounded) segment. No need for joining open balls in an "algorithmic" way. The set of components is also countable, as each must contains a (necessarily different) rational number.

To answer the main question: we can go beyond countably many steps with transfinite recursion, but you have to be precise, especially at limit steps. SUch proofs often abundantly use AC (which is often considered overkill); it will depend on the precise problem.

  • 2
    $\begingroup$ It's worth clarifying that transfinite recursion itself doesn't require choice at all; rather, we often need choice to be able to make transfinite recursion useful in a given setting (since this will often amount to providing a well-ordering of some set of objects involved, corresponding to the "requirements" the thing we're building needs to satisfy). $\endgroup$ – Noah Schweber Aug 23 '17 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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