4 characteristics of natural numbers [axiom]

###
- If a, b ∈ N, then a + b ∈ N .

(The subset N is closed under addition.)

- If a, b ∈ N, then ab ∈ N .

(The subset N is closed under multiplication.)

- 0 ∉ N .

- For every a ∈ Z, we have

a ∈ N

or a = 0

or -a ∈ N.

(The subset N is closed under addition.)

(The subset N is closed under multiplication.)

a ∈ N

or a = 0

or -a ∈ N.

order on the intergers [definition]

For a, b ∈ Z, we write

a < b (and say a is less than b)

or b > a (and say b is greater than a,

if and only if **(b - a) ∈ N** .

We write a ≤ b (and say a is less than or equal to b)

or b ≥ a (and say b is greater than a)

if and only if **a < b or a = b **.

transitivity of <

Suppose a, b, c ∈ Z.

If a < b and b < c ,

then a < c

(ie the relation < is transitive).

N has no largest element [proposition]

For each a ∈ N, there exists b ∈ N such that b > a .

notation for "A is a subset of B" [notation]

"A is a subset of B"

can be written

A ⊆ B .

notation for "A = B" (ie the two sets A and B are equal) [notation]

A = B

can be expressed as

A ⊆ B and B ⊆ A

or

x ∈ A ⇔ x ∈ B .

notation for " P ⇒ Q and Q ⇒ P" [notation]

P ⇒ Q and Q ⇒ P

can be expressed as

P ⇔ Q .

difference between ⊈ and ⊊ [notation]

A ⊈ B

means that A is not a subset of B, ie at least one element of A is not an element of B

A ⊊ B

means that A is a subset of B, but at least one element of B is not in A; can also be expressed as

A ⊆ B and A ≠ B

notation for all intergers satisfying a given property [notation]

{n ∈ Z : some property of n}

ex: {n ∈ Z : n > 69} denotes the set of all intergers greater than 69.

induction [axiom]

(i) 1 ∈ *A* ,

(ii) *n* ∈ *A* ⇒ *n* + 1 ∈ A .

Then **N** ⊆ A .

principle of mathematical induction - first form [theorem]

Suppose that, for each *k* ∈ **N**, we have a statement P(*k*) , and that ...

(i) P(1) is true, and

(ii) for all *n* ∈ **N**, P(*n*) ⇒ P(*n* + 1) .

Then P(*k*) is true for all *k* ∈ N.

priciple of mathematical induction - first form revisited [theorem]

Suppose that m is a fixed integer,

and that for each k ∈ Z with k ≥ m , we have a statement P(*k*) ,

and that...

(i) P(*m*) is true, and

(ii) for all *n* ≥ *m *, P(*n*) ⇒ P(*n* + 1) .

Then P(k) is true for all k ≥ m .

smallest and greatest elements [definition]

Suppose *A* ⊆ **Z** is nonempty.

If there exists *m* ∈ *A* such that *m* ≤ *a* for all *a* ∈ *A*,

then we say *m* is a smallest element of *A*

and write *m* = min(*A*).

If there exists *M* ∈ *A* such that *M* ≥ a for all *a* ∈ *A*,

then we say *M* is a greatest element of *A*

and write *M* = max(*A*).

well-ordering principle [theorem]

Every nonempty subset of **N** has a smallest element.

gcd [definition]

Suppose *a*, *b* ∈ **Z**. If *a* and *b* are not both zero,

we define

gcd(*a*, *b*) = min ({*k* ∈ **N** : *k* = a*x* + b*y* for some *x* , *y* ∈ **Z**} )