Rationals are countable. Map each pair to a unique natural number.
Reals in are uncountable. Assume, for a contradiction that they are countable. Construct a real whose i’th digit is 0 if the i’th digit of the i’th number is odd and 1 otherwise. Then this number has some index t. The t’th digit of the number gives us a contradiction.
Finite strings are countable, infinite (even binary) strings are uncountable.
Diagonalization is the proof technique we used for showing sets are uncountable and languages are undecidable.
Here’s a different proof of the existence of an undecidable language.
For a binary string , let . In words, it is the shortest string including the description of a Turing machine and an input on which the TM produces the desired string .
Claim 1. For every integer , there is a string s.t. .
Define . , the language of incompressible strings is infinite.
Theorem. The language is undecidable.
Proof. Suppose is decidable. Then consider the following TM M:
On input an integer , M scans through each string of length and outputs the lexicographically first string that belongs to .
Claim 2. Let be the string output by M on input . Then . But . Contradiction for larger than some constant!
Therefore, our assumption is false and is undecidable.