A set is countable only when it can be described as a list (because a countable set can be count in a way that is 1-1 and onto). The set of rational numbers, Q, is countable because a 1-1 and onto function can be specified from N --> Q, where N is the set of natural number.
Then, a Cantor's example is showed for the uncountable sets:
"To show that the set of in nite decimals in [0; 1] was bigger
than the natural numbers, Cantor showed that any so-called list
of these numbers would always miss entries" (form slide w12)
A specification of a function is its behavior on every step.
Python functions are countable because every python function can be written in UTF-8, which is out of 256 characters. "Each string can be converted to a different number by treating each character as a digit in base 256. This gives us an onto function from N to the set of python programs".
Then, an introduction of induction is given.
First, we have an assumption for example: P(n) for all n
Then, we get the base statement: P(k) is true
Then, we prove the P(n) => P(n+1) for all n greater or equal to k
Then, we know that for all n greater or equal to k: P(n)
