MATH 127: Sample Final Exam B
1. Consider the following proposition.
∀n ∈ N, ∃p ∈ N, ((p > n)∧ ∀k ∈ N, (k | p → (k = 1 ∨ k = p))).
(a) Determine whether this statement is true or false. Justify your answer with a sentence or two. (A full proof is not necessary.) [4 pts]
(b) Regardless of the truth value, write the logical negation of this statement in maximally negated form. [5 pts]
2. Define a sequence ⟨an | n ∈ N⟩ recursively as follows:
Prove that for all n ∈ N, an and an+1 are coprime. [10 pts]
3. Let n ∈ Z with n ≥ 2. Prove that
using a “counting in two ways” argument. [12 pts]
• Use the exact form of the equation as given; do not simplify it algebraically.
• If your argument involves constructing partitions, justify that your construction defines a valid partition.
4. For the following problems, provide an appropriate counting argument to justify your answer.
You may leave answers as products, sums of integers, factorials, or binomial coefficients.
Let S be the set of strings (arrangements with repetition) of length 8 formed from the 26 letters of the English alphabet, and let T ≤ S be the subset consisting of strings with all distinct letters.
(a) Determine the cardinalities of S and T. [3 pts]
(b) How many elements of S contain the letters A, B, and C? [6 pts]
(c) How many elements of T contain the letters G and J such that G appears somewhere to the left of J in the string? [6 pts]
5. (a) Let m ∈ Z+ and Fm = {f : N → N | ∀n ≥ m,f(n) = 0}. Define a bijection between Fm and Nm and prove that it is a bijection. [10 pts]
(b) Prove that
F = {f : N → N | f(n) ≠ 0 for only finitely many values of n}
is countably infinite. [6 pts]
6. Let A and B be non-empty sets, and let f : A → B be an arbitrary function. Prove that f
is injective if and only if
∀X ∈ P(A), Imf(X) ⊆ Imf(X).
Note: X denotes the complement of X in A, and Imf(X) denotes the complement of Imf(X) in B. [12 pts]
7. A relation R on a non-empty set S is called Euclidean if and only if R satisfies the following
property:
∀a, b, c ∈ S, (((a, b) ∈ R ∧ (a, c) ∈ R) → (b, c) ∈ R).
Prove that a relation R is an equivalence relation on S if and only if R is both Euclidean and reflexive. [10 pts]
8. For any x ∈ R, define the function frac(x) = x - lx」. Let α ∈ R and n ∈ Z+ be arbitrary and fixed. Prove that there exist i,j ∈ {0} U [n], with i ≠ j, such that [8 pts]
|frac(iα) - frac(jα)| < n/1 .
9. Determine, with proof, the set of all integers that leave a remainder of 4 when divided by 5 and a remainder of 6 when divided by 13. [8 pts]