Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Somebody sent me an email with the following comment on the entry countable set. I am not in position to react to this, maybe some expert here could reply. The sentence being quoted originates from revision 1 of the entry.
Forwarded message:
“We do have, however, that a countable set is either empty or inhabited, which is classically trivial but need not hold constructively for every set.”
(https://ncatlab.org/nlab/show/countable+set)
The set D={n\in N | 2n+6 is not the sum of two odd primes} is decidable, hence countable. However we cannot decide whether it is empty or inhabited. (We could decide it if we assumed LPO, for instance.)
Do you agree?
the way i learned these definitions is thus:
i) a set S is countable iff there is a bijection from N to S
ii) a set S is enumerable iff there is a surjection from N to S
that means that in my dictionary countable and enumerable sets are inhabited, and that decidable subsets of N need not be enumerable, but: every inhabited decidable subset of N is enumerable.
the example D={n\in N | 2n+6 is not the sum of two odd primes} is decidable, but so far not enumerable, in my book.
The nlab entry defines countable constructively as
$S$ is countable if there exists a surjection from a decidable subset of $\mathbf{N}$ to $S$
I agree that under this definition inhabitedness is not decidable, but the argument about the Goldbach conjecture is only a “weak counterexample” (as Brouwer calls it) in that existence of even non-Goldbach numbers > 4 might well be decidable. A proof of non-decidability of inhabitedness of decidable sets of integers can be given by showing that it implies decidability of the halting problem.
Thanks. If you think there is room to clarify any remaining subtlety in the entry, please consider doing so.
the current definition of ’countable’ in countable set is lacking, i feel, in the following way.
from time to time when trying to define an enumerable cover of a topological space, or an enumerable basis of opens, or an enumerable filtering set, one really wants to have a concrete enumeration, which one can start with, not depending on (the undecidable issue of) whether some decidable set is inhabited or not.
a simple trick that i have had occasion to use:
if S is a decidable subset of N, then $\{-1\}\bigcup\,$S is enumerable.
the current definition of ’countable’ in countable set does not differentiate between those sets that can be enumerated (which in all practical situations is a big plus) and those for which it is unknown.
less importantly, on the terminology side, the definition implies that many sets which in intuitionistic math are called subfinite, are countable according to nLab.
what’s in a name, it doesn’t matter much to me, but i do think that the concept of ’enumerability’ needs to be added.
if we let the definitions be
i’) a set S is countable iff there is a surjection from a decidable subset of N to S
ii) a set S is enumerable iff there is a surjection from N to S
then we have the following correspondence:
(${\ast}$) a set S is countable iff $\{-1\}\bigcup\,$S is enumerable.
proof:
-> let D be decidable, let f be a surjection from D to S, let g be an enumeration of $\{-1\}\bigcup\,$D, put f(-1)=-1, then h=f$\circ$g is an enumeration of $\{-1\}\bigcup\,$S.
<- let f be an enumeration of $\{-1\}\bigcup\,$S, then D = {n| f(n) in N} is decidable, and f restricted to D is a surjection from D to S.
this illustrates to me that enumerability is more useful than the current definition of ’countable’.
btw the above illustrates another terminological problem which mostly goes unnoticed: the definition of ‘decidable subset’. in classical complexity theory, a subset of N is decidable iff its membership function is a total recursive function. this is however not so in constructive mathematics, in constructive mathematics it suffices to have a total membership function (since functions are considered to be evaluable for any n).
this often leads to confusion, especially when giving talks…
for a constructive mathematician, given $\alpha$ in Baire space, the set S = {n | $\alpha$(n)=1} is decidable…
for defining ‘countable’ this terminological confusion can be prevented by using the proposed definition of enumerability and ($\ast$) above.
Re: #7, this may be part of why some people say “detachable” instead for a subset having the property that everything is either in it or not in it.
By analogy to “finite” and “finitely indexed”, I would be inclined to define a set as “countable” if it is in bijection with $\mathbb{N}$ and “countably indexed” if it admits a surjection from $\mathbb{N}$. I don’t remember ever seeing this business of detachable subsets of $\mathbb{N}$ appearing in the notion of countability. Toby, if you’re listening, do you have references for it?
1 to 8 of 8