SP20:Lecture 9 prep

From CS2800 wiki

We will cover countability and diagonalization. Last semester, some of this material was covered in lecture 8 and the rest was in lecture 9.

Please come to lecture with the following definitions:

Definition: Finite
A set [math]X [/math] is finite if there exists a natural number [math]n [/math] such that [math]|X| \href{/cs2800/wiki/index.php/Equality_(cardinality)}{=} |\href{/cs2800/wiki/index.php/Enumerated_set}{\{1,2,\dots,n\}}| [/math].
Definition: Countable
A set [math]X [/math] is countable if [math]|X| \href{/cs2800/wiki/index.php/%E2%89%A4}{≤} |\href{/cs2800/wiki/index.php/%E2%84%95}{ℕ}| [/math].

You may also find it helpful to read the entry on Diagonalization and the proofs linked from that entry.