Week 8 at a glance

We will be learning and practicing to:

• 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

TODO:

Week 8 Monday: Cardinality of Sets

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

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\).

Week 8 Wednesday and Friday: Finite, countably infinite, and uncountable sets

Cardinality of sets

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.

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.

Claim: \(L\) is countably infinite

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}\]

Cardinality categories

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\).

Are there always *bigger* sets?

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.

Countable vs. uncountable: sets of numbers

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):

Completeness axioms (Rosen Appendix 1):

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$}\]

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)\). Since¹ \(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}\)

Other examples of uncountable sets

• 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.

Review Quiz

1. Sets of numbers.
   

   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

   1. \(\forall x \in \mathbb{Q} ~\forall y \in \mathbb{Q}~ \exists z \in \mathbb{Q} ~( x + y = z)\)

   2. \(\forall x \in \mathbb{Q} ~\forall y \in \mathbb{Q}~ \exists z \in \mathbb{Q} ~( x + z = y)\)

   3. \(\forall x \in \mathbb{Q} ~\forall y \in \mathbb{Q}~ \exists z \in \mathbb{Q} ~( x \cdot y = z)\)

   4. \(\forall x \in \mathbb{Q} ~\forall y \in \mathbb{Q} ~\exists z \in \mathbb{Q} ~( x \cdot z = y)\)

   5. \(\forall x \in \overline{\mathbb{Q}}~ \forall y \in \overline{\mathbb{Q}}~ \exists z \in \overline{\mathbb{Q}} ~( x + y = z)\)

   6. \(\forall x \in \overline{\mathbb{Q}}~ \forall y \in \overline{\mathbb{Q}}~ \exists z \in \overline{\mathbb{Q}}~( x + z = y)\)

   7. \(\forall x \in \overline{\mathbb{Q}} ~\forall y \in \overline{\mathbb{Q}}~ \exists z \in \overline{\mathbb{Q}} ~( x \cdot y = z)\)

   8. \(\forall x \in \overline{\mathbb{Q}} ~\forall y \in \overline{\mathbb{Q}}~ \exists z \in \overline{\mathbb{Q}}~( x \cdot z = y)\)

   1. Which of the statements above (if any) could be disproved using the counterexample \(x = \frac{1}{2}\), \(y= \frac{3}{4}\)?

   2. Which of the statements above (if any) could be disproved using the counterexample \(x = \sqrt{4}\), \(y= \sqrt{3}\)?

   3. Which of the statements above (if any) could be disproved using the counterexample \(x = 0\), \(y= 3\)?

   4. Which of the statements above (if any) could be disproved using the counterexample \(x = \sqrt{2}\), \(y= 0\)?

   5. 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}\).

2. Finite vs. infinite.
   

   Select all and only the finite sets below.

   1. \(X = \{ a,b,c\}\)

   2. \(Y = \{ 1, 2, 3, 4, 5\}\)

   3. \(Z = \{ 10, 20, 30 \}\)

   4. \(\emptyset\)

   5. \(\mathbb{Z}\)

   6. \(\{ \emptyset \}\)

   7. \(\{ \mathbb{Z} \}\)

3. Functions.
   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\)

   1. Select all and only the tables that each define a well-defined function whose domain and codomain is each \(X\), \(Y\), or \(Z\).

   2. 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.

   3. 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.

4. Functions.
   

   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}\]

   1. What is the result of \(f(-3)\)?

   2. 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.

   3. 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.

   4. What is the result of \(g(-4)\)?

   5. What is the result of \(g(4)\)?

   6. Consider the following statements, and indicate if they are true for each of \(f\), \(g\), \(h\), and \(q\).

      1. This function is one-to-one.

      2. This function is onto.

      3. This function is a bijection.

      4. This function could serve as a witness for \(|\mathbb{Z}| \leq |\mathbb{N}|\).

      5. This function could serve as a witness for \(|\mathbb{Z}| \geq |\mathbb{N}|\).

      6. This function could serve as a witness for \(|\mathbb{N}| \leq |\mathbb{Z}|\).

      7. This function could serve as a witness for \(|\mathbb{N}| \geq |\mathbb{Z}|\).

5. Functions.
   

   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.

   1. \(f\) is one-to-one

   2. \(f\) is onto

   3. \(f\) is a bijection

   4. \(f\) witnesses that \(|\mathbb{N}| \leq |\mathbb{Z}|\)

   5. \(f\) witnesses that \(|\mathbb{N}| \geq |\mathbb{Z}|\)

   6. \(f\) witnesses that \(|\mathbb{N}| = |\mathbb{Z}|\)

   7. There is a one-to-one function with domain \(\mathbb{N}\) and codomain \(\mathbb{Z}\)

   8. There is an onto function with domain \(\mathbb{N}\) and codomain \(\mathbb{Z}\)

   9. There is a bijection with domain \(\mathbb{N}\) and codomain \(\mathbb{Z}\)

   10. \(|\mathbb{N}| \leq |\mathbb{Z}|\)

   11. \(|\mathbb{N}| \geq |\mathbb{Z}|\)

   12. \(|\mathbb{N}| = |\mathbb{Z}|\)

6. Diagonalization.
   

   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.

   1. \(0 \in D_{f_1}\)

   2. \(D_{f_1}\) is infinite

   3. \(D_{f_1}\) is uncountable

   4. \(1 \in D_{f_2}\)

   5. \(D_{f_2}\) is empty

   6. \(D_{f_2}\) is countably infinite

7. Classifying cardinality.
   

   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?

   1. \(B\)

   2. \(S\)

   3. \(\{ x \in \mathbb{N} ~\mid~ x = (4102)_3 \}\)

   4. \(\{ x \in \mathbb{R} ~\mid~ \text{$x$ has a binary fixed-width $5$ expansion} \}\)

   5. \(\{ x \in \mathbb{R} ~\mid~ x = (0.10)_{(2,1,2)} \}\)