View source for FA18:Lecture 9 countability

We will continue our discussion of [[cardinality]], defining [[countable]] and [[uncountable]] sets.  We will see proofs by [[diagonalization]].

At the tail end of lecture, we started a new topic, introducing some motivating examples of [[relation]]s.  These notes will be folded into the [[FA18:Lecture 10 relations|next lecture's notes]].


* Last semester: [[SP18: Lecture 9 Countability]]
* [[File:fa18-lec09-board.pdf]]

= Countability =

{{:Countable}}


= Examples of uncountable sets =

[[FA18:Lecture 8 cardinality|Last lecture]], we showed that <math>[[Example:cardinality of ℕ ∪ -1|ℕ ∪ \{-1\}]]</math>, <math>[[Example:cardinality of the integers|ℤ]]</math>, and <math>[[Example:cardinality of ℕ ⨯ ℕ|ℕ ⨯ ℕ]]</math> were all [[countable]].  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}}

= Relations =

At the tail end of lecture, we started a new topic, introducing some motivating examples of [[relation]]s.  These notes will be folded into the [[FA18:Lecture 10 relations|next lecture's notes]].