2 
People try to sit down when the music stops
Person sits in Chair 1, Person sits in Chair 2,
Person is left standing!
We have the following subset relationships between sets of numbers:
\[\mathbb{Z}^{+} \subsetneq \mathbb{N} \subsetneq \mathbb{Z} \subsetneq \mathbb{Q} \subsetneq \mathbb{R}\]
Which of the proper subset inclusions above can you prove?
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 \}|\]
Let \(S_2\) be the set of RNA strands of length 2, formally \(S_2 = \{ s \in S \mid rnalen(s) = 2\}\).
True or False: \(| \{\texttt{A},\texttt{U},\texttt{G},\texttt{C}\} | \leq |S_2 |\)
Why?
True or False: \(| \{\texttt{A},\texttt{U},\texttt{G},\texttt{C}\} \times \{\texttt{A}, \texttt{U}, \texttt{G},\texttt{C}\} | \leq |S_2 |\)
Why?
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\} |\]
Let \(S_2\) be the set of RNA strands of length 2.
True or False: \(|S_2 | \geq | \{\texttt{A},\texttt{U},\texttt{G},\texttt{C}\} |\)
Why?
True or False: \(|S_2 | \geq | \{\texttt{A},\texttt{U},\texttt{G},\texttt{C}\} \times \{\texttt{A}, \texttt{U}, \texttt{G},\texttt{C}\} |\)
Why?
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{aligned} |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{aligned}\]
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.
Select all and only the finite sets below.
\(X = \{ a,b,c\}\)
\(Y = \{ 1, 2, 3, 4, 5\}\)
\(Z = \{ 10, 20, 30 \}\)
\(\emptyset\)
\(\mathbb{Z}\)
\(\{ \emptyset \}\)
\(\{ \mathbb{Z} \}\)
Consider the following input-output definition tables with \(X = \{ a,b,c\}\) and \(Y = \{ 1, 2, 3, 4, 5\}\) and \(Z = \{ 10, 20, 30 \}\)
3
c Table 1
| Input | Output |
|---|---|
| \(1\) | \(10\) |
| \(2\) | \(20\) |
| \(3\) | \(30\) |
c Table 2
| Input | Output |
|---|---|
| \(a\) | \(1\) |
| \(b\) | \(4\) |
| \(c\) | \(5\) |
c Table 3
| Input | Output |
|---|---|
| \(10\) | \(a\) |
| \(20\) | \(b\) |
| \(30\) | \(a\) |
Select all and only the tables that each define a well-defined function whose domain and codomain is each \(X\), \(Y\), or \(Z\).
Select all and only the tables that each define a well-defined function (with domain \(X\) or \(Y\) or \(Z\) and with codomain \(X\) or \(Y\) or \(Z\)) and that is one-to-one.
Select all and only the tables that each define a well-defined function (with domain \(X\) or \(Y\) or \(Z\) and with codomain \(X\) or \(Y\) or \(Z\)) and that is onto.
Consider the following functions:
\[\begin{array}{l|l} \begin{array}{ll} f : \mathbb{Z} &\to \mathbb{N} \\ f(n) & = \begin{cases} 0 & \textrm{ when } n = 0 \\ (-2 \cdot n) - 1 & \textrm{ when } n < 0 \\ 2 \cdot n & \textrm{ when } n > 0 \end{cases} \end{array} & \begin{array}{ll} g : \mathbb{Z} &\to \mathbb{N} \\ g(n) & = \begin{cases} -1 \cdot n & \textrm{ when } n < 0 \\ n & \textrm{ when } n \geq 0 \end{cases} \end{array} \\ \hline \begin{array}{ll} h : \mathbb{N} &\to \mathbb{Z} \\ h(n) & = \begin{cases} (-2 \cdot n) + 1 & \textrm{ when } n \textrm{ is even } \\ 2 \cdot n & \textrm{ when } n \textrm{ is odd } \end{cases} \end{array} & \begin{array}{ll} q : \mathbb{N} &\to \mathbb{Z} \\ q(n) & = \begin{cases} -1 \cdot ((n + 1) \textbf{ div } 2) & \textrm{ when } n \textrm{ is odd} \\ n \textbf{ div } 2 & \textrm{ when } n \textrm{ is even} \\ \end{cases} \end{array} \\ \end{array}\]
What is the result of \(f(-3)\)?
What is the result of \(q(f(-4))\)?
Notice we are looking at function composition here: first apply \(f\) and then apply \(q\) to the result.
What is the result of \(f(h(4))\)?
Notice we are looking at function composition here: first apply \(h\) and then apply \(f\) to the result.
What is the result of \(g(-4)\)?
What is the result of \(g(4)\)?
Consider the following statements, and indicate if they are true for each of \(f\), \(g\), \(h\), and \(q\).
This function is one-to-one.
This function is onto.
This function is a bijection.
This function could serve as a witness for \(|\mathbb{Z}| \leq |\mathbb{N}|\).
This function could serve as a witness for \(|\mathbb{Z}| \geq |\mathbb{N}|\).
This function could serve as a witness for \(|\mathbb{N}| \leq |\mathbb{Z}|\).
This function could serve as a witness for \(|\mathbb{N}| \geq |\mathbb{Z}|\).
Properties of cardinality \[\begin{aligned} &\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{aligned}\]
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{aligned} &list: \mathbb{N} \to L \\ &list(n) = (n, []) \\ & \end{aligned}\]
\[\begin{aligned} &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{aligned}\]
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{aligned} &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{aligned}\]
2 \[\begin{aligned} &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{aligned}\]
\[\begin{aligned} &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{aligned}\]
Consider the function \(f: \mathbb{N} \to \mathbb{Z}\) given by \(f(n) = \begin{cases} n~\text{\bf div}~4 \qquad &\text{if $n$ is even} \\ -( (n+1)~\text{\bf div}~4) \qquad &\text{if $n$ is odd} \end{cases}\)
Select all and only the true statements below.
\(f\) is one-to-one
\(f\) is onto
\(f\) is a bijection
\(f\) witnesses that \(|\mathbb{N}| \leq |\mathbb{Z}|\)
\(f\) witnesses that \(|\mathbb{N}| \geq |\mathbb{Z}|\)
\(f\) witnesses that \(|\mathbb{N}| = |\mathbb{Z}|\)
There is a one-to-one function with domain \(\mathbb{N}\) and codomain \(\mathbb{Z}\)
There is an onto function with domain \(\mathbb{N}\) and codomain \(\mathbb{Z}\)
There is a bijection with domain \(\mathbb{N}\) and codomain \(\mathbb{Z}\)
\(|\mathbb{N}| \leq |\mathbb{Z}|\)
\(|\mathbb{N}| \geq |\mathbb{Z}|\)
\(|\mathbb{N}| = |\mathbb{Z}|\)
Goals for this question: Reason through multiple nested quantifiers. Fluently use the definition and properties of the set of rationals.
Recall the definition of the set of rational numbers, \(\mathbb{Q} = \left\{ \frac{p}{q} \mid p \in \mathbb{Z} \text{ and } q \in \mathbb{Z} \text{ and } q \neq 0 \right\}\). We define the set of irrational numbers \(\overline{\mathbb{Q}} = \mathbb{R} - \mathbb{Q} = \{ x \in \mathbb{R} \mid x \notin \mathbb{Q} \}\).
2
\(\forall x \in \mathbb{Q} ~\forall y \in \mathbb{Q}~ \exists z \in \mathbb{Q} ~( x + y = z)\)
\(\forall x \in \mathbb{Q} ~\forall y \in \mathbb{Q}~ \exists z \in \mathbb{Q} ~( x + z = y)\)
\(\forall x \in \mathbb{Q} ~\forall y \in \mathbb{Q}~ \exists z \in \mathbb{Q} ~( x \cdot y = z)\)
\(\forall x \in \mathbb{Q} ~\forall y \in \mathbb{Q} ~\exists z \in \mathbb{Q} ~( x \cdot z = y)\)
\(\forall x \in \overline{\mathbb{Q}}~ \forall y \in \overline{\mathbb{Q}}~ \exists z \in \overline{\mathbb{Q}} ~( x + y = z)\)
\(\forall x \in \overline{\mathbb{Q}}~ \forall y \in \overline{\mathbb{Q}}~ \exists z \in \overline{\mathbb{Q}}~( x + z = y)\)
\(\forall x \in \overline{\mathbb{Q}} ~\forall y \in \overline{\mathbb{Q}}~ \exists z \in \overline{\mathbb{Q}} ~( x \cdot y = z)\)
\(\forall x \in \overline{\mathbb{Q}} ~\forall y \in \overline{\mathbb{Q}}~ \exists z \in \overline{\mathbb{Q}}~( x \cdot z = y)\)
Which of the statements above (if any) could be disproved using the counterexample \(x = \frac{1}{2}\), \(y= \frac{3}{4}\)?
Which of the statements above (if any) could be disproved using the counterexample \(x = \sqrt{4}\), \(y= \sqrt{3}\)?
Which of the statements above (if any) could be disproved using the counterexample \(x = 0\), \(y= 3\)?
Which of the statements above (if any) could be disproved using the counterexample \(x = \sqrt{2}\), \(y= 0\)?
Which of the statements above (if any) could be disproved using the counterexample \(x = \sqrt{2}\), \(y= - \sqrt{2}\)?
Hint: we proved in class that \(\sqrt{2} \notin \mathbb{Q}\). You may also use the facts that \(\sqrt{3} \notin \mathbb{Q}\) and \(-\sqrt{2} \notin \mathbb{Q}\).
Bonus - not to hand in: prove these facts; that is, prove that \(\sqrt{3} \notin \mathbb{Q}\) and \(-\sqrt{2} \notin \mathbb{Q}\).
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{aligned} {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{aligned}\]
\(\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 diagonalization argument constructs, for each function \(f: \mathbb{N} \to \mathcal{P}(\mathbb{N})\), a set \(D_f\) defined as \[D_f = \{ x \in \mathbb{N} \mid x \notin f(x) \}\] which has the property that, for all \(n \in \mathbb{N}\), \(f(n) \neq D_f\). Consider the following two functions with domain \(\mathbb{N}\) and codomain \(\mathcal{P}(\mathbb{N})\) \[f_1(x) = \{ y \in \mathbb{N} \mid y~\text{\bf mod}~3 = x~\text{\bf mod}~3 \}\] \[f_2(x) = \{ y \in \mathbb{N} \mid (y > 0) \land (x ~\text{\bf mod}~y \neq 0)\}\]
Select all and only the true statements below.
\(0 \in D_{f_1}\)
\(D_{f_1}\) is infinite
\(D_{f_1}\) is uncountable
\(1 \in D_{f_2}\)
\(D_{f_2}\) is empty
\(D_{f_2}\) is countably infinite
Recall the definitions from previous assignments and class: The bases of RNA are elements of the set \(B = \{\texttt{A}, \texttt{C}, \texttt{G}, \texttt{U}\}\). The set of RNA strands \(S\) is defined (recursively) by:
\[\begin{array}{ll} \textrm{Basis Step: } & \texttt{A}\in S, \texttt{C}\in S, \texttt{U}\in S, \texttt{G}\in S \\ \textrm{Recursive Step: } & \textrm{If } s \in S\textrm{ and }b \in B \textrm{, then }sb \in S \end{array}\]
For \(b\) an integer greater than \(1\) and \(n\) a positive integer, the base \(b\) expansion of \(n\) is \[(a_{k-1} \cdots a_1 a_0)_b\] where \(k\) is a positive integer, \(a_0, a_1, \ldots, a_{k-1}\) are nonnegative integers less than \(b\), \(a_{k-1} \neq 0\), and \[n = a_{k-1} b^{k-1} + \cdots + a_1b + a_0\]
For \(b\) an integer greater than \(1\), \(w\) a positive integer, and \(n\) a nonnegative integer with \(n < b^w\), the base \(b\) fixed-width \(w\) expansion of \(n\) is \[(a_{w-1} \cdots a_1 a_0)_{b,w}\] where \(a_0, a_1, \ldots, a_{w-1}\) are nonnegative integers less than \(b\) and \[n = a_{w-1} b^{w-1} + \cdots + a_1b + a_0\] For \(b\) an integer greater than \(1\), \(w\) a positive integer, \(w'\) a positive integer, and \(x\) a real number the base \(b\) fixed-width expansion of \(x\) with integer part width \(w\) and fractional part width \(w'\) is \[(a_{w-1} \cdots a_1 a_0 . c_{1} \cdots c_{w'})_{b,w,w'}\] where \(a_0, a_1, \ldots, a_{w-1}, c_1, \ldots, c_{w'}\) are nonnegative integers less than \(b\) and \[x \geq a_{w-1} b^{w-1} + \cdots + a_1 b + a_0 + c_{1} b^{-1} + \cdots + c_{w'} b^{-w'}\] and \[x < a_{w-1} b^{w-1} + \cdots + a_1 b + a_0 + c_{1} b^{-1} + \cdots + (c_{w'} +1) b^{-w'}\]
For each set below, determine if it is empty, nonempty and finite, countably infinite, or uncountable.
Challenge - not to hand in: how would you prove this?
\(B\)
\(S\)
\(\{ x \in \mathbb{N} ~\mid~ x = (4102)_3 \}\)
\(\{ x \in \mathbb{R} ~\mid~ \text{$x$ has a binary fixed-width $5$ expansion} \}\)
\(\{ x \in \mathbb{R} ~\mid~ x = (0.10)_{(2,1,2)} \}\)
There’s a subtle imprecision in this part of the proof as presented, but it can be fixed.↩︎