# ‌147Pm SAGA

## 2 2017-01-09T19:46:56; M590

### 2.1 Notation practice

1. For every $$x$$ there is a $$y$$ such that $$x < y$$ becomes

$\forall x \, \exists y \: | \: x < y$

For every $$\epsilon$$ there is a $$\delta$$ such that for every $$y$$

$if \: \left|x - y\right| \: < \delta \quad then \quad \left| f(x) - f(y) \right| \: < \: \epsilon$

becomes

$\forall \epsilon \, \exists \delta \, \forall y \, (\left|x - y \right| \: < \: \delta \rightarrow \left|f(x) - f(y)\right| \: < \: \epsilon)$

### 2.2 Axiomatic set theory

1. Equality

Two sets are equal if and only if they have the same elements. Moreover, equal elements belong to the same sets.

### 2.3 Mathematical Induction

1. The Well-Ordering Principle

Every nonempty set $$S$$ of nonnegative integers contains a least element; that is, there is some integer $$a$$ in $$S$$ such that $$a \leq b$$ for all $$b$$ 's belonging to $$S$$.

2. Proof: Let $$A$$ be a non-empty subset of $$\mathbb{N}$$. We wish to show that $$A$$ has a least element, that is, that there is an element $$a \in A$$ such that $$a \, \le \, n$$ for all $$n \in A$$. Do strong induction on the following predicate:

$$P(n)$$ : If $$n \, \in \, A$$, then $$A$$ has a least element.

Basic step: $$P(0)$$ is clearly true, since $$0 \le n$$ for all $$n \in \mathbb{N}$$.

Strong Inductive Step: We want to show that $$[P(0) \land P(1) \land \dots \land P(n)] \rightarrow P(n + 1)$$. Then suppose $$P(0), P(1), \dots, P(n)$$ are all true and that $$n + 1 \in A$$. Consider two cases:

3. $$\mathbb{Z}$$

Date: 2015-05-09 Sat 07:53

Created: 2017-01-10 Tue 08:09

Validate