# How to prove this function as onto?

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.

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