Resources to make predictions (proof)

Resources used to make predictions §

Topics §

These are the topics that Evgeny explicitly stated would be on the midterm paper.

• Relations,
• Mappings,
• Cardinalities and Bijections,
• Statements and Logical Operations,
• Negation and Proof Strategies.

Past Papers §

Note: These are for the final exams, hence are twice as long as the mid-term papers - take this into account when testing the time taken to complete the exam(s).

Relevant questions are summarised here: Proof Exam Question Breakdowns.

2021 §

• Proof PP (2021).pdf,
• Proof PP (2021) - checks.pdf.

Question	Topic	Marks
1a	Simul. inequalities, interval solution	8
1b	Prove an equivalence, visual classes	9
1c	State and prove a theorem ON LIMITS	8
2ai/ii	Create truth tables, categorise taut./contr.	4 x2
2bi	Definition ON LIMITS	4
2bii	Prove a given statement ON LIMITS	5
2c	Use Cantor’s diagonalisation to prove by contradiction that a set is uncountable	8
3a	Prove by induction for a sequence $\ge 3$	8
3b	Simplify an expression using set operation prop.	8
3ci/ii/iii	Determine if a mapping is injective/surjective	3 x3
4a	Prove by induction for an inequality $\ge 4$	8
4bi	Prove R is an order relation	5
4bii	Depict a relation as a subset on the diagram of a Cartesian product	4
4c	Demonstrate that two sets have the same cardinality with a bijective mapping	8

2022 §

• Proof PP (2022).pdf,
• Proof PP (2022) - checks.pdf.

Question	Topic	Marks
1a	Simul. inequalities, interval solution	8
1b	Prove an equivalence, visual classes	9
1c	State and prove a theorem ON LIMITS	8
2ai/ii	Create truth tables, categorise taut./contr.	4 x2
2bi	Definition ON LIMITS	4
2bii	Prove a given statement ON LIMITS	5
2c	Use Cantor’s diagonalisation to prove by contradiction that a set is uncountable	8
3a	Prove by induction for a sequence $\ge 3$	8
3b	Simplify an expression using set operation prop.	8
3ci/ii/iii	Determine if a mapping is injective/surjective	3 x3
4a	Prove by induction for an inequality $\ge 3$	8
4b	Prove by contradiction that (a number is irrational)	8
4c	Demonstrate that two sets have the same cardinality with a bijective mapping	8

2023 §

• Proof PP (2023).pdf,
• Proof PP (2023) - checks.pdf.

Question	Topic	Marks
1a	Use induction to prove an inequality $\ge 3$	8
1b	Simul. inequalities, interval solution	8
1ci	Prove an equivalence relation	3
1cii	Depict relation as a subset of $A\times A$	3
1ciii	List elements of corresponding equivalence class	3
2a	Use induction to prove divisbility	8
2bi/ii	Truth tables to find tauts/contras	4 x2
2c	Limits stuff	9
3a	Use induction to prove sequence $\ge 3$	8
3bi/ii/iii	Determine if mappings are injective/surjective	8 (/3)
3c	Prove by contradiction that (a number is irrational)	9
4a	Use set operation properties to simplify	8
4bi/ii/iii	Evaluate logical statements to true or false	8 (/3)
4c	Limits stuff

In-Class Material §

Practical Worksheets §

• Proof Practical Class, Week 21,
• Proof Practical Class, Week 22,
• Proof Practical Class, Week 23,
• Proof Practical Class, Week 24.

Summarised Questions §

Note: includes tutorial and practical questions, but not past papers.

… (irrelevant questions)

25. Use a diagram to prove the property $A\times (B\cup C)=(A\times B)\cup (A\times C)$.

26. Let $A=\{1,2,\dots ,100\}$ be the set of all integers from 1 to 100. Let $R$ be a relation on $\mathcal{P}(A)$ (the set of all subsets of $A$) defined as $BRC$ if $|B|\le |C|$. Determine if $R$ is…

    1. …transitive,
    2. …reflexive,
    3. …symmetric,
    4. …antisymmetric, and in each case giving a proof if yes, or a counterexample if not. Hence state whether $R$ is an order, or an equivalence, or neither.

27. On the set $S=\{1,2,3,4,5,6,7,8,9\}$, consider the relation $R$ defined as $aRb$ if $a|b$ (that is, $a$ divides $b$). Draw the diagram $R$ as a subset of $S\times S$.

28. Let $\sim$ be a relation on the set $\mathbb{R}\times \mathbb{R}$ defined by $(x,y)\sim (a,b)$ if $y-|x|=b-|a|$.

    1. Show that $\sim$ is an equivalence.
    2. What is the equivalence class of $(2,-3)$ with respect to this equivalence $\sim$?

