Every past question, categorised (proof)

Every past question, categorised §

Simul. inequalities -> interval solution §

1. Solve the system of simultaneous inequalities

$$\begin{array}{rl}{x}^2+x-6& >0\\ x^2-25& <0\end{array}$$

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

2. Solve the system of simultaneous inequalities

$$\begin{array}{rl}{x}^2-6x+8& \ge 0\\ x^2-4x+3& >0\end{array}$$

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

3. Solve the system of simultaneous inequalities

$$\begin{array}{rl}{x}^2-2x& \ge 0\\ x^2-x-6& <0\end{array}$$

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

Mapping -> injective, surjective? §

1. 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))=2^a\cdot 3^b$; [3 marks]
   2. $g:[0,\infty )\to (0,1],g(x)=\frac{1}{x^2+1}$; [3 marks]
   3. $h:A\to A$, where $A=\mathcal{P}(\{a,b,c\})$ is the set of all subsets of $\{a,b,c\}$ and $h(X)=X\cap \{b,c\}$. [3 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))=\frac{a}{b}$; [3 marks]
   2. $g:(0,\infty )\to (0,\infty ),g(x)=\frac{1}{x^2}$; [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 \{v\}$ for $X\in A$. [3 marks]

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

   1. $f:\mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}\times \mathbb{Z},f((a,b))=(a+b,a-b)$;
   2. $g:\mathbb{R}\to (0,1],g(x)=\frac{1}{x^2+1}$;
   3. $h:\mathcal{P}(\mathbb{N})\to \mathcal{P}(\mathbb{Z})$, where $h(X)=\{-a:a\in X\}$. (Recall that $\mathcal{P}(A)$ denotes the set of all subsets of a set $A$).

Prove an equivalence -> visualise classes (and list elements) §

1. 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 }|x_1|+y_1=|x_2|+y_2$$

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

2. 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 }(x_1{)}^2+(y_1{)}^2=(x_2{)}^2+(y_2{)}^2$$

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

3. Let $\sim$ be a relation on the set $A=\{1,2,3,4,5,6,7\}$ defined as

$$a\sim b⟺a+b\text{ is even}$$

Prove that $\sim$ is an equivalence relation and depict this relation on the diagram as a subset of $A\times A$, then list the elements of the corresponding equivalence class $[3]$ of the element $3$. [9 marks]

Prove an order relation -> visualise subset §

1. 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]

Bijective mapping -> same cardinality demonstration §

1. 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]

2. Demonstrate that the set of positive integers $\mathbb{N}$ and the Cartesian product $\{1,2\}\times \mathbb{N}$ have the same cardinality by exhibiting a bijective mapping $f:\mathbb{N}\to \{1,2\}\times \mathbb{N}$. [9 marks]

Create truth tables -> categorise tautologies/contradictions §

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

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

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

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

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

Evaluate logical statements -> true or false §

1. 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))$.

Prove by contradiction -> Cantor diagonal argument §

1. 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]

2. 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 letter $X$ or letter $Y$. Use Cantor’s diagonalisation method to prove by contradiction that $S$ is uncountable. [8 marks]

Prove by contradiction -> number is irrational §

1. Prove by contradiction that $\sqrt{3}\text{centernot}\in \mathbb{Q}$. [8 marks]

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

Prove by induction -> sequence §

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

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

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

Prove by induction -> inequality §

1. Use mathematical induction to prove that $3^n>20n$ for any positive integer $n\ge 4$. [8 marks]

2. Use mathematical induction to prove that $4^k>10k$ for any positive integer $k\ge 3$. [8 marks]

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

Prove by induction -> divisibility §

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

Properties of set operations -> Expression simplification §

1. 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]

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

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

[8 marks]

3. Use the properties of operations on sets to show that

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

[8 marks]