#math/analysis #TODO ## Number Systems We use $ \mathbb N=\{1,2,3,\ldots\}, \qquad \mathbb Z=\{\ldots,-2,-1,0,1,2,\ldots\}, \qquad \mathbb Q=\left\{\frac mn:m\in\mathbb Z,\ n\in\mathbb Z\setminus\{0\}\right\}. $ Thus $0\notin\mathbb N$. ## Sets $x\in A$ means that $x$ is an element of $A$. `Set-builder notation` $ \{x\in A:P(x)\} $ denotes the set of all $x\in A$ for which $P(x)$ is true. The `empty set` $\varnothing$ has no elements; in particular, $0\notin\varnothing$. A `singleton` $\{x\}$ has exactly one element. $A$ is a `subset` of $B$ when every element of $A$ belongs to $B$: $ A\subseteq B \quad\Longleftrightarrow\quad \forall x\,(x\in A\Rightarrow x\in B). $ This text also writes $A\subset B$ for $A\subseteq B$; equality is allowed. A `proper subset` is written $A\subsetneq B$. Subset inclusion is transitive, and the empty set is a subset of every set: $ A\subseteq B\subseteq C\Rightarrow A\subseteq C, \qquad \varnothing\subseteq A. $ Membership and inclusion are distinct: $1\in\mathbb N$, whereas $\{1\}\subseteq\mathbb N$. Two sets are equal exactly when each contains the other: $ A=B\quad\Longleftrightarrow\quad A\subseteq B\text{ and }B\subseteq A. $ For sets $A$ and $B$: | Construction | Definition | |---|---| | `union` | $A\cup B=\{x:x\in A\text{ or }x\in B\}$ | | `intersection` | $A\cap B=\{x:x\in A\text{ and }x\in B\}$ | | `difference` | $A\setminus B=\{x:x\in A\text{ and }x\notin B\}$ | | `symmetric difference` | $A\mathbin{\triangle}B=(A\setminus B)\cup(B\setminus A)$ | Here “or” is inclusive. The sets $A$ and $B$ are `disjoint` when $A\cap B=\varnothing$. A `class` is a collection of sets. A class $\mathcal A$ is a `subclass` of $\mathcal B$ when every set in $\mathcal A$ also belongs to $\mathcal B$. Class membership must not be confused with subset inclusion. For example, let $ \mathcal S=\{\{n\}:n\in\mathbb N\}, \qquad \mathcal D=\{\{m,n\}:m,n\in\mathbb N,\ m\ne n\}. $ Then $\mathcal S\not\subseteq\mathcal D$, although each member of $\mathcal S$ is a subset of some member of $\mathcal D$. ## Equivalence Relations An `equivalence relation` on a set $S$ is a relation $\sim$^[We read $s\sim s'$ as "s is related to s-prime" or "s is equivalent to s-prime." ] satisfying, for all $s,s',s''\in S$, $ \begin{aligned} s&\sim s &&\text{(reflexivity)},\\ s\sim s'&\Rightarrow s'\sim s &&\text{(symmetry)},\\ s\sim s'\text{ and }s'\sim s''&\Rightarrow s\sim s'' &&\text{(transitivity)}. \end{aligned} $ The `equivalence class` of $s$ is $ [s]=\{s'\in S:s'\sim s\}. $ $s$ is a `representative` of $[s]$. Any two equivalence classes are either equal or disjoint, and their union is $S$; equivalence classes therefore partition $S$. ![[Pasted image 20261003183156.png|300]] > [!Example] > On $\mathbb Z$, define $m\sim n$ when $3\mid(m-n)$. The equivalence classes are > $ > [0]=\{\ldots,-3,0,3,\ldots\},\quad > [1]=\{\ldots,-2,1,4,\ldots\},\quad > [2]=\{\ldots,-1,2,5,\ldots\}. > $ > Every integer lies in exactly one class. Since $4\in[1]$, the representatives $1$ and $4$ determine the same class: $[1]=[4]$. jjjj ## Logic The principal symbols are^[We should say "for each" rather than "for all" with respect to $\forall \:{}$] $ \forall\ \text{“for each”}, \qquad \exists\ \text{“there exists”}, \qquad \Rightarrow\ \text{“implies”}, \qquad \neg\ \text{“not”}. $ Place quantifiers before the variables they bind and assertions after them. A quantifier governs only what follows it, so its position and scope are essential. ### Example: Mixing moral quantifier orderings A `prime` is an integer greater than $1$ whose only positive divisors are $1$ and itself. Let $P$ be the set of primes. The statement “each integer is smaller than some prime” is $ \forall n\in\mathbb Z\ \exists p\in P:\ n<p. $ Quantifier order changes meaning. The statement $ \forall n\in\mathbb N\ \forall m\in\mathbb N\ \exists p\in P:\ nm<p $ is true because $p$ may be chosen after $n$ and $m$. In contrast, $ \forall n\in\mathbb N\ \exists p\in P\ \forall m\in\mathbb N:\ nm<p $ is false: taking $n=1$, no fixed prime exceeds every $m$. ### Logical Operators In mathematics, $a\lor b$ ($a\text{ or }b$) is inclusive: it permits either statement or both. An `implication` $a\Rightarrow b$ asserts only that truth of $a$ forces truth of $b$; it does not assert $b\Rightarrow a$. The symbol $\equiv$ denotes `logical equivalence`. The fundamental rules are $ \begin{aligned} \neg\neg a&\equiv a,\\ \neg(a\land b)&\equiv \neg a\lor\neg b,\\ \neg(a\lor b)&\equiv \neg a\land\neg b,\\ a\Rightarrow b&\equiv \neg b\Rightarrow\neg a\equiv\neg a\lor b,\\ \neg(a\Rightarrow b)&\equiv a\land\neg b. \end{aligned} $ For example, $ \neg(m<n)\equiv m\ge n, \qquad \neg(x\in A)\equiv x\notin A. $ To negate a quantified statement, exchange every $\forall$ with $\exists$, preserve their order, and negate the final assertion: $ \begin{aligned} \neg(\forall x\in X:P(x))&\equiv\exists x\in X:\neg P(x),\\ \neg(\exists x\in X:P(x))&\equiv\forall x\in X:\neg P(x). \end{aligned} $ Thus $ \neg\bigl(\forall n\in\mathbb N\ \exists p\in P:\ n<p\bigr) \equiv \exists n\in\mathbb N\ \forall p\in P:\ n\ge p. $ ## Proof A `theorem` has the form $a\Rightarrow b$, where $a$ is the `hypothesis` and $b$ is the `conclusion`. Standard methods are: - `Direct proof`: assume $a$ and derive $b$. - `Contrapositive`: assume $\neg b$ and derive $\neg a$. - `Contradiction`: assume $a\land\neg b$ and derive an impossibility, denoted $\unicode{x21af}$. Classical arguments use the `law of excluded middle`: every proposition is either true or false, but not both. > [!Example] Infinitely many primes > Suppose the primes are $p_1,\ldots,p_k$ and set $N=p_1\cdots p_k+1$. Division of $N$ by any $p_i$ leaves remainder $1$, so none of the listed primes divides $N$. Yet every integer at least $2$ has a prime divisor. This contradiction proves that the set of primes is infinite. ## Advice on Proofs 1. Name each object that appears in your proof. (For instance, you might begin your proof with a phrase, “Consider a set $X$, and elements $x,y$ that belong to $X$,” etc.) 2. Draw a diagram that captures how these objects relate, and extract logical statements from it. Quantifiers precede the objects quantified; see below. 3. Become confident that the mathematical assertion you are trying to prove is really true before trying to write down a proof of it. If there a specific function involved—say $\sin x^\alpha$—draw the graph of the function for a few values of $\alpha$ before starting any $\epsilon,\delta$ analysis. Belief first and proof second. 4. Proceed step by step, each step depending on the hypotheses, previously proved theorems, or previous steps in your proof. 5. Check for “rigor”: All cases have been considered, all details have been tied down, and circular reasoning has been avoided. 6. Before you sign off on the proof, check for counterexamples and any implicit assumptions you made that could invalidate your reasoning. We will try to apply real-world intuition with respect to our ideas in mathematics.