Not signed in (Sign In)

Start a new discussion

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

  • Sign in using OpenID

Discussion Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorUrs
    • CommentTimeJan 24th 2018
    • (edited Jan 24th 2018)

    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?

    • CommentRowNumber2.
    • CommentAuthorfwaaldijk
    • CommentTimeJan 24th 2018
    • (edited Jan 24th 2018)

    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.

    • CommentRowNumber3.
    • CommentAuthorJonasFrey
    • CommentTimeJan 24th 2018
    • (edited Jan 24th 2018)

    The nlab entry defines countable constructively as

    SS is countable if there exists a surjection from a decidable subset of N\mathbf{N} to SS

    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.

    • CommentRowNumber4.
    • CommentAuthorUrs
    • CommentTimeJan 25th 2018

    Thanks. If you think there is room to clarify any remaining subtlety in the entry, please consider doing so.

    • CommentRowNumber5.
    • CommentAuthorfwaaldijk
    • CommentTimeJan 25th 2018
    • (edited Jan 25th 2018)

    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}\{-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.

    • CommentRowNumber6.
    • CommentAuthorfwaaldijk
    • CommentTimeJan 25th 2018

    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}\{-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}\{-1\}\bigcup\,D, put f(-1)=-1, then h=f\circg is an enumeration of {1}\{-1\}\bigcup\,S.
    <- let f be an enumeration of {1}\{-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’.

    • CommentRowNumber7.
    • CommentAuthorfwaaldijk
    • CommentTimeJan 25th 2018
    • (edited Jan 25th 2018)

    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.

    • CommentRowNumber8.
    • CommentAuthorMike Shulman
    • CommentTimeJan 25th 2018

    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?

Add your comments
  • Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
  • To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

  • (Help)