-2
$\begingroup$

The common belief is that every formal language is countable, based on the claim that "every subset of the natural numbers is countable." In the article https://homepage.divms.uiowa.edu/~hzhang/countable.pdf by Prof Hantao Zhang, a theorem was given as follows:

Let N denote the set of all natural numbers. L is decidable iff there exists a computable and increasing bijection f: N -> L. L is recognizable iff there exists a computable bijection f: N -> L.

This theorem implies that a recognizable but undecidable language cannot have an increasing bijection with N.

I didn't understand his proof and think that a well-defined bijection between a recognizable but undecidable language and N will help. The bijection constructed from the proof of "every subset of natural numbers is countable" seems not working because that bijection is increasing.

$\endgroup$
4
  • $\begingroup$ Thank you and the question was updated. $\endgroup$
    – Mofun
    Apr 2 at 22:57
  • 1
    $\begingroup$ I fail to find a decent source, but it seems long known that a language is decidable if and only if it can be enumerated in order. See a question on stack overflow Recursive vs recursively enumerable language in Turing Machines? $\endgroup$ Apr 3 at 0:32
  • $\begingroup$ Yes, “ a language is decidable if and only if it can be enumerated in order.” This ordered enumeration defines an increasing bijection. $\endgroup$
    – Mofun
    Apr 3 at 1:34
  • 1
    $\begingroup$ You should ignore the paper you linked to. It make ridiculous claims. $\endgroup$ Apr 3 at 23:11

2 Answers 2

6
$\begingroup$

You're getting confused and distracted by a fact that is not relevant to countability. Such a bijection definitely exists. It might or might not be computable, but that is irrelevant; it exists. Because it exists, the set is countable. Countability only requires that there exists a bijection, not that it be computable. Computability is not a requirement for countability. There are plenty of countable sets that are not computable.

The theorem does not imply that "a recognizable but undecidable language cannot have an increasing bijection with N". It can have an increasing bijection, though that bijection might not be computable.


Separately: the "paper" you link to has some serious problems. It does not appear to have been published anywhere, as far as I can see. It departs from standard accepted terminology in its usage of terms like "countable", and so has a high risk of leading to confusion, particularly if you are a bit new to the topic. I would recommend that you focus your studies on standard textbooks and resources, and do not use that paper to help you learn the subject.

$\endgroup$
5
  • $\begingroup$ If the bijection is not computable, then the formal language is not recognizable, as the theorem indicates. $\endgroup$
    – Mofun
    Apr 3 at 1:36
  • 3
    $\begingroup$ @Mofun, that's neither here nor there. The language is still countable. Recognizability is not a requirement to be countable. $\endgroup$
    – D.W.
    Apr 3 at 4:02
  • $\begingroup$ I agree that recognizability is not a requirement to be countable. My question is about a recognizable language, and by Zhang's theorem, this language has a computable bijection with N. $\endgroup$
    – Mofun
    Apr 3 at 12:48
  • $\begingroup$ On your first post, if your claim that "Such a bijection definitely exists" is based on "every subset of a countable set is countable", then the following is a circular argument: "Such a bijection definitely exists. It might or might not be computable, but that is irrelevant; it exists. Because it exists, the set is countable. " $\endgroup$
    – Mofun
    Apr 3 at 12:55
  • 2
    $\begingroup$ @Mofun, no, it's based on the fact that mathematicians have proven that such a bijection exists. Existence follows from the fact that every subset of a countable set is countable, or can be proven directly. If you'd like to know how that proof goes, I suggest you study standard textbooks that prove facts like "every subset of a countable set is countable". Such proofs are valid; there is nothing wrong with them, and they are not circular. Computability, recognizability, and decidability are irrelevant here -- I think you're getting confused by something tangential. $\endgroup$
    – D.W.
    Apr 3 at 16:34
1
$\begingroup$

If we consider some alphabet $\Sigma$ where $\Sigma$ is finite, then $\Sigma^*$ is countable, therefore since every language defined on that alphabet is subset of $\Sigma^*$, you get that every language defined on finite alphabet is countable. basic idea is that, first write down all strings of length 0 and order them lexicographically, then all strings of length 1 and order them lexicographically as well and next enumerate. for details check Corollary 4.18 in the book by Michael Sipser: for the details why subset of countable set is countable check the following answer.

P.S also if you specify in what part exactly you have problem with the proof, it will be easier to answer. also in "every formal language" do you mean set consisting of all formal languages, or countability of every formal language itself?

$\endgroup$
3
  • $\begingroup$ Thank you very much for the quick answer. Corollary 4.18 in the book by Michael Sipser states that some formal languages are unrecognizable. Zhang's article says that any unrecognizable language is not countable unless every bijection from this language to the set of natural numbers is computable. My question is: Do we have a well-defined bijection between an unrecognizable language and the set of natural numbers? $\endgroup$
    – Mofun
    Apr 2 at 19:29
  • $\begingroup$ since undecidable languages are also subset of $\Sigma^*$ there must exist bijection between them and natural numbers. $\endgroup$
    – math boy
    Apr 2 at 19:44
  • $\begingroup$ The original question was edited. The bijection from the proof of "a subset of natural numbers is countable" does not work because it is increasing. $\endgroup$
    – Mofun
    Apr 2 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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