2 
People try to sit down when the music stops
Person sits in Chair 1, Person sits in Chair 2,
Person is left standing!
Clearly and unambiguously communicate computational ideas using appropriate formalism. Translate across levels of abstraction.
Defining important sets of numbers, e.g. set of integers, set of rational numbers
Defining functions using multiple representations
Classifying sets into: finite sets, countably infinite sets, uncountable sets
Using functions to compare cardinality of sets
Know, select and apply appropriate computing knowledge and problem-solving techniques. Reason about computation and systems. Use mathematical techniques to solve problems. Determine appropriate conceptual tools to apply to new situations. Know when tools do not apply and try different approaches. Critically analyze and evaluate candidate solutions.
Determining what evidence is required to establish that a quantified statement is true or false
Evaluating quantified statements about finite and infinite domains
Apply proof strategies, including direct proofs and proofs by contradiction, and determine whether a proposed argument is valid or not.
Tracing and/or modifying a proof by contradiction
Using proofs as knowledge discovery tools to decide whether a statement is true or false
Review quiz based on Week 7 class material (due Monday 02/23/2026)
Homework 4 due on Gradescope https://www.gradescope.com/ (Thursday 02/26/2026)
Review quiz based on Week 8 class material (due Monday 03/02/2026)
Test 2 Attempt 1 in the CBTF next week at your scheduled time.
Definition: A finite set is one whose distinct elements can be counted by a natural number.
Motivating question: when can we say one set is bigger than another?
Which is bigger?
The set \(\{1,2,3\}\) or the set \(\{0,1,2,3\}\)?
The set \(\{0, \pi, \sqrt{2} \}\) or the set \(\{\mathbb{N}, \mathbb{R}, \emptyset\}\)?
The set \(\mathbb{N}\) or the set \(\mathbb{R}^+\)?
Which of the sets above are finite? infinite?
Key idea for cardinality: Counting distinct elements is a way of labelling elements with natural numbers. This is a function! In general, functions let us associate elements of one set with those of another. If the association is “good", we get a correspondence between the elements of the subsets which can relate the sizes of the sets.
Analogy: Musical chairs
2
People try to sit down when the music stops
Person sits in Chair 1, Person sits in Chair 2,
Person is left standing!
What does this say about the number of chairs and the number of people?
Recall that a function is defined by its (1) domain, (2) codomain, and (3) rule assigning each element in the domain exactly one element in the codomain. The domain and codomain are nonempty sets. The rule can be depicted as a table, formula, English description, etc.
A function can fail to be well-defined if there is some domain element where the function rule doesn’t give a unique codomain element. For example, the function rule might lead to more than one potential image, or to an image outside of the codomain.
Example: \(f_A: \mathbb{R}^+ \to \mathbb{Q}\) with \(f_A(x) = x\) is not a well-defined function because
Example: \(f_B: \mathbb{Q} \to \mathbb{Z}\) with \(f_B\left(\frac{p}{q}\right) = p+q\) is not a well-defined function because
Example: \(f_C: \mathbb{Z} \to \mathbb{R}\) with \(f_C(x) = \frac{x}{|x|}\) is not a well-defined function because
Definition : A function \(f: D \to C\) is one-to-one (or injective) means for every \(a,b\) in the domain \(D\), if \(f(a) = f(b)\) then \(a=b\).
Formally, \(f: D \to C\) is one-to-one means \(\underline{\phantom{\forall a \in D \forall b \in D ~(f(a) = f(b) \to a = b)}}\).
Informally, a function being one-to-one means “no duplicate images”.
Definition: For nonempty sets \(A, B\), we say that the cardinality of \(A\) is no bigger than the cardinality of \(B\), and write \(|A| \leq |B|\), to mean there is a one-to-one function with domain \(A\) and codomain \(B\). Also, we define \(|\emptyset| \leq |B|\) for all sets \(B\).
In the analogy: The function \(sitter: \{ Chair1, Chair2\} \to \{ Person\sun, Person\smiley, Person\frownie \}\) given by \(sitter(Chair1) = Person\sun\), \(sitter(Chair2) = Person\smiley\), is one-to-one and witnesses that \[| \{ Chair1, Chair2\} | \leq |\{ Person\sun, Person\smiley, Person\frownie \}|\]
Definition: A function \(f: D \to C\) is onto (or surjective) means for every \(b\) in the codomain, there is an element \(a\) in the domain with \(f(a) = b\).
Formally, \(f: D \to C\) is onto means \(\underline{\phantom{\forall b \in C \exists a \in D ( f(a) = b)}}\).
Informally, a function being onto means “every potential image is an actual image”.
Definition: For nonempty sets \(A, B\), we say that the cardinality of \(A\) is no smaller than the cardinality of \(B\), and write \(|A| \geq |B|\), to mean there is an onto function with domain \(A\) and codomain \(B\). Also, we define \(|A| \geq |\emptyset|\) for all sets \(A\).
In the analogy: The function \(triedToSit: \{ Person\sun, Person\smiley, Person\frownie \} \to \{ Chair1, Chair2\}\) given by \(triedToSit(Person\sun) = Chair1\), \(triedToSit(Person\smiley) = Chair2\), \(triedToSit(Person\frownie) = Chair2\), is onto and witnesses that \[|\{ Person\sun, Person\smiley, Person\frownie \}| \geq | \{ Chair1, Chair2\} |\]
Definition : A function \(f: D \to C\) is a bijection means that it is both one-to-one and onto. The inverse of a bijection \(f: D \to C\) is the function \(g: C \to D\) such that \(g(b) = a\) iff \(f(a) = b\).
For nonempty sets \(A, B\) we say \[\begin{align*} |A| \leq |B| &\text{ means there is a one-to-one function with domain $A$, codomain $B$} \\ |A| \geq |B| &\text{ means there is an onto function with domain $A$, codomain $B$} \\ |A| = |B| &\text{ means there is a bijection with domain $A$, codomain $B$} \end{align*}\]
For all sets \(A\), we say \(|A| = |\emptyset|\), \(|\emptyset| = |A|\) if and only if \(A = \emptyset\).
Caution: we use familiar symbols to define cardinality, like \(| \phantom{\cdots} | \leq | \phantom{\cdots} |\) and \(| \phantom{\cdots} | \geq | \phantom{\cdots} |\) and \(| \phantom{\cdots} | = | \phantom{\cdots} |\), but the meaning of these symbols depends on context. We’ve seen that vertical lines can mean absolute value (for real numbers), divisibility (for integers), and now sizes (for sets).
Now we see that \(\leq\) and \(\geq\) can mean comparing numbers or comparing sizes of sets. When the sets being compared are finite, the definitions of \(|A| \leq |B|\) agree.
But, properties of numbers cannot be assumed when comparing cardinalities of infinite sets.
In a nutshell: cardinality of sets is defined via functions. This definition agrees with the usual notion of “size” for finite sets.
Properties of cardinality \[\begin{align*} &\forall A ~ (~ |A| = |A| ~)\\ &\forall A ~ \forall B ~(~ |A| = |B| ~\to ~ |B| = |A|~)\\ &\forall A ~ \forall B ~ \forall C~ (~ (|A| = |B| ~\wedge~ |B| = |C|) ~\to ~ |A| = |C|~) \end{align*}\]
Extra practice with proofs: Use the definitions of bijections to prove these properties.
Cantor-Schroder-Bernstein Theorem: For all nonempty sets, \[|A| = |B| \qquad\text{if and only if} \qquad (|A| \leq |B| ~\text{and}~ |B| \leq |A|) \qquad\text{if and only if} \qquad (|A| \geq |B| ~\text{and}~ |B| \geq |A|)\]
To prove \(|A| = |B|\), we can do any one of the following
Prove there exists a bijection \(f: A \to B\);
Prove there exists a bijection \(f: B \to A\);
Prove there exists two functions \(f_1: A \to B\), \(f_2: B \to A\) where each of \(f_1, f_2\) is one-to-one.
Prove there exists two functions \(f_1: A \to B\), \(f_2: B \to A\) where each of \(f_1, f_2\) is onto.
Definition: A set \(A\) is countably infinite means it is the same size as \(\mathbb{N}\).
Natural numbers \(\mathbb{N}\) List: \(0~~1~~2~~3~~4~~5~~6~~7~~8~~9~~10 \ldots\)
\(identity: \mathbb{N} \to \mathbb{N}\) with \(identity(n) = n\)
Claim: \(identity\) is a bijection. Proof: Ex. Corollary: \(| \mathbb{N} | = |\mathbb{N}|~\)
Positive integers \(\mathbb{Z}^+\) List: \(1~~2~~3~~4~~5~~6~~7~~8~~9~~10~~11\ldots\)
\(positives: \mathbb{N} \to \mathbb{Z}^+\) with \(positives(n) = n+1\)
Claim: \(positives\) is a bijection. Proof: Ex.Corollary: \(| \mathbb{N} | = |\mathbb{Z}^+|\)
Negative integers \(\mathbb{Z}^-\)List: \(-1\) \(-2\) \(-3\) \(-4\) \(-5\) \(-6\) \(-7\) \(-8\) \(-9\) \(-10\) \(-11\)…
\(negatives: \mathbb{N} \to \mathbb{Z}^-\) with \(negatives(n) = -n-1\)
Claim: \(negatives\) is a bijection. Corollary: \(| \mathbb{N} | = |\mathbb{Z}^-|\)
Proof: We need to show it is a well-defined function that is one-to-one and onto.
Well-defined?
Consider an arbitrary element of the domain, \(n \in \mathbb{N}\). We need to show it maps to exactly one element of \(\mathbb{Z}^-\).
One-to-one?
Consider arbitrary elements of the domain \(a, b \in \mathbb{N}\). We need to show that \[\left(~negatives(a) = negatives(b) ~\right) \to (a=b)\]
Onto?
Consider arbitrary element of the codomain \(b \in \mathbb{Z}^-\). We need witness in \(\mathbb{N}\) that maps to \(b\).
Integers \(\mathbb{Z}\) List: \(0~-1~~1~-2~~2~-3~~3~-4~~4~-5~~5\)…
\(f: \mathbb{Z} \to \mathbb{N}\) with \(f(x) = \begin{cases}2x &\text{if $x \geq 0$} \\-2x-1 &\text{if $x < 0$} \end{cases}\)
Claim: \(f\) is a bijection. Proof: Ex.Corollary: \(| \mathbb{Z} | = |\mathbb{N}|\)
More examples of countably infinite sets
Claim: \(S\) is countably infinite
Similarly: The set of all strings over a specific alphabet is countably infinite.
Bijection using alphabetical-ish ordering (first order by length, then alphabetically among strings of same length) of strands
Claim: \(L\) is countably infinite
2 \[\begin{align*} &list: \mathbb{N} \to L \\ &list(n) = (n, []) \\ & \end{align*}\]
\[\begin{align*} &toNum: L \to \mathbb{N} \\ &toNum([]) = 0 \\ &toNum( ~(n,l)~) = 2^n 3^{toNum}(l) \qquad \text{for $n \in \mathbb{N}$, $l \in L$} \end{align*}\]
Claim: \(|\mathbb{Z}^+| = |\mathbb{Q}|\)
One-to-one function from \(\mathbb{Z}^+\) to \(\mathbb{Q}\) is \(f_1: \mathbb{Z} \to \mathbb{Q}\) with \(f_1(n) = n\) for all \(n \in \mathbb{N}\).
\[\begin{align*} &f_2: \mathbb{Q} \to \mathbb{Z} \times \mathbb{Z} \\ &f_2(x) = \begin{cases} (0,1) & \text{if $x = 0$} \\ (p,q) & \text{if $x = \frac{p}{q}$,}\\ & \text{$gcd(p,q) = 1$, $q > 0$} \end{cases} \end{align*}\]
2 \[\begin{align*} &f_3: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}^+ \times \mathbb{Z}^+ \\ &f_3(~(x,y)~) = \begin{cases} (2x+2, 2y+2) & \text{if $x \geq 0, y \geq 0$} \\ (-2x-1, 2y+2) & \text{if $x < 0, y \geq 0$} \\ (2x+2, -2y+1) & \text{if $x \geq 0, y < 0$} \\ (-2x-1, -2y-1) & \text{if $x < 0, y < 0$} \\ \end{cases} \end{align*}\]
\[\begin{align*} &f_4: \mathbb{Z}^+ \times \mathbb{Z}^+ \to \mathbb{Z}^+ \\ &f_4(~(x,y)~) = 2^x 3^y \qquad \text{for $x,y \in \mathbb{Z}^+$} \end{align*}\]
A set \(A\) is finite means it is empty or it is the same size as \(\{ 1, \ldots, n \}\) for some \(n \in \mathbb{N}\).
A set \(A\) is countably infinite means it is the same size as \(\mathbb{N}\). Notice: all countably infinite sets are the same size as each other.
A set \(A\) is countable means it is either finite or countably infinite.
A set \(A\) is uncountable means it is not countable.
Lemmas about countable and uncountable sets
Lemma: If \(A\) is a subset of a countable set, then it’s countable.
Lemma: If \(A\) is a superset of an uncountable set, then it’s uncountable.
Lemma: If \(A\) and \(B\) are countable sets, then \(A \cup B\) is countable and \(A \cap B\) is countable.
Lemma: If \(A\) and \(B\) are countable sets, then \(A \times B\) is countable.
Generalize pairing ideas from \(\mathbb{Z}^+ \times \mathbb{Z}^+\) to \(\mathbb{Z}^+\)
Lemma: If \(A\) is a subset of \(B\) , to show that \(|A| = |B|\), it’s enough to give one-to-one function from \(B\) to \(A\) or an onto function from \(A\) to \(B\).
Recall: When \(U\) is a set, \(\mathcal{P}(U) = \{ X \mid X \subseteq U\}\)
Key idea: For finite sets, the power set of a set has strictly greater size than the set itself. Does this extend to infinite sets?
Definition: For two sets \(A, B\), we use the notation \(|A| < |B|\) to denote \((~|A| \leq |B| ~) \land \lnot (~|A| = |B|)\).
\[\begin{alignat*} {4} &\emptyset = \{ \} \qquad &&\mathcal{P}(\emptyset) = \{ \emptyset \} \qquad &&|\emptyset| < |\mathcal{P}(\emptyset)| \\ &\{1 \} \qquad &&\mathcal{P}(\{1\}) = \{ \emptyset, \{1\} \} \qquad &&|\{1\}| < |\mathcal{P}(\{1\})| \\ &\{1,2 \} \qquad &&\mathcal{P}(\{1,2\}) = \{ \emptyset, \{1\}, \{2\}, \{1,2\} \} \qquad &&|\{1,2\}| < |\mathcal{P}(\{1,2\})| \\ \end{alignat*}\]
\(\mathbb{N}\) and its power set
Example elements of \(\mathbb{N}\)
Example elements of \(\mathcal{P}(\mathbb{N})\)
Claim: \(| \mathbb{N} | \leq |\mathcal{P} ( \mathbb{N} ) |\)
Claim: There is an uncountable set. Example: \(\underline{\phantom{~~~\mathcal{P}(\mathbb{N})~~~}}\)
Proof: By definition of countable, since \(\underline{\phantom{~~~\mathcal{P}(\mathbb{N})~~~}}\) is not finite, to show is \(|\mathbb{N}| \neq |\mathcal{P}(\mathbb{N})|\) .
Rewriting using the definition of cardinality, to show is
Towards a proof by universal generalization, consider an arbitrary function \(f: \mathbb{N} \to\mathcal{P}(\mathbb{N})\).
To show: \(f\) is not a bijection. It’s enough to show that \(f\) is not onto.
Rewriting using the definition of onto, to show: \[\neg \forall B \in \mathcal{P}(\mathbb{N}) ~\exists a \in \mathbb{N} ~(~f(a) = B~)\] . By logical equivalence, we can write this as an existential statement: \[\underline{\phantom{\qquad\qquad\exists B \in \mathcal{P}(\mathbb{N}) ~\forall a \in \mathbb{N} ~(~f(a) \neq B~)\qquad\qquad}}\] In search of a witness, define the following collection of nonnegative integers: \[D_f = \{ n \in \mathbb{N} ~\mid~ n \notin f(n) \}\] . By definition of power set, since all elements of \(D_f\) are in \(\mathbb{N}\), \(D_f \in \mathcal{P}(\mathbb{N})\). It’s enough to prove the following Lemma:
Lemma: \(\forall a \in \mathbb{N} ~(~f(a) \neq D_f~)\).
Proof of lemma:
By the Lemma, we have proved that \(f\) is not onto, and since \(f\) was arbitrary, there are no onto functions from \(\mathbb{N}\) to \(\mathcal{P}(\mathbb{N})\). QED
Where does \(D_f\) come from? The idea is to build a set that would “disagree" with each of the images of \(f\) about some element.
| \(n \in \mathbb{N}\) | \(f(n) = X_n\) | Is \(0 \in X_n\)? | Is \(1 \in X_n\)? | Is \(2 \in X_n\)? | Is \(3 \in X_n\)? | Is \(4 \in X_n\)? | … | Is \(n \in D_f\)? |
|---|---|---|---|---|---|---|---|---|
| \(0\) | \(f(0) = X_0\) | Y / N | Y / N | Y / N | Y / N | Y / N | … | N / Y |
| \(1\) | \(f(1) = X_1\) | Y / N | Y / N | Y / N | Y / N | Y / N | … | N / Y |
| \(2\) | \(f(2) = X_2\) | Y / N | Y / N | Y / N | Y / N | Y / N | … | N / Y |
| \(3\) | \(f(3) = X_3\) | Y / N | Y / N | Y / N | Y / N | Y / N | … | N / Y |
| \(4\) | \(f(4) = X_4\) | Y / N | Y / N | Y / N | Y / N | Y / N | … | N / Y |
| ⋮ |
Comparing \(\mathbb{Q}\) and \(\mathbb{R}\)
Both \(\mathbb{Q}\) and \(\mathbb{R}\) have no greatest element.
Both \(\mathbb{Q}\) and \(\mathbb{R}\) have no least element.
The quantified statement \[\forall x \forall y (x < y \to \exists z ( x < z < y) )\] is true about both \(\mathbb{Q}\) and \(\mathbb{R}\).
Both \(\mathbb{Q}\) and \(\mathbb{R}\) are infinite. But, \(\mathbb{Q}\) is countably infinite whereas
\(\mathbb{R}\) is uncountable.
The set of real numbers
\(\mathbb{Z} \subsetneq \mathbb{Q} \subsetneq \mathbb{R}\)
Order axioms (Rosen Appendix 1):
| Reflexivity | \(\forall a \in \mathbb{R} (a \leq a)\) |
| Antisymmetry | \(\forall a \in \mathbb{R}~\forall b \in \mathbb{R}~(~(a \leq b~ \wedge ~b \leq a) \to (a=b)~)\) |
| Transitivity | \(\forall a \in \mathbb{R}~\forall b \in \mathbb{R}~\forall c \in \mathbb{R}~ (~(a \leq b \wedge b \leq c) ~\to ~(a \leq c)~)\) |
| Trichotomy | \(\forall a \in \mathbb{R}~\forall b \in \mathbb{R}~ ( ~(a=b ~\vee~ b > a ~\vee~ a < b)\) |
Completeness axioms (Rosen Appendix 1):
| Least upper bound | Every nonempty set of real numbers that is bounded above has a least upper bound |
| Nested intervals | For each sequence of intervals \([a_n , b_n]\) where, for each \(n\), \(a_n < a_{n+1} < b_{n+1} < b_n\), there is at least one real number \(x\) such that, for all \(n\), \(a_n \leq x \leq b_n\). |
Each real number \(r \in \mathbb{R}\) is described by a function to give better and better approximations \[x_r: \mathbb{Z}^+ \to \{0,1\} \qquad \text{where $x_r(n ) = n^{th} $ bit in binary expansion of $r$}\]
| \(r\) | Binary expansion | \(x_r\) |
|---|---|---|
| \(0.1\) | \(0.00011001 \ldots\) | \(x_{0.1}(n) = \begin{cases} 0&\text{if $n > 1$ and $(n~\text{\bf mod}~4) =2$} \\ 0&\text{if $n=1$ or if $n > 1$ and $(n~\text{\bf mod}~4) =3$} \\1&\text{if $n > 1$ and $(n~\text{\bf mod}~4) =0$} \\ 1&\text{if $n > 1$ and $(n~\text{\bf mod}~4) =1$} \end{cases}\) |
| \(\sqrt{2} - 1 = 0.4142135 \ldots\) | \(0.01101010\ldots\) | Use linear approximations (tangent lines from calculus) to get algorithm for bounding error of successive operations. Define \(x_{\sqrt{2}-1}(n)\) to be \(n^{th}\) bit in approximation that has error less than \(2^{-(n+1)}\). |
Claim: \(\{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\) is uncountable.
Approach 1: Mimic proof that \(\mathcal{P}(\mathbb{Z}^+)\) is uncountable.
Proof: By definition of countable, since \(\{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\) is not finite, to show is \(|\mathbb{N}| \neq |\{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}|\) .
To show is \(\forall f : \mathbb{Z}^+ \to \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \} ~~(f \text{ is not a bijection})~~\). Towards a proof by universal generalization, consider an arbitrary function \(f: \mathbb{Z}^+ \to \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\). To show: \(f\) is not a bijection. It’s enough to show that \(f\) is not onto. Rewriting using the definition of onto, to show: \[\exists x \in \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \} ~\forall a \in \mathbb{N} ~(~f(a) \neq x~)\] In search of a witness, define the following real number by defining its binary expansion \[d_f = 0.b_1 b_2 b_3 \cdots\] where \(b_i = 1-b_{ii}\) where \(b_{jk}\) is the coefficient of \(2^{-k}\) in the binary expansion of \(f(j)\). Since1 \(d_f \neq f(a)\) for any positive integer \(a\), \(f\) is not onto.
Approach 2: Nested closed interval property
To show \(f: \mathbb{N} \to \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\) is not onto. Strategy: Build a sequence of nested closed intervals that each avoid some \(f(n)\). Then the real number that is in all of the intervals can’t be \(f(n)\) for any \(n\). Hence, \(f\) is not onto.
Consider the function \(f: \mathbb{N} \to \{ r \in \mathbb{R} ~\mid~ 0 \leq r ~\wedge~ r \leq 1 \}\) with \(f(n) = \frac{1+\sin(n)}{2}\)
| \(n\) | \(f(n)\) | Interval that avoids \(f(n)\) |
|---|---|---|
| \(0\) | \(0.5\) | |
| \(1\) | \(0.920735\ldots\) | |
| \(2\) | \(0.954649\ldots\) | |
| \(3\) | \(0.570560\ldots\) | |
| \(4\) | \(0.121599\ldots\) | |
| ⋮ |
The power set of any countably infinite set is uncountable. For example: \[\mathcal{P}(\mathbb{N}), \mathcal{P}(\mathbb{Z^+}), \mathcal{P}(\mathbb{Z})\] are each uncountable.
The closed interval \(\{x \in \mathbb{R} ~|~ 0 \leq x \leq 1\}\), any other nonempty closed interval of real numbers whose endpoints are unequal, as well as the related intervals that exclude one or both of the endpoints.
The set of all real numbers \(\mathbb{R}\) is uncountable and the set of irrational real numbers \(\overline{\mathbb{Q}}\) is uncountable.
There’s a subtle imprecision in this part of the proof as presented, but it can be fixed.↩︎