29. Consider the order relation on $\mathbb{N}$ defined by divisibility: $a|b$ (when $b=ak$ for $k\in \mathbb{N}$). What are the infimum and supremum of the set $S=\{8,12,36\}$? Does this set have the greatest element? What about the smallest element?

30. Consider the lexicographical order ${\le }_L$ on $\mathbb{R}\times \mathbb{R}$, which means that by definition $(a,b){\le }_L(c,d)$ if either $a<c$ (while $b$ and $d$ can be any), or $a=c$ and $b\le d$.

    1. Find the supremum (least upper bound), if it exists, with respect to ${\le }_L$ of the set $D=\{(x,y):x^2+y^2\le 1\}$ (the disc of radius $1$ with centre at the origin, including the unit circle).
    2. Find the supremum (least upper bound), if it exists, with respect to ${\le }_L$ of the set $D_0=\{(x,y):x^2+y^2<1\}$ (the disc of radius $1$ with centre at the origin, without the boundary unit circle).

31. On the set $S=\mathbb{N}\times \mathbb{N}$, consider the relation $\sim$ defined as $(m_1,n_1)\sim (m_2,n_2)$ if $m_1\cdot n_2=m_2\cdot n_1$. Show that $\sim$ is an equivalence. Describe the equivalence class of $(1,2)$ with respect to this equivalence $\sim$.

32. Give an example of finite sets $A,B,X,Y$ such that $(A\times Y)\cup (B\times Y)\ne (A\cup B)\times (X\cup Y)$. Hint: try small sets, say, subsets of $1,2,3,4$.

33. For a fixed set $S$, consider $\mathcal{P}(S)$ (set of all subsets of $S$) ordered by inclusion. For $A,B\subset S$, what is $\sup \{A,B\}$ with respect to this order? What is $\inf \{A,B\}$?

34. How to tie a goat so as it can eat grass exactly within a square? It is allowed to use several leashes, with several pegs. For example, one peg and leash mean that the goat eats within a circle. It is also allowed to string one rope tightly between two pegs, and to tie the goat with leash to as small ring sliding on the first rope. *Hint: use intersections of sets.

35. For which of the following pairs $A,B\subset \mathbb{R}$ does the relation $f=\{(x,y):x=\mid y|\}\subset A\times B$ define a mapping $f:A\to B$? Give reasons to your answers:

    1. $A=\mathbb{R},B=[0,\infty )$.
    2. $A=[0,\infty ),B=\mathbb{R}$.
    3. $A=[0,\infty ),B=(-\infty ,0]$.

36. Given the following mappings, determine which of the composites $f\circ g,g\circ f$ is defined, and write the resulting mapping in standard form:

$$\begin{array}{c}f:\mathbb{Z}\times \mathbb{Z}\to \mathbb{R},f((x,y))=x+y,\text{and}\\ g:\mathbb{R}\to \mathbb{R},g(a)=a^2+1\end{array}$$

37. For each of the following mappings, determine whether it is injective and/or surjective:

    1. $f:\mathbb{Z}\to \mathbb{N},f(k)=k^2+2$.
    2. $f:\mathbb{R}\times \mathbb{R}\to \mathbb{R},f((x,y))=x+y$.
    3. $f:\mathbb{N}\times \mathbb{N}\to \mathbb{N},f((m,n))=2^{m-1}\cdot (2n-1)$.

38. Let $A=\mathcal{P}(\{u,v,w\})$ be the set of all subsets of $\{u,v,w\}$ and let $f:A\to A,f(x)=X\cap \{u,v\}$. Draw the diagram of the Cartesian product $A\times A$ and indicate $f$ as a subset of $A\times A$. What is the image of $f$?

39. Find the image of the mapping $f:\mathbb{R}\to \mathbb{R},f(x)=\frac{1}{x^2+5}$.

40. Show that $f:[3,\infty )\to (0,1],f(x)=\frac{2}{x-1}$ is a bijection and find the inverse mapping $f^{-1}$ - indicating its domain and image.

41. Let $f:\mathbb{R}\to \mathbb{R},f(x)=2x+1$. Define recursively the mappings $F_1=f$ and $F_{k+1}=f\circ F_k$ for all $k\in \mathbb{N}$. Compute several first mappings, conjecture an expression for $F_n$, and prove it by induction.

42. Draw the mapping $g:\mathbb{R}\to \mathbb{R}$ on the $(x,y)$ plane defined by the rule following rule - is it injective, surjective?

$$g(x)=\text{largest integer}\le x$$

