Chapter 0

Question 1

Well Ordering Principle

Answer 1

Every nonempty set of positive integers contains a smallest member.

Question 2

Division Algorithm

Answer 2

Let a and b be integers with b > 0. Then there exist unique integers q and r for which a = bq + r and
0 ≤ r < b.

Question 3

GCD is a linear combination

Answer 3

For any nonzero integers a and b, there exist integers
s and t for which gcd(a,b) = as + bt.

Furthermore, gcd(a,b) is the smallest positive integer of the form as + bt.

Question 4

Euclid’s Lemma

Answer 4

For prime p, p | ab (integer a and b) implies

p | a or p | b.

Question 5

Fundamental Theorem of Arithmetic

Answer 5

Every integer greater than 1 is a prime or a product of primes. This product is unique, except for the order in which factors appear.

Question 6

First Principle of Mathematical Induction

Answer 6

Let S be a set of integers containing a. Suppose that S has the property that whenever some integer n ≥ a belongs to S, then the integer n + 1 also belongs to S. Then S contains every integer greater than or equal to a.

Question 7

Second Principle of Mathematical Induction (Strong Form)

Answer 7

Let S be a set of integers containing a. Suppose that S has the property that whenever some integer n ≥ a belongs to S, then every integer less than n and greater than a also belongs to S. Then S contains every integer greater than or equal to a.

Question 8

Equivalence relation to a set S

Answer 8

A set R of ordered pairs of elements of S such that

(1) (a,a) ∈ R for all a in S (reflexive property).
(2) (a,b) ∈ R implies (b,a) ∈ R for all a, b in S (symmetric property).
(3) (a,b) ∈ R and (b,c) ∈ R imply (a,c) ∈ R
for all a, b, c in S (transitive property).

Question 9

Equivalence class (of a set S containing a)

Answer 9

[a]={x ∈ S | x ~ a}

Question 10

Partition of a set S

Answer 10

A collection of nonempty disjoint subsets of S whose union is S

Question 11

Equivalence Classes Partition

Answer 11

The equivalence classes of an equivalence relation on a set S constitute a partition of S. Conversely, for any partition P of S, there is an equivalence relation on S whose equivalence classes are the elements of P.

Question 12

Function (mapping) φ from set A (domain) to set B (range)

Answer 12

A rule that assigns to each element a of A exactly one element b of B.

Question 13

Image of A under φ: A→B

Answer 13

The set of images of all elements of A, i.e., {φ(a) | a ∈ A}

Question 14

Composition of functions ψφ

Answer 14

Given φ: A→B and ψ: B→C, the mapping from A to C defined by (ψφ)(a) = ψ(φ(a)).

Question 15

One-to-one (pertains to function φ: A→B)

Answer 15

Having the property that for every a,b ∈ φ, φ(a) = φ(b) implies a = b.

Question 16

Onto (pertains to function φ: A→B)

Answer 16

Having the property that for every b ∈ B, there exists at least one a ∈ A for which φ(a) = b .

Question 17

properties of functions

Answer 17

Given functions α:A→B, β:B→C, γ:C→D. Then

(1) (γβ)α = γ(βα) (associativity).
(2) If α and β are one-to-one, so is βα.
(3) If α and β are onto, so is βα.
(4) If α is one-to-one and onto, then there is a function α-1 from B onto A such that (α-1α)(a) = a for all a in A and (αα-1)(b) = b for all b in B.