Chapter 2

Question 1

4 characteristics of natural numbers [axiom]

Answer 1

1. If a, b ∈ N, then a + b ∈ N .
   (The subset N is closed under addition.)
2. If a, b ∈ N, then ab ∈ N .
   (The subset N is closed under multiplication.)
3. 0 ∉ N .
4. For every a ∈ Z, we have
   a ∈ N
   or a = 0
   or -a ∈ N.

Question 2

order on the intergers [definition]

Answer 2

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.

Question 3

transitivity of <

Answer 3

Suppose a, b, c ∈ Z.
If a < b and b < c ,
then a < c
(ie the relation < is transitive).

Question 4

N has no largest element [proposition]

Answer 4

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

Question 5

notation for “A is a subset of B” [notation]

Answer 5

“A is a subset of B”
can be written
A ⊆ B .

Question 6

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

Answer 6

A = B
can be expressed as
A ⊆ B and B ⊆ A
or
x ∈ A ⇔ x ∈ B .

Question 7

notation for “ P ⇒ Q and Q ⇒ P” [notation]

Answer 7

P ⇒ Q and Q ⇒ P
can be expressed as
P ⇔ Q .

Question 8

difference between ⊈ and ⊊ [notation]

Answer 8

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

Question 9

notation for all intergers satisfying a given property [notation]

Answer 9

{n ∈ Z : some property of n}

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

Question 10

induction [axiom]

Answer 10

(i) 1 ∈ A ,
(ii) n ∈ A ⇒ n + 1 ∈ A .

Then N ⊆ A .

Question 11

principle of mathematical induction - first form [theorem]

Answer 11

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.

Question 12

priciple of mathematical induction - first form revisited [theorem]

Answer 12

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 .

Question 13

smallest and greatest elements [definition]

Answer 13

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).

Question 14

well-ordering principle [theorem]

Answer 14

Every nonempty subset of N has a smallest element.

Question 15

gcd [definition]

Answer 15

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

we define

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