43. For the following mapping, what is the image of $g$? What is the full inverse image $g^{-1}(2)$?

$$g(x)=\text{largest integer}\le x$$

44. Given any mapping $f:A\to B$, prove that the relation $\sim$ on $A$ defined by $a_1\sim a_2$ if $f(a_1)=f(a_2)$ is an equivalence relation. What are the equivalence classes?

45. Prove that the following sets have the same cardinality by producing explicitly a bijection between the sets and describing this bijection…

    1. … by a formula for $|(-\infty ,0]|=|[3,+\infty )$;
    2. … by representing the set on the right as a sequence: $|\mathbb{N}|=|\{a,b,c\}\cup \mathbb{N}|$;
    3. … by any method: $|\{a,b\}\times \mathbb{Z}|=|\mathbb{Z}|$;
    4. … by using a sequence of points: $|[0,1]|=|(0,1)|$;
    5. … geometrically: $|(0,1)|=|(0,\infty )|$.

46. Use this theorem to prove that $|\mathbb{N}\times \mathbb{N}\times \mathbb{N}|={\aleph }_0$.

47. Let $S$ be the set of all sequences of the form $(a_1,a_2,a_3,\dots )$, where every $a_i$ is either $A$ or $B$. Use Cantor’s “diagonal method” to prove that the set $S$ is not countable.

48. Recall that $\{0,1\}\times \{0,1\}\times \{0,1\}$ consists of triples of $1$s and $0$s, and $\mathcal{P}(\{a,b,c\})$ is the set of all subsets of $\{a,b,c\}$. Consider the following mapping, in which a subset $X\subset \{a,b,c\}$ is mapped to a string of length $3$ consisting of $0$s and $1$s depending on which of the elements $a,b,c$ belong to $X$ (with $1$ indicating yes and $0$ indicating no). Write the images $f(\varnothing )$, $f(\{a,c\})$, $f(\{b\})$. Is $f$ a bijection?

$$f:\mathcal{P}(\{a,b,c\})\to \{0,1\}\times \{0,1\}\times \{0,1\}$$

49. Use this theorem to show that any set consisting of pairwise disjoint intervals of the real line (each of $\text{length}>0$) is countable.

50. How does the graph of the function $f(x)$ change under the following transformations (where $a$ is a constant)? That is, how to obtain the graph of $F(x)$ from the graph of $f(x)$, where…

    1. $F(x)=f(x)+a$;
    2. $F(x)=f(x+a)$;
    3. $F(x)=f(ax)$.

51. Assume the mapping $f:[0,1)\to [1,\infty )$, $f(x)=\frac{1}{\sqrt{1-x^2}}$, is a bijection. Apply transformations from the previous question to the mapping $f$ to produce a bijection $F:[2,4)\to [0,\infty )$.

52. Prove that the set $W$ of all finite sequences (‘words) composed of two letters $A,B$ is countable.

53. Translate the following statements between logical formulae and plain statements, given that…

$$\begin{array}{rl}R& =\text{it is raining}\\ S& =\text{the sun is shining}\\ B& =\text{there is a rainbow}\end{array}$$

1. There is a rainbow only if it is raining but the sun is shining.
2. There is no rainbow although it is raining and the sun is shining.
3. $(\neg B\land R)\implies \neg S$.
4. $S\lor (R\land B)$.

54. Use truth tables to prove the logical equivalences… 1. $\neg (P⟹Q)\equiv P\wedge \neg Q$. 2. $(P\wedge Q)\vee R\equiv (P\vee R)\wedge (Q\vee R)$.

55. Use the properties of logical operations to simplify the expression $\neg P\wedge \neg (Q\wedge \neg P)$.

56. Prove by contradiction:

    1. if $k$ is an integer such that $k^2$ is not divisible by $3$, then $k$ is not divisible by $2$.
    2. $\sqrt{5}\text{centernot}\in \mathbb{Q}$.

57. Use the Cantor-Bernstein-Schroder theorem to show that $|A|=|B|$ by producing injective mappings $A\to B$ and $B\to A$, where $A$ is the square $A=[0,1]\times [0,1]$ and $B$ is the disc $B=\{(x,y):x^2+y^2\le 1\}$.

Slides §

• Proof Prelim Slides (Week 21).pdf,
• Proof Prelim Slides (Week 22).pdf,
• Proof Prelim Slides (Week 23).pdf,
• Proof Prelim Slides (Week 24).pdf (up to page 69).

Summarised Notes §

To be written - base on the given answers to give mock answers for every type of question that could be ask, providing all theorems that are required, and offer set methods/layouts for solving the questions.