View source for SP18:Lecture 9 Countability

[[Category:Functions]]

We used the [[cardinality]] definitions to define [[countability]]; we gave several examples of countable and uncountable sets.

* Reading: [[MCS]] 8.1
* Last semester: [http://www.cs.cornell.edu/courses/cs2800/2017fa/lectures/lec14-cardinality.html Cardinality] and [http://www.cs.cornell.edu/courses/cs2800/2017fa/lectures/lec15-uncountable.html Uncountability]
* [[File:lec09-board.pdf]]

= Countability =

{{:Countable}}

= Countable sets =

== ℕ ∪ {-1} ==

{{:Example:cardinality of ℕ ∪ -1}}

== Even naturals ==

{{Example: cardinality of evens}}

== Integers ==

{{:Example:cardinality of the integers}}

== ℕ ⨯ ℕ ==

{{:Example:cardinality of ℕ ⨯ ℕ}}

= Examples of uncountable sets =

At this point, you might suspect that all [[set]]s are [[countable]].  However,
this is not the case.

== Diagonalization ==

{{:Diagonalization}}

== The set of subsets of the natural numbers ==

{{:Proof:The power set of the naturals is uncountable}}

== The set of real numbers ==

{{:Proof:The set of reals is uncountable}}