Our proof that an undecidable language exists first shows that there are uncountably many infinite binary sequences (and hence languages), and that there are countably many finite strings (and hence TMs).
So, there are "strictly more" languages than TMs. However, the result doesn't follow immediately from this, so we need to do more.
To bridge this gap, our current materials re-do the entire diagonalization argument (this time with deciders vs the languages they decide). This works, but it is redundant and "overkill" -- for example, the uncountability of all languages is never actually used anywhere in the proof!
There is a more direct route that uses the key (un)countability facts as "black boxes," in a more abstract way:
There is an injection from decidable languages to TMs: map each decidable language to an arbitrary TM that decides it. (This is injective because the same machine can’t decide two different languages.)
Composing this with the injection from TMs to the naturals, we get an injection from decidable languages to naturals—so there are only countably many decidable langs.
Since there are uncountably many languages, there must be an undecidable one. (IOW: if “all langs=decidable langs”, then “all langs” would be countable.)
More broadly, this logic just shows that there’s no injection from an uncountable set to a countable one. (In particular, there’s no injection from the set of all languages to the set of TMs.)
Our proof that an undecidable language exists first shows that there are uncountably many infinite binary sequences (and hence languages), and that there are countably many finite strings (and hence TMs).
So, there are "strictly more" languages than TMs. However, the result doesn't follow immediately from this, so we need to do more.
To bridge this gap, our current materials re-do the entire diagonalization argument (this time with deciders vs the languages they decide). This works, but it is redundant and "overkill" -- for example, the uncountability of all languages is never actually used anywhere in the proof!
There is a more direct route that uses the key (un)countability facts as "black boxes," in a more abstract way:
More broadly, this logic just shows that there’s no injection from an uncountable set to a countable one. (In particular, there’s no injection from the set of all languages to the set of TMs.)