2 Mathematical Notation and Proof Techniques

Standard vocabulary for proofs and algorithms.

2.1 Logic and Set Notation

Definition: Logical Quantifiers

Universal ($\forall$): ``For all.’’
Existential ($\exists$): ``There exists.’’
Example: $\forall \varepsilon > 0,\;\exists \delta > 0$'' reads asfor every positive $\varepsilon$ there is a positive $\delta$.’’

Definition: Implication and Equivalence

Implication ($P \Rightarrow Q$): $P$ implies $Q$.
Equivalence ($P \Leftrightarrow Q$): $P$ if and only if $Q$ (iff).
Contrapositive: $\neg Q \Rightarrow \neg P$. Logically equivalent to $P \Rightarrow Q$.

Definition: Set Notation

$x \in S$: $x$ is an element of $S$.
$S \subseteq T$: $S$ is a subset of $T$.
$S \cup T$: Union; $S \cap T$: Intersection; $S \setminus T$: Set difference.
$\{x \in S : P(x)\}$: Set builder notation.
Number Sets: $\fZ$ (integers), $\fR$ (reals), $\fC$ (complex), $\fR^n$ (vectors), $\fR^{m \times n}$ (matrices).

Exercise

Write ``every invertible matrix has a nonzero determinant’’ using quantifiers and implication.
State the contrapositive of: ``if $\bA$ is invertible, then $\bA\bx = \bzero \Rightarrow \bx = \bzero$.’’
Let $S = \{1, 2, 3, 4\}$ and $T = \{3, 4, 5, 6\}$. Compute $S \cup T, S \cap T, S \setminus T$.

2.2 Proof Techniques

Definition: Direct Proof

Assume $P$ is true and derive $Q$ through a chain of valid logical steps.

Definition: Proof by Contradiction

Assume $\neg P$ and derive a logical contradiction ($R \wedge \neg R$). Proves $P$ must hold.

Definition: Proof by Induction

To prove $P(n)$ holds for all integers $n \geq n_0$:

Base case: Verify $P(n_0)$ directly.
Inductive step: Assume $P(k)$ and prove $P(k+1)$.

Tip

Numerical Proofs: Often validate that an approximation is stable or that an error term converges. Frequently involves showing $|f(x) - \hat{f}(x)| \leq \varepsilon$ for small $\varepsilon$.

Exercise

Prove: if $\bA$ and $\bB$ are symmetric, then $\bA + \bB$ is symmetric.
Prove by contradiction: if $\bA\bx = \bzero \Rightarrow \bx = \bzero$, then $\bA$ has no zero eigenvalue.
By induction, prove $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.

2.3 Notation Conventions

Tip

Scalars, Vectors, and Matrices.

Scalars: Lowercase italic ($a, b, x$).
Vectors: Lowercase bold ($\bx, \by, \ba$). Default is column vector.
Matrices: Uppercase bold ($\bA, \bB, \bQ$).
Indexing: 1-based (unlike Python). $x_i$ is $i$-th entry; $a_{ij}$ is $(i,j)$ entry.

Tip

Transpose and Inverse.

$\bA^T$: Transpose.
$\bA^{-1}$: Matrix inverse (square, nonsingular matrices).
$\bA^{-T}$: Transpose of the inverse $(\bA^{-1})^T$.
$\bA^k$: $k$-th power. $\bA^0 = \bI$.

Tip

Sums and Products. \[ \begin{align} \sum_{i=1}^{n} a_i = a_1 + ... + a_n, \qquad \prod_{i=1}^{n} a_i = a_1 ... a_n. \end{align} \]

Tip

Functions.

$f : \fR^n \to \fR^m$: Maps $n$-vectors to $m$-vectors.
$f \circ g$: Function composition $(f \circ g)(\bx) = f(g(\bx))$.

Tip

Asymptotic Notation. Scaling of algorithms is described using Big-O notation ($O(n^2), O(n^3)$). Details in the Computational Complexity section.