Proof Exam Content

Predictions §

Resources to make predictions (proof).

Every past question, categorised (proof).

Proof Question-Based Revision.

Possible questions §

1. Solve the system of simultaneous inequalities

$$\begin{array}{rl}a{x}^2+bx+c& \le 0\\ x^2-d^2& >0\end{array}$$

and represent the solution as a union of intervals. [8 marks]

2. For each of the following mappings, determine whether it is (1) injective, (2) surjective, giving reasons to your answers.

   1. $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N},f((a,b))=\dots$; [3 marks]
   2. $g:[0,\infty )\to \dots ,g(x)=\frac{1}{x^2+1}$; [3 marks]
   3. $h:A\to A$, where $A=\mathcal{P}(\{u,v,w\})$ is the set of all subsets of $\{u,v,w\}$ and $h(X)=X\cup \{\dots \}$ for $X\in A$. [3 marks]

3. Let $\sim$ be a relation on the $(x,y)$ coordinate plane $\mathbb{R}\times \mathbb{R}$ defined as

$$(x_1,y_1)\sim (x_2,y_2)\text{ if }\dots$$

Prove that $\sim$ is an equivalence relation and indicate the equivalence classes of the elements $(0,0)$ and $(\dots ,\dots )$ by pictures on the coordinate plane. [9 marks]

Then, list the elements of the corresponding equivalence class $[\dots ]$ of the element $\dots$. [3 marks]

4. Let $R$ be the relation on the set $A=\{1,2,3,4,5,6,7,8,9\}$ defined as $aRb$ if $b$ is divisible by $a$.

   1. Prove that $R$ is an order relation. [5 marks]
   2. Depict the relation $R$ as a subset on the diagram of the Cartesian product $A\times A$. [4 marks]

5. Demonstrate that the sets of the positive integers $\mathbb{N}$ and all integers $\mathbb{Z}$ have the same cardinality by exhibiting a bijective mapping $f:\mathbb{Z}\to \mathbb{N}$. [8 marks]

6. Determine the truth tables for the following statements and indicate which of them (if any) are tautologies or contradictions:

   1. $(P\vee Q)⟹(P\wedge \neg Q)$; [4 marks]
   2. $(\neg Q⟹P)\vee (\neg P\vee Q)$. [4 marks]

7. Let $\mathcal{U}=\mathbb{R}$. Determine which of these statements are true, giving reasons to your answers: [8 marks]

   1. $\forall x\forall y((x<y))⟹(x^2<y^2)$;
   2. $\exists x\exists y((x<y)⟹(x^2<y^2))$;
   3. $\exists x\exists y((x>y)\wedge (x^2<y^2))$.

8. Let $S$ be the set of all infinite sequences of the form $(a_1,a_2,\dots )$, where each of the $a_i$ is either $1$ or $2$. Use Cantor’s diagonalisation method to prove by contradiction that $S$ is uncountable. [8 marks]

9. Prove by contradiction that ${\log }_{10}7$ is an irrational number. [9 marks]

10. Let $a_n$ be a sequence defined recursively as $a_1=4$, $a_2=6$, and $a_i=a_{i-1}+2a_{i-2}-4$ for $i\ge 3$. Use mathematical induction to prove that $a_n=2^n+2$ for all positive integers $n$. [8 marks]

11. Use mathematical induction to prove that $6^k>15k$ for any positive integer $k\ge 2$. [8 marks]

12. Use mathematical induction to prove that $2^{2n+1}+1$ is divisible by $3$ for any positive integer $n$. [8 marks]

13. Given that $A$ and $B$ are sets, use the properties of operations on sets to simplify the expression

$$\overline{\overline{A}\cap (B\cup A)}$$

[8 marks]