The function $\ f$ : L→B, where $\ f(A)$ equals the characteristic sequence of A, is one-to-one and onto, and hence is a correspondence. Therefore, as B is uncountable, L is uncountable as well.

  • L be the set of all languages over alphabet Σ.
  • B be the set of all infinite binary sequences.
  • An infinite binary sequence is an unending sequence of 0s and 1s.
  • Let $\ Σ\ ^ ∗ $ = { $\ s_1, s_2, s_3, . . . $ }
  • Each language A ∈ L has a unique sequence in B. The ith bit of that sequence is a 1 if $\ s_i $ ∈ A and is a 0 if $\ s_i\not\in\ A$, which is called the characteristic sequence of A.

$\ f $ is one-one because if A1 and A2 are two languages from L then f(A1) = f(A2) iff A1 = A2 because characteristics sequences of A1 and A2 will differ only when A1 and A2 differ.

How should I prove that $\ f$ is onto ?

Came across this in COROLLARY 4.18 Some languages are not Turing-recognizable in Sipser's Theory of Computation Book.

  • $\begingroup$ Every infinite binary string defines some language $L$, just use the definition of the characteristic sequence to construct $L$. $\endgroup$ – diplodoc Sep 7 '19 at 11:20

Your Answer

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

Browse other questions tagged or ask your own question.