Below are the instructions that will be on the first page of the test package:

1. Predicates and Quantifiers

Express each of the following statements symbolically using quantifiers, variables, propositional connectives, and predicates (make sure to define the domain and the meaning of any predicates you introduce). Then, express its negation as a logically equivalent compound proposition without a \(\neg\) in front. Decide whether the statement or its negation is true, and prove it.

1. If \(m\) is an integer, \(m^2 + m +1\) is odd.

2. For all integers \(n\) greater than \(5\), \(2^n-1\) is not prime.

3. If \(n\) and \(m\) are even integers, then \(n - m\) is even.

2. Proof strategies

Prove each of the following claims. Use only basic definitions and general proof strategies in your proofs; do not use any results proved in class / the textbook as lemmas. You may use basic properties of real numbers that we stated (without proof) in class, e.g. that the difference of two integers is an integer.

1. The difference of any rational number and any irrational number is irrational.

2. If \(a, b, c\) are integers and \(a^2 + b^2 = c^2\), then at least one of \(a\) and \(b\) is even.

3. For any integer \(n\), \(n^2 + 5\) is not divisible by \(4\).

4. For all positive integers \(a,b,c\), if \(a \not | bc\) then \(a \not | b\). (The notation \(a \not | b\) means “a does not divide b”).

Bonus: Watch the video https://www.youtube.com/watch?v=MhJN9sByRS0 and write down the statement and one or both of the proofs described using the notation, definitions, and proof strategies from CSE 20.

3. Sets

Prove or disprove each of the following statements.

1. For all sets \(A\) and \(B\), \(\mathcal{P}(A) \cup \mathcal{P}(B) = \mathcal{P}(A \cup B)\).

2. For all sets \(A\) and \(B\), \(\mathcal{P}(A) \cap \mathcal{P}(B) = \mathcal{P}(A \cap B)\).

3. For any sets \(A, B, C, D\), if the Cartesian products \(A\times B\) and \(C \times D\) are disjoint then either \(A\) and \(C\) are disjoint or \(B\) and \(D\) are disjoint (or both).

4. There are sets \(A, B\) such that \(A \in B\) and \(A \subseteq B\).

5. For all sets \(A, B, C\): \(A \cap B = \emptyset\) and \(B \cap C = \emptyset\) if and only if \((A \cap B) \cap C = \emptyset\).

4. Induction and Recursion

Prove the following statements:

1. \(\forall s \in S \, (~rnalen(s) = basecount(s,\texttt{A}) + basecount(s,\texttt{C}) + basecount(s,\texttt{U}) + basecount(s,\texttt{G})~)\) where \(S\) RNA strands and the functions \(rnalen\) and \(basecount\) are define recursively as: \[\begin{array}{llll} & & \textit{rnalen} : S & \to \mathbb{Z}^+ \\ \textrm{Basis Step:} & \textrm{If } b \in B\textrm{ then } & \textit{rnalen}(b) & = 1 \\ \textrm{Recursive Step:} & \textrm{If } s \in S\textrm{ and }b \in B\textrm{, then } & \textit{rnalen}(sb) & = 1 + \textit{rnalen}(s) \end{array}\] \[\begin{array}{llll} & & \textit{basecount} : S \times B & \to \mathbb{N} \\ \textrm{Basis Step:} & \textrm{If } b_1 \in B, b_2 \in B & \textit{basecount}(b_1, b_2) & = \begin{cases} 1 & \textrm{when } b_1 = b_2 \\ 0 & \textrm{when } b_1 \neq b_2 \\ \end{cases} \\ \textrm{Recursive Step:} & \textrm{If } s \in S, b_1 \in B, b_2 \in B &\textit{basecount}(s b_1, b_2) & = \begin{cases} 1 + \textit{basecount}(s, b_2) & \\ \qquad \textrm{when } b_1 = b_2 &\\ \textit{basecount}(s, b_2) & \\ \qquad \textrm{when } b_1 \neq b_2 &\\ \end{cases} \end{array}\]

2. \(\forall l_1 \in L \, \forall l_2 \in L \, (\textit{sum}(\textit{concat}(l_1, l_2)) = \textit{sum}(l_1) + \textit{sum}(l_2))\), where the function \(\textit{concat}\) is defined as: \[\begin{array}{llll} & & \textit{concat} : L \times L & \to L \\ \textrm{Basis Step:} & \textrm{If } l \in L & \textit{concat}([], l) & = l \\ \textrm{Recursive Step:} & \textrm{If } l, l' \in L\textrm{ and }n \in \mathbb{N}\textrm{, then } & \textit{concat}((n, l), l') & = (n, \textit{concat}(l, l')) \end{array}\] and the function \(\textit{sum} : L \to \mathbb{N}\) that sums all the elements of a list and is defined by: \[\begin{array}{llll} & & \textit{sum} : L & \to \mathbb{N} \\ \textrm{Basis Step:} & & \textit{sum}([]) & = 0 \\ \textrm{Recursive Step:} & \textrm{If } l \in L, n \in \mathbb{N} & \textit{sum}((n, l)) & = n + \textit{sum}(l) \end{array}\]

5. Induction and Recursion

At time 0, a particle resides at the point 0 on the real line. Within 1 second, it divides into 2 particles that fly in opposite directions and stop at distance 1 from the original particle. Within the next second, each of these particles again divides into 2 particles flying in opposite directions and stopping at distance 1 from the point of division, and so on. Whenever particles meet they annihilate (leaving nothing behind). How many particles will there be at time \(2^{11} -1\)? You do not need to justify your answer. Hint: Derive a formula for the number/ locations of particles at time \(2^n-1\) for arbitrary positive integer n, prove the formula using induction, and apply it when \(n=11\).

6. Induction and Recursion

Prove that every positive integer has a base \(3\) expansion. Hint: use strong induction.

7. Functions & Cardinalities of sets

Prove each of the following claims.

1. For the “function" \(f: \mathbb{Z} \to \{0, 1, 2, 3 \}\) given by \(f(x) = x~\text{\bf mod}~5\), it is not the case that every element of the domain maps to exactly one element of the codomain (that is, it is not a well-defined function).

2. The “function" \(f: \mathcal{P}( \mathbb{Z}^+) \to \mathbb{Z}\) given by \[f(A) = \text{the maximum element in A}\] is not well-defined.

3. There is a one-to-one function with domain \(\{a,b,c\}\) and codomain \(\mathbb{R}\).

4. There is an onto function with domain \(R\) and codomain \(\{ \pi, \frac{1}{17} \}\), where \(R\) is the set of user ratings in a database with 5 movies.

5. The Cartesian product \(\mathbb{Z}^+ \times \{ a,b,c \}\) is countable.

6. The interval of real numbers \(\{x \in \mathbb{R} ~\mid~ 5 \leq x \leq 8\}\) is uncountable. Hint: you may use the fact that the unit interval \(\{ x \in \mathbb{R} ~\mid~ 0 \leq x \leq 1\}\) is uncountable.