← Back to Mathematical Logic, Set Theory and Combinatorics
Course: MAT1MN104 — Mathematical Logic, Set Theory and Combinatorics Hours: 10 | Textbook Sections: 3.1, 3.2, 3.7 (Thomas Koshy, Discrete Mathematics with Applications, 1/e)
Notation: $f: X \to Y$, $\text{Dom}(f)$, $\text{codom}(f)$, floor $\lfloor x \rfloor$, ceiling $\lceil x \rceil$, matrix $A = (a_{ij})$.
1. The Concept of a Function
A function f from X to Y ($f: X \to Y$) assigns exactly one element of Y to each element of X. $X = \text{Dom}(f)$ (domain), $Y = \text{codom}(f)$ (codomain). If f assigns y to x, write $y = f(x)$; y is the value/image, x a pre-image.
⚠️ A function may send two different x’s to the same y, and need not use every element of Y. What’s forbidden: leaving some x unassigned, or assigning it to two different values.
Example. $X=\{a,b,c,d\}$, $Y=\{1,2,3,4\}$. $a\mapsto 1$, $b\mapsto 3$, $c\mapsto 2$, $d\mapsto 4$ is a function. Any x with no arrow, or two arrows, is not a function.
1.1 Piecewise Functions, Sum and Product
A function can be defined by different formulas on different parts of its domain:
\[g(x) = \begin{cases} x^2 & \text{if } x \ge 0 \\ -1 & \text{if } -2 \le x < 0 \\ 3x+4 & \text{otherwise} \end{cases}\]Sum and product: $(f+g)(x) = f(x)+g(x)$, $(fg)(x) = f(x)\cdot g(x)$, defined wherever both f and g are defined: $\text{Dom}(f+g) = \text{Dom}(fg) = \text{Dom}(f) \cap \text{Dom}(g)$.
Example. $f(x)=x^2$ (Dom=$(-\infty,\infty)$), $g(x)=\sqrt{x-1}$ (Dom=$[1,\infty)$). $(f+g)(x) = x^2 + \sqrt{x-1}$, $(fg)(x) = x^2\sqrt{x-1}$, both with domain $[1,\infty)$.
Two functions $f:A\to B$ and $g:C\to D$ are equal if $A=C$, $B=D$, and $f(x)=g(x)$ for all $x\in A$.
(Exam scope: Section 3.1 examinable through Example 3.2, plus piecewise/sum/product; Example 3.7 optional.)
2. Special Functions
- Polynomial: $f(x) = a_nx^n+\cdots+a_1x+a_0$ ($a_n\neq 0$), degree $n$. $n=1$: linear; $n=2$: quadratic.
- Exponential/Logarithmic: $f(x)=a^x$ ($a>0, a\neq 1$); $(\log_a y = x) \leftrightarrow (y = a^x)$.
2.1 Floor and Ceiling
$\lfloor x \rfloor$ = largest integer $\le x$. $\lceil x \rceil$ = smallest integer $\ge x$.
Examples: $\lfloor 3.7 \rfloor=3$, $\lfloor -3.7 \rfloor=-4$, $\lceil 3.2 \rceil=4$, $\lceil -3.2 \rceil=-3$, $\lfloor 5 \rfloor=\lceil 5 \rceil=5$.
Post-office function (intuition): 2003 first-class postage = 37¢ + 23¢ per extra ounce or fraction: $p(x) = 0.37 + 0.23\lceil x-1 \rceil$ for $0<x\le 11$. $p(7.8) = 0.37+0.23\lceil 6.8 \rceil = 0.37+0.23(7) =$ $1.98.
Key properties (Theorem 3.1, proof not examined): for real $x$, integer $n$: $\lfloor n \rfloor=n=\lceil n \rceil$; $\lfloor x+n \rfloor=\lfloor x \rfloor+n$; $\lceil x+n \rceil=\lceil x \rceil+n$; if $n\notin\mathbb{Z}$, $\lceil x \rceil=\lfloor x \rfloor+1$.
2.2 Characteristic Function
For $S \subseteq U$: $f_S(x) = 1$ if $x\in S$, else $0$.
Example. $U=\{a,b,c,d,e,f\}$, $A=\{a,c,d,e\}$. $f_A(a)=f_A(c)=f_A(d)=f_A(e)=1$, $f_A(b)=f_A(f)=0$. Bits right-to-left: A ↔ 6-bit word 011101 — any subset of an n-element universe is an n-bit word.
Theorem 3.3 (properties, proof not examined):
\[\begin{aligned} f_{A\cap B}(x) &= f_A(x)\cdot f_B(x) \\ f_{A\cup B}(x) &= f_A(x) + f_B(x) - f_{A\cap B}(x) \\ f_{A'}(x) &= 1 - f_A(x) \\ f_{A\oplus B}(x) &= f_A(x) + f_B(x) - 2f_{A\cap B}(x) \end{aligned}\](Same “avoid double-counting” idea as $|A\cup B| = |A|+|B|-|A\cap B|$, but per-element instead of per-set-size.)
2.3 Mod and Div Functions
$x \bmod y$ = remainder when x divided by positive integer y. $x \text{ div } y$ = quotient.
Examples: $23 \bmod 5 = 3$, $18 \bmod 6 = 0$, $23 \text{ div } 5 = 4$, $5 \text{ div } 6 = 0$.
Worked example. Today is Thursday — what day in 100 days? $100 \bmod 7 = 2$ → two days after Thursday = Saturday.
(Exam scope: Section 3.2 examinable through Example 3.13; proofs of Theorems 3.1/3.2, Theorem 3.3’s proof, “Card Dealing”, and the “Two Queens Puzzle” are optional/non-examined. Know definitions and be able to compute — not prove.)
3. Matrices
A matrix is a rectangular arrangement of numbers in brackets. $m\times n$ = m rows, n columns (its size). $m=1$: row vector; $n=1$: column vector; $m=n$: square matrix of order $n$. Double subscript: $a_{ij}$ = entry in row i, column j; $A = (a_{ij})_{m\times n}$.
Example. $A = \begin{bmatrix} 3 & -5 & 6 \\ 1 & 0 & 4 \end{bmatrix}$ is $2\times 3$; $a_{12}=-5$, $a_{23}=4$.
- Equal matrices: same size and $a_{ij}=b_{ij}$ for all $i,j$.
- Zero matrix O: all entries 0.
- Main diagonal: $a_{11},a_{22},\ldots,a_{nn}$ of a square matrix.
- Identity matrix $I_n$: $a_{ij}=1$ if $i=j$, else $0$.
3.1 Addition and Scalar Multiplication
For same-size $A=(a_{ij})$, $B=(b_{ij})$, scalar $c$: $A+B = (a_{ij}+b_{ij})$, $cA = (ca_{ij})$. Negative: $-A = (-1)A$.
Worked example (Oct 2024). $A=\begin{bmatrix} 2 & -3 & 7 \\ 0 & 1 & 1 \end{bmatrix}$, $B=\begin{bmatrix} 1 & 5 & 0 \\ 2 & 0 & -1 \end{bmatrix}$.
\[A+B = \begin{bmatrix} 2+1 & -3+5 & 7+0 \\ 0+2 & 1+0 & 1-1 \end{bmatrix} = \begin{bmatrix} 3 & 2 & 7 \\ 2 & 1 & 0 \end{bmatrix}\]Theorem 3.12 (properties, proof not examined): $A+B=B+A$; $A+(B+C)=(A+B)+C$; $A+O=A=O+A$; $A+(-A)=O=(-A)+A$; $(-1)A=-A$; $c(A+B)=cA+cB$; $(c+d)A=cA+dA$; $(cd)A=c(dA)$.
3.2 Matrix Multiplication
Product $AB$ of $A=(a_{ij}){m\times n}$ and $B=(b{ij}){n\times p}$ is $C=(c{ij})_{m\times p}$ where:
\[c_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj} = \sum_k a_{ik}b_{kj}\]⚠️ $AB$ is defined only if columns of A = rows of B. Even when both $AB$ and $BA$ are defined, they’re generally not equal — matrix multiplication is not commutative.
Worked example (Oct 2024, exact question). $A=\begin{bmatrix} 1 & -2 & 3 \\ 0 & 4 & -1 \end{bmatrix}$ ($2\times 3$), $B=\begin{bmatrix} 3 & -2 \\ 0 & 1 \\ -1 & 0 \end{bmatrix}$ ($3\times 2$).
$AB$ ($2\times 2$):
\[AB = \begin{bmatrix} 1(3)+(-2)(0)+3(-1) & 1(-2)+(-2)(1)+3(0) \\ 0(3)+4(0)+(-1)(-1) & 0(-2)+4(1)+(-1)(0) \end{bmatrix} = \begin{bmatrix} 0 & -4 \\ 1 & 4 \end{bmatrix}\]$BA$ ($3\times 3$):
\[BA = \begin{bmatrix} 3(1)+(-2)(0) & 3(-2)+(-2)(4) & 3(3)+(-2)(-1) \\ 0(1)+1(0) & 0(-2)+1(4) & 0(3)+1(-1) \\ -1(1)+0(0) & -1(-2)+0(4) & -1(3)+0(-1) \end{bmatrix} = \begin{bmatrix} 3 & -14 & 11 \\ 0 & 4 & -1 \\ -1 & 2 & -3 \end{bmatrix}\]$AB$ ($2\times 2$) and $BA$ ($3\times 3$) aren’t even the same size — a clean illustration of non-commutativity.
(Exam scope: addition, scalar multiplication, and multiplication — including checking whether AB/BA are defined — are core and repeatedly examined. Theorem 3.12’s proof and matrix-product algorithm analysis are optional/non-examined.)
4. Optional / Not Examined — Module V Extensions
4.1 Basic Calculus Concepts
Preview only (developed fully in MAT1CJ101 Differential Calculus):
- Limit: $\lim_{x\to a} f(x) = L$ — f(x) gets arbitrarily close to L as $x\to a$.
- Continuity: f continuous at a if $\lim_{x\to a} f(x) = f(a)$ — no jump/hole in the graph.
- Differentiation: $f’(a) = \lim_{h\to 0} \dfrac{f(a+h)-f(a)}{h}$ — instantaneous rate of change.
- Integration: $\int_a^b f(x)\,dx$ — signed area under the graph from a to b.
4.2 Root-Finding: Bisection and Regula-Falsi
A root of f is r with $f(r)=0$.
- Bisection: if $f(a)$, $f(b)$ have opposite signs (f continuous), a root lies in $[a,b]$. Let $c=(a+b)/2$; if $f(a),f(c)$ opposite signs, root in $[a,c]$; else in $[c,b]$. Repeat. Always converges, can be slow.
- Regula-Falsi: like bisection, but use $c = \dfrac{a\cdot f(b) - b\cdot f(a)}{f(b) - f(a)}$ (where the line through $(a,f(a)),(b,f(b))$ crosses the x-axis) instead of the midpoint — usually converges faster.
4.3 The Gauss-Jordan Method
Write a linear system as an augmented matrix $[A \mid b]$. Apply elementary row operations — (1) swap 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, 0’s elsewhere in pivot columns). Read off the solution 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$ ✓.)
Chapter Summary
- Function $f: X\to Y$ assigns exactly one $f(x)\in\text{codom}(f)$ to each $x\in\text{Dom}(f)$. Piecewise definitions; sum/product with domain $\text{Dom}(f)\cap\text{Dom}(g)$.
- Special functions: polynomial, exponential/log, floor/ceiling, characteristic function, mod/div.
- Matrix $A=(a_{ij})_{m\times n}$; addition/scalar mult entrywise; product $AB$ (needs $\text{cols}(A)=\text{rows}(B)$) via row·column, not commutative.
- Module V: calculus preview, bisection/regula-falsi, Gauss-Jordan.
Practice Problems
- Which are functions $\{1,2,3\}\to\{a,b\}$? (i) $1\to a,2\to b,3\to a$. (ii) $1\to a,2\to a$ (3 unassigned). (iii) $1\to a,1\to b,2\to a,3\to b$.
- $f(x)=x^2-1$, $g(x)=\sqrt{x}$ (Dom=$[0,\infty)$). Find $(f+g)(x)$, $(fg)(x)$, and their domain.
- Define $|x|$ piecewise and sketch its graph.
- Compute $\lfloor -2.3 \rfloor$, $\lceil -2.3 \rceil$, $\lfloor 7 \rfloor$, $17 \bmod 5$, $17 \text{ div } 5$.
- $U=\{1..8\}$, $A=\{1,3,5,7\}$, $B=\{2,3,5,7\}$. Write $f_A$, $f_B$; verify $f_{A\cap B}(x)=f_A(x)f_B(x)$ for $x=3$, $x=4$.
- If today is Wednesday, what day in 250 days? Show the mod computation.
- $A=\begin{bmatrix} 2 & 0 \\ -1 & 3 \end{bmatrix}$, $B=\begin{bmatrix} 1 & 4 \\ 2 & -2 \end{bmatrix}$. Find $A+B$, $3A$, $AB$, $BA$. Is $AB=BA$ here?
- $A$ is $2\times 3$, $B$ is $3\times 4$. Is $AB$ defined? Is $BA$ defined? Give the size of whichever exist.
- $A=\begin{bmatrix} 1 & -1 \\ 0 & 2 \end{bmatrix}$. Verify $A+(-A)=O$ directly.
- (Module V) One bisection step to narrow a root of $f(x)=x^3-x-2$ known to lie in $[1,2]$.
- (Module V) Solve $2x+y=5$, $x-y=1$ by Gauss-Jordan, showing each row operation.
- Prove using the definition of matrix equality: if $A+B=A$ for all $m\times n$ matrices $A$, then $B$ must be the zero matrix.