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
Classifying sets into: finite sets, countably infinite sets, uncountable sets
Defining functions, predicates, and binary relations using multiple representations
Determining whether a given binary relation is symmetric, antisymmetric, reflexive, and/or transitive
Determining whether a given binary relation is an equivalence relation and/or a partial order
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.
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)
Homework 4 due Tuesday
Test 2 in the CBTF at your scheduled time! You will be required to show a physical photo identification in order to test. Electronic IDs and photos of IDs are not accepted. Additionally, you will only be allowed to bring your ID and a writing utensil into the testing room. You will have to store away all of your other belongings before entering the room. Please see the Triton Testing Center’s website for more details.
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.
The set of positive integers \(\mathbb{Z}^{+}\) is countably infinite.
The set of integers \(\mathbb{Z}\) is countably infinite and is a proper superset of \(\mathbb{Z}^{+}\). In fact, the set difference \[\mathbb{Z} \setminus \mathbb{Z}^{+} = \{ x \in \mathbb{Z} \mid x \notin \mathbb{Z}^+\} = \{ x \in \mathbb{Z} \mid x \leq 0 \}\] is countably infinite.
The set of rationals \(\mathbb{Q} = \left\{ \frac{p}{q} \mid p \in \mathbb{Z} \text{ and } q \in \mathbb{Z} \text{ and } q \neq 0 \right\}\) is countably infinite.
The set of real numbers \(\mathbb{R}\) is uncountable. In fact, 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 are each uncountable. The set of irrational numbers \(\overline{\mathbb{Q}} = \mathbb{R} - \mathbb{Q} = \{ x \in \mathbb{R} \mid x \notin \mathbb{Q} \}\) is uncountable.
We can classify any set as
Finite size. Fact: For each positive number \(n\), for any sets \(X\) and \(Y\) each size \(n\), there is a bijection between \(X\) and \(Y\).
Countably Infinite. Fact: for any countably infinite sets \(X\) and \(Y\), there is a bijection between \(X\) and \(Y\).
Uncountable. Examples: \(\mathcal{P}(\mathbb{N})\), the power set of any infinite set, the set of real numbers, any nonempty interval of real numbers. Fact: there are (many) examples of uncountable sets that do not have a bijection between them.
True or False? For all sets \(A\) and \(B\) where \(A \subseteq B\), if \(A\) is infinite then \(B\) is finite.
True or False? For all sets \(A\) and \(B\) where \(A \subseteq B\), if \(A\) is countable then \(B\) is countable.
True or False? For all sets \(A\) and \(B\) where \(A \subseteq B\), if \(B\) is infinite then \(A\) is finite.
True or False? For all sets \(A\) and \(B\) where \(A \subseteq B\), if \(B\) is uncountable then \(A\) is countable.
Definition: When \(A\) and \(B\) are sets, we say any subset of \(A \times B\) is a binary relation. A relation \(R\) can also be represented as
A function \(f_{TF} : A \times B \to \{T, F\}\) where, for \(a \in A\) and \(b \in B\), \(f_{TF}(~(a,b)~) = \begin{cases} T \qquad&\text{when } (a,b) \in R \\ F \qquad&\text{when } (a,b) \notin R \end{cases}\)
A function \(f_{\mathcal{P}} : A \to \mathcal{P}(B)\) where, for \(a \in A\), \(f_{\mathcal{P}}( a ) = \{ b \in B ~|~ (a,b) \in R \}\)
When \(A\) is a set, we say any subset of \(A \times A\) is a (binary) relation on \(A\).
For relation \(R\) on a set \(A\), we can represent this relation as a graph: a collection of nodes (vertices) and edges (arrows). The nodes of the graph are the elements of \(A\) and there is an edge from \(a\) to \(b\) exactly when \((a,b) \in R\).
Example: For \(A = \mathcal{P}(\mathbb{R})\), we can define the relation \(EQ_{\mathbb{R}}\) on \(A\) as \[\{ (X_1, X_2 ) \in\mathcal{P}(\mathbb{R}) \times \mathcal{P}(\mathbb{R}) ~|~ |X_1| = |X_2| \}\]
Example: Let \(R_{(\textbf{mod } n)}\) be the set of all pairs of integers \((a, b)\) such that \((a \textbf{ mod } n = b \textbf{ mod } n)\). Then \(a\) is congruent to \(b\) mod \(n\) means \((a, b) \in R_{(\textbf{mod } n)}\). A common notation is to write this as \(a \equiv b (\textbf{mod } n)\).
\(R_{(\textbf{mod } n)}\) is a relation on the set \(\underline{\phantom{\mathbb{Z}}\hspace{20em}}\)
Some example elements of \(R_{(\textbf{mod } 4)}\) are:
There’s a subtle imprecision in this part of the proof as presented, but it can be fixed.↩︎