← Back to Mathematical Logic, Set Theory and Combinatorics
Course: MAT1MN104 — Mathematical Logic, Set Theory and Combinatorics Hours: 12 (Open Ended — not assessed in the external exam)
Exam status: Module V is not part of the external (70-mark) examination, which covers only Modules I–IV. It exists to broaden students’ exposure beyond the core syllabus. This page collects all of Module V’s listed topics in one place, each cross-referenced to the module it most naturally extends.
1. Basic Calculus Concepts
(Extends Module III — Functions and Matrices, since these ideas are properties of functions. See the concurrent course MAT1CJ101 Differential Calculus for full development.)
- Limit: $\lim_{x\to a} f(x) = L$ — f(x) gets arbitrarily close to L as x gets arbitrarily close to a.
- Continuity: f is continuous at a if $\lim_{x\to a} f(x) = f(a)$ — no jump or hole in the graph at $x=a$.
- Differentiation: the derivative $f’(a) = \lim_{h\to 0} \dfrac{f(a+h) - f(a)}{h}$ measures the instantaneous rate of change (slope) of f at a.
- Integration: $\int_a^b f(x)\, dx$ measures the signed area between the graph of f and the x-axis, from $x=a$ to $x=b$.
These are previewed only for orientation; MAT1CJ101 develops them rigorously with proofs and techniques.
2. Relations and Digraphs
(Extends Module II — Set Theory, building on the Cartesian product. See Module II, Section 4.)
- A relation R from set A to set B is a subset of A × B: $R \subseteq A \times B$. Write $aRb$ if $(a,b) \in R$. A relation from A to A is a relation on A.
- Example. $A=\{1,2,3\}$, $aRb$ iff $a \le b$: $R = \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}$.
- Digraph: draw each element of A as a vertex (dot); draw an arrow $a\to b$ whenever $aRb$.
- Properties of a relation on A:
- Reflexive — $aRa$ for every $a$ (every vertex has a self-loop).
- Symmetric — $aRb \Rightarrow bRa$ (every arrow has a matching reverse arrow).
- Transitive — $aRb$ and $bRc \Rightarrow aRc$ (“shortcut” arrows already present).
- Reflexive + symmetric + transitive = equivalence relation (partitions A into groups of mutually related elements).
3. Conditional Probability and the Multiplication Theorem
(Extends Module IV — Combinatorics and Discrete Probability. See Module IV, Section 5.)
$p(A\mid B) = p(A\cap B) / p(B)$, for $p(B) \neq 0$ — the probability of A once we already know B has occurred; B becomes the new, smaller sample space.
Multiplication theorem: rearranging, $p(A\cap B) = p(B)\cdot p(A\mid B) = p(A)\cdot p(B\mid A)$.
4. Dependent and Independent Events
(Same section as above.)
Events A, B are independent if one’s occurrence doesn’t affect the other’s probability: $p(A\mid B) = p(A)$, equivalently $p(A\cap B) = p(A)\cdot p(B)$. If this fails, they are dependent.
Example. Draw two cards with replacement: independent, $p(\text{both aces}) = (4/52)\cdot(4/52)$. Draw two cards without replacement: dependent, $p(\text{both aces}) = (4/52)\cdot(3/51)$ — the second probability changes because the deck changed.
5. Probability Distributions
(Same section as above; uses the combination formula from Module IV, Section 3.)
A random variable $X$ assigns a number to each outcome of an experiment (e.g., $X$ = number of heads in three coin tosses). Its probability distribution lists every value of $X$ with its probability.
Example. Three fair coin tosses, $X$ = number of heads $\in \{0,1,2,3\}$:
\[\begin{aligned} p(X=0) &= C(3,0)/2^3 = 1/8 \\ p(X=1) &= C(3,1)/2^3 = 3/8 \\ p(X=2) &= C(3,2)/2^3 = 3/8 \\ p(X=3) &= C(3,3)/2^3 = 1/8 \end{aligned}\]Expected value: $E[X] = \sum x\cdot p(X=x)$ — the long-run average value of $X$.
6. Correlation and Regression
Given paired data $(x_1,y_1), \ldots, (x_n,y_n)$:
- The correlation coefficient $r$ (between $-1$ and $1$) measures how strongly x and y move together linearly. $r$ near $\pm1$: strong linear relationship. $r$ near $0$: little or none.
- Linear regression fits the “best” straight line $\hat{y} = a + bx$ through the data, minimizing the total squared vertical distance from the data points to the line — the standard tool for predicting y from x.
7. Numerical Methods
(Extends Module III — Functions and Matrices. See Module III, Sections 4.2–4.3.)
7.1 Bisection Method
A root of a continuous function f is r with $f(r)=0$. If $f(a)$ and $f(b)$ have opposite signs, a root lies in $[a,b]$ (Intermediate Value Theorem). Let $c = (a+b)/2$:
- if $f(c)=0$, done;
- if $f(a)$, $f(c)$ have opposite signs, the root is in $[a,c]$ — replace b with c;
- otherwise the root is in $[c,b]$ — replace a with c.
Repeat until the interval is as small as desired. Always converges for continuous f, but can be slow.
7.2 Regula-Falsi (False Position) Method
Same setup as bisection, but instead of the midpoint, use where the straight line through $(a,f(a))$ and $(b,f(b))$ crosses the x-axis:
\[c = \frac{a\cdot f(b) - b\cdot f(a)}{f(b) - f(a)}\]Usually converges faster than bisection, since it uses the function’s actual values (not just signs) to make a smarter guess.
7.3 Gauss-Jordan Method
Write a linear system as an augmented matrix $[A \mid b]$. Apply elementary row operations — (1) swap two rows, (2) scale a row by a nonzero constant, (3) add a multiple of one row to another — to reach reduced row-echelon form (leading 1’s in a staircase pattern, 0’s elsewhere in pivot columns). Read the solution off directly.
Worked example. Solve $x+y=3$, $2x-y=0$:
\[\begin{bmatrix} 1 & 1 & \vert & 3 \\ 2 & -1 & \vert & 0 \end{bmatrix} \xrightarrow{R_2 \to R_2-2R_1} \begin{bmatrix} 1 & 1 & \vert & 3 \\ 0 & -3 & \vert & -6 \end{bmatrix} \xrightarrow{R_2 \to -\frac{1}{3}R_2} \begin{bmatrix} 1 & 1 & \vert & 3 \\ 0 & 1 & \vert & 2 \end{bmatrix} \xrightarrow{R_1 \to R_1-R_2} \begin{bmatrix} 1 & 0 & \vert & 1 \\ 0 & 1 & \vert & 2 \end{bmatrix}\]$x=1$, $y=2$. (Check: $1+2=3$ ✓, $2(1)-2=0$ ✓.)
Where Each Topic Fits
| Module V topic | Extends |
|---|---|
| Relations and Digraphs | Module II — Set Theory |
| Basic Calculus Concepts | Module III — Functions and Matrices |
| Root-Finding (Bisection, Regula-Falsi) | Module III — Functions and Matrices |
| Gauss-Jordan Method | Module III — Functions and Matrices |
| Conditional Probability, Multiplication Theorem, Dependent/Independent Events, Probability Distributions, Correlation and Regression | Module IV — Combinatorics and Discrete Probability |
None of this material is required for the external exam; it exists to broaden your view of where the ideas in Modules I–IV lead next.