CCHOICE and countably infinite versus countable

[jkingdon]

CCHOICE and countably infinite versus countable

[jkingdon]

My current assumption is that the existence of a choice function for any countable collection of inhabited sets requires more than countable choice. If I look at something like the definition of the Axiom of Countable Choice, AC_ω, in section 10.2 of [AczelRathjen] they only discuss an infinitely countable collection and the same is true of places like Lemma: 8.1.27 (a countably infinite collection of countable sets has a sequence of enumerations, given countable choice).

At least based on a browse through that work, it would seem like the question everyone is asking about is the union of a sequence of countable sets (that is, a countably infinite number of them), rather than the union of countably many countable sets.

[digama0]

But we are looking for a choice function on A, and given an element of A, there might be multiple natural numbers which F maps to that element and no way to choose one of them that I noticed.

Luckily, the natural numbers come with a canonical choice function: choose the minimal one. Any inhabited subset of natural numbers should have a minimum element (constructively), you take the intersection of all the ordinals considered as sets.

[jkingdon]

Any inhabited subset of natural numbers should have a minimum element (constructively),

You mean like https://us.metamath.org/ileuni/nnregexmid.html ?

[benjub]

Any inhabited subset of natural numbers should have a minimum element (constructively),

You mean like https://us.metamath.org/ileuni/nnregexmid.html ?

A way to formalize Mario's original claim that you do not need the axiom of choice or any variant is to assume that the subset of natural numbers has decidable membership: "An inhabited decidable subset of natural numbers has a minimum element."

[jkingdon]

A way to formalize Mario's original claim that you do not need the axiom of choice or any variant is to assume that the subset of natural numbers has decidable membership: "An inhabited decidable subset of natural numbers has a minimum element."

Oh, I think that works, using https://us.metamath.org/ileuni/ctssdc.html .

I've started in on this, and it is enough formalizing that it might take me a day or two to work this out, but at first glance it seems like it will work. Thanks for the suggestion.

Update: I don't think ctssdc helps the way I thought it would. Although the set s from that theorem is decidable, the set which wasn't decidable was the set of indexes which map to a particular element of A .

[digama0]

Yes, the theorem I was thinking of assumes that the set has decidable membership. In this case, that amounts to a requirement that A has decidable equality. If you don't have that, then I think you will not be able to prove the original claim. It might be better to have A index a collection of sets instead of being a collection of sets, since there are some examples where the indexing set has decidable equality even if the sets themselves don't.

[jkingdon]

See https://us.metamath.org/ileuni/cc3.html or https://us.metamath.org/ileuni/cc4.html for examples where the choice is on one set which is indexed by a second set, a countably infinite one. I'm going to consider cc3 and cc4 as sufficient solutions and close this issue, since they should make it possible to prove what you need to prove in this area.