In our first lecture together, we'll discuss the big questions we will answer in CS103, then explore the finite and the infinite through the world of set theory.
Readings
File Attachments
Lecture Recording
The complete archive of this quarter's lecture recordings is available on Canvas.
Lecture Prezi
Here is the Prezi with the logistics we discussed at the top of class today:
đź“ť Lecture Summary and Key Take-Aways
Key definitions and notation:
-
We defined a set as an unordered collection of distinct objects, which may be anything, including other sets. The objects that make up a set are called the elements of that set. We saw several examples of sets, along with the curly brace notation with comma-separated elements for denoting sets.
-
The power set of a set $S$ is the set of all subsets of $S$. We write the power set of set $S$ as $\wp(S)$. Formally, using set builder notation, $\wp(S) = \set{T\ |\ T \subseteq S}$.
-
The cardinality of a set is the number of elements it contains. If $S$ is a set, we denote its cardinality as $|S|$. We saw several examples in class. (See below for discussion of how we compare cardinalities of two sets.)
-
The cardinality of $\naturals$ is $\boldsymbol{\aleph_0}$ ("aleph-zero," "aleph-nought," or "aleph-null"). Wikipedia has some interesting details about $\aleph_0$, if you're interested.
Key set notation:
- $\in$ ("element of"); example: $t \in \set{q, w, e, r, t, y}$
- $\notin$ ("not an element of"); example: $z \notin \set{q, w, e, r, t, y}$
- $\subseteq$ ("subset of"); example: $\set{h, i} \subseteq \set{h, o, i, s, t}$
- $\wp(S)$ ("power set of $S$"); example: $\wp(\set{a, b}) = \set{\varnothing, \set{a}, \set{b}, \set{a, b}}$
- $|S|$ ("cardinality of $S$"); example: $|\set{w, a, t}| = 3$
Notation for three infinite sets we will refer to frequently:
- $\boldsymbol{\naturals} = \set{0, 1, 2, 3, …}$ is the set of all natural numbers. (In this class, assume 0 is a natural number.)
- $\boldsymbol{\integers} = \set{…, -2, -1, 0, 1, 2, …}$ is the set of all integers.
- $\boldsymbol{\reals}$ is the set of all real numbers.
Subsets and elements (key distinction):
- We say that $S \in T$ when, among the elements of $T$, one of them is exactly the object $S$.
- We say that $S \subseteq T$ when $S$ is a set and every element of $S$ is also an element of $T$. ($S$ has to be a set for the statement $S \subseteq T$ to be true.)
Observations:
- Every set is a subset of itself.
- The empty set is a subset of every set.
- $\varnothing \subset \varnothing$ ($\varnothing$ is a subset of itself), which follows from both (1) and (2) above (independently of one another).
- $\varnothing \notin \varnothing$ (the empty set is not an element of the empty set).
- $x \neq \set{x} $ (no object $x$ is equal to the set containing $x$).
Set builder notation:
- We saw several examples of set builder notation. Recall that not all sets are so frequently discussed that they warrant having their own dedicated symbol that has been agreed upon by mathematicians. Set builder notation gives us a way to precisely and concisely define a set without using "…" and hoping a human reader gleans our intended meaning.
- We talked about how to read set builder notation. You will want to be comfortable interpreting set definitions expressed in set builder notation, such as the ones given below. (See slide deck for more detail.)
Set builder notation examples:
- $\set{ n\ |\ n \in \naturals \text{ and } n \text{ is even} }$
- $\set{ n \in \naturals\ |\ n \text{ is even} }$
- $\set{ C\ |\ C \text{ is a set of US coins} }$
- $\set{ r \in \reals\ |\ r < 3 }$
- $\set{ n \in \naturals\ |\ n < 3}$
Key operators for combining sets:
- $\cup$ ("union")
- $\cap$ ("intersection")
- $-$ ("set difference")
- $\triangle$ ("symmetric difference")
Comparing the cardinalities of two sets:
-
If $S$ and $T$ are sets, we say that $|S| = |T|$ when there is a way of pairing off the elements of $S$ and $T$ without leaving anything uncovered.
-
If $S$ and $T$ are sets, we say $|S| < |T|$ when, no matter how you pair off the elements of $S$ and $T$, there's always at least one element of $T$ left uncovered.
-
Key take-away! Showing that a single attempted pairing-off of elements from two sets leaves something uncovered is not sufficient to conclude $|S| \neq |T|$. We saw an example of this in class when investigating whether $|\naturals| = |\integers|$.
-
Key take-away! We saw $|\naturals| = |\integers| = \aleph_0$. This is perhaps very surprising! To arrive at this conclusion, we relied upon the definition of cardinality equality given above. Understanding the pairing technique used is a key take-away from today's lecture.
Cantor's Theorem:
- Key theorem! Cantor's Theorem: If $S$ is a set, then $|S| \lt |\wp(S)|$.
- Stated differently: No matter how you pair off the elements of a set $S$ with the elements of $\wp(S)$, there will always be some element of $wp(S)$ left uncovered.
Proof of Cantor's Theorem:
- If the proof of Cantor's Theorem went a bit fast for you today,
DON'T PANIC!!
- While it's important to internalize the result of the proof – that $|S| \lt |\wp(S)|$ – we don't expect the proof itself to be immediately clear to everyone in the ultra-compressed time frame we had for discussing it today. We will come back to this proof again some other time. In the meantime, think of today's encounter with that proof as an exposure to the masterwork of one of the greatest artists of all time. Our understanding and appreciation of the proof will get richer as we delve more into the world of discrete mathematics.
Applying Cantor's Theorem to $\naturals$, we get:
- $|\naturals| < |\wp(\naturals)|$
Cantor's Theorem also gives us the following:
- $|\wp(\naturals)| < |\wp(\wp(\naturals))|$
- $|\wp(\wp(\naturals))| < |\wp(\wp(\wp(\naturals)))|$
- $|\wp(\wp(\wp(\naturals)))| < |\wp(\wp(\wp(\wp(\naturals))))|$
- … and so on.
The key take-aways here are:
- Not all infinite sets have the same size! For example, see explicitly from Cantor's Theorem that the cardinalities of the infinite sets $\naturals$ and $\wp(\naturals)$ are not equal!
- There is no biggest infinity!
- There are infinitely many infinities!
Key take-away! We used the results above to argue that there are more problems to solve than there are programs to solve them. (See the last several slides of today's slide deck.) That means there must be some problems computers cannot solve – a topic we will build up to and then explore in great depth as the quarter continues.