CHAPTER 1

The Real Number System

1.1 Sets and Operations on Sets

In this section, we shall define sets and operations on sets that the reader is already familiar with and will use standard notation. Examples are deemed not necessary for this section and have not been provided.

1.1D1 Definition: Sets

A set is a well defined collection of objects and can be described by listing its objects or elements and also may be defined as the collection of all elements x satisfying a given property. Thus the notation

A = {x} P(x)}

defines A to be the set of all elements x satisfying the condition P(x). This reads as "A equals the set of all elements x such that P(x)."

Notation:x [member of] A means that x is an element of the set A. x [not member of] A means that x is not an element of the set A.

We may also use the notation from A = {x member of]/P(x)} to mean that only the elements x from the set X are being used.

We will assume that the set of natural numbers or positive integers have already being defined. This set will be denoted by N or or {1, 2, 3, ...}.

We will also assume that the set of integers have already being defined. This set will be denoted by Z or {0, ± 1, ± 2, ± 3, ...}.

Furthermore, the set of rational numbers with the binary operations of addition and multiplication will be denoted by Q. We shall also assume all the properties of Q.

The set without any members is called the empty (or null) set and is denoted by Ø

1.1D2 Definition: Equality of Sets

Two sets A and B are said to be equal if every element of A is an element of B and every element of B is an element of A. In this case, we write A = B. A ≠ B means that the set A is not equal to the set B.

1.1D3 Definition: Subsets of Sets

A set A is said to be a subset of a set B or A is said to be contained in B if every element of A is also an element of B. In this case, we use the notation: A ⊆ B. If A ⊆ B and A ≠ B, then we say that A is a proper subset of B and use the notation A ⊂ B. Note that the empty set ∅ is a subset of any set A.

Note: A = B if and only if A ⊆ B and B ⊆ A.

1.1D4 Definition: Union, Intersection, and Complement of Sets

The union of sets A and B is the set of all elements that belong to A or B or both A and B and is denoted by A [union] B. Thus,

A [intersection] B = {x| x [member of] A or x [member of] B}.

The intersection of sets A and B is the set of all elements that belong to both A and B and is denoted by A [intersection] B. Thus,

A [intersection] B = {x | x [member of] A and x [member of] B}.

The relative complement of A in B or the complement of Arelative toB, denoted by B \ A is the set of all elements in B that are not elements of A. Thus

B \ A = x [member of] B | x [not member of] A.

If A is a subset of some fixed set X consisting of all the elements under consideration, then X \ A is referred to as the complement of A and is denoted by Ac. Thus

Ac = {x | x [not member of] A}.

1.1T1 Theorem: Distributive and DeMorgan's Laws

Let A, B, and C be sets. Then

(a) A [intersection] (B [union] C) = (A[intersection]B) [union] (A[intersection]C).

(b) A [union] (B[intersection]C) = (A[union]B) [intersection] (A[union]C).

(c) C \ (A [union]B) = (C\A) [intersection] (C\B).

(d) C \ (A [intersection]B) = (C\A) [union] (C\B).

(a) and (b) are referred to as the distributive laws, whereas (c) and (d) are known as DeMorgan Laws.

Proof: We will provide the proofs of (a) and (c). The proofs of (b) and (d) are left as an exercise.

(a) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This completes the proof of (a).

(c) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This completes the proof of (c).

1.1D5 Definition: The Power Set

Let A be a set. The set consisting of all the subsets of A is called the power set of A and is denoted by P(A). If a set has n elements, then its power set consists of 2n elements, i.e., the set has 2n subsets.

1.1D6 Definition: Cartesian Product

Let A and B be sets. Then the Cartesian product of A and B,, denoted by A × B, is the set of all ordered pairs (a, b), where the first component a is an element of A and the second component b is an element of B. Thus,

A × B = {a, b)| a [member of] A and b [member of] B}.

1.2 Relations and Functions

1.2D1 Definition: Relations and Functions

Let A and B be sets. Then a subset of the Cartesian product A × B is called a relation from A into B. If ρ is a relation from A into B, then the domain of ρ, denoted by Dom (ρ) is given by

Dom(ρ) = {a | (a,b) [member of] ρ}

The range of ρ, denoted by Ran (ρ), is given by

Ran (ρ){b|(a, b)[member of] ρ}.

A subset F of the Cartesian product A × B is called a function from A into B if the following condition is also satisfied:

(x, y1 [member of] F and (x, y2 [member of] F [right arrow] y1 = y2.

Notation: The domain and the range of F have already been defined because a function is also a relation. If F is a function and (x, y) [member of] F, then we may use the notation y = f (x), and may refer to the function as f or y = f(x) or simply f(x). If f is a function from A to (into) B, we say that f maps A to (into) B and use the notation: f : A [right arrow] B.

1.2D2 Definition: One-to-one and Onto Functions

Let f : A [right arrow]B. The function f is said to be onto if Ran(f) = B. In this case, we say that f is a function (mapping) from A onto B. The function f is said to be one-to-one (1-1) if the following condition is satisfied:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note: The function f is one-to-one if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

1.2D3 Definition: Image and Inverse Image

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(a) The image of E under f, denoted f(E), is given by

(b) The inverse image of H under f, denoted f-1 (H) is given by f-1 = {x [member of] H}

1.2D4 Definition: The Inverse Function

Let f: A [right arrow] B be 1-1. Then the inverse function of f, denoted by f-1, is the function: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The domain of f-1 is the range of f and the range of f-1 is the domain of f.

Note: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

1.2D5 Definition: Composition of Functions

Let f : A [right arrow] B and g : B [right arrow] C. Then the composition of g with f, denoted g ο f, is the function from A into C defined by

g ο f = {(x,z)|z = g(y) where y = f(x), x [member of]A}

The domain and range of g ο f are given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

1.2D6 Definition: The Identity Function

The identity function on a set A, is the function iA : A [right arrow] A given by

iA = {(x, x) | x [member of]A}.

This function is clearly one-to-one and onto.

1.2T1 Theorem:

f : A [right arrow] B be 1-1. Then

(a) f-1 ο f = iA

(b) f ο f-1 = iRam(f)

Proof:

(a) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(b) Similar to (a).

1.2A1 Assignment:

(a) Let f : A [right arrow] B and let C [subset or equal to] A. Prove that f [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and provide an example where f (A)\ f(C) ≠ f (A \ C).

(b) Let f : A [right arrow] B and g : B [right arrow] A satisfying: g ο f = iA. Show that f is one-to-one. Should f be onto? Justify!

(c) f : A [right arrow] B and g : B [right arrow] C are one-to-one functions. Prove that (g ο f)-1 = f-1 ο g-1 on Ran (g ο f).

(d) f : A [right arrow] B and g : B [right arrow] C are onto functions. Show that g ο f is onto.

1.3 Mathematical Induction

Mathematical induction is a useful tool in proving a statement, identity, or inequality involving the positive integer n. We will provide two versions of mathematical induction and the well-ordering principle in this section.

Note: The Well-Ordering Principle

Every nonempty subset of N has a smallest element. This statement is taken as an axiom for the natural numbers and may be restated as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

1.3T1 Theorem: The Principle of Mathematical Induction

Let Ρ(n) be a statement about n for each n [member of] N. Suppose

(a) Ρ (1) is true,

(b) Ρ (k + 1) is true whenever Ρ (k) is true, where k [member of] N.

Then Ρ(n) is true for all n [member of] N.

Proof: Suppose the conclusion is false, i.e., there exists n [member of] N such that Ρ(n) is false. Let

A = {k [member of] N | Ρ (k) is false.

The set A is a nonempty subset of the natural numbers and must have a smallest element, say m. Since Ρ (1) IS TRUE, m > 1. Since m is the smallest element of A, Ρ (m - 1) is true. But then (b) implies that Ρ (m) is true. This is a contradiction. Therefore, Ρ (n) is true for all n [member of] N.

1.3E1 Example:

Prove that: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all [n [member of] N

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is true. Suppose Ρ (k) is true, where k [member of] N. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, Ρ (k+1) is true. Therefore, by the principle of mathematical induction, Ρ(n) is true for all n [member of] N.

Note: If we change the hypothesis (a) in 1.3T1 to Ρ(m) is true, where m [member of] Z, then we have the Modified Principle of Mathematical Induction, stated as follows:

Let Ρ (n) be a statement about n for each n [member of] Z. Suppose

(a') Ρ (m) is true, where m [member] Z.

(b') Ρ (k + 1) is true whenever Ρ (k) is true, where k [member of] z, k ≥ m.

Then Ρ (n) is true for all n [member of] Z, n ≥ m

This is easily proved by defining a new statement: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

1.3E2 Example:

Prove that: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all n [member of] Z, n ≥ 3.

Let Ρ (n): [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all n [member of] Z, n ≥ 3.

Then Ρ(3): [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is true. Suppose Ρ(k) is true, where k [member of] Z, k ≥ 3. First we show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] . This follows easily because,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, Ρ(k + 1) is true. Therefore, by the modified principle of mathematical induction, Ρ (n) is true for all n [member of] N, n ≥ 3

1.3T2 Theorem: The Second Principle of Mathematical Induction

Let Ρ(n) be a statement about n for each n [member of] N. Suppose

(a) Ρ(1) is true

(b) Ρ(k + 1) is true whenever Ρ(1), Ρ(2), ..., Ρ(k) is true, where k [member of] N.

Then Ρ(n) is true for all n [member of] N.

Proof: Exercise.

1.3E3 Example: Let f: N [right arrow] N be defined by f (1) = 1, f (2) = 2, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all n [member of] N.

Prove that: 1 ≥ f (n) ≥ 2 for all n [member of] N.

Let Ρ(n): 1 ≥ f (n) ≥ 2 for all n [member of] N. Then Ρ(1), Ρ(2), ...., Ρ(k), Ρ(k + 1) are true. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus, Ρ(k + 1) is true. Therefore, by the second principle of mathematical induction, Ρ(n) is true for all n [member of] N.

1.3A1 Assignment:

(a) Use the principle of mathematical induction to prove that:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(b) Use the modified principle of mathematical induction to prove that:

n! > 2n for all n [member of] 4.

(c) Let f: N [right arrow] N be defined by f (1), f (2) = 4, and f (n + 2) = 2f (n + 1) - f (n) + 2 for all n [member of] N.

Determine a formula for f(n) and use induction to prove your conclusion.

1.4 The Real Number System

In this section, we will consider the concept of the least upper bound of an ordered field and introduce the real number system with its various properties.

1.4D1 Definition: Field

A field is a set F with at least two distinct elements along with two binary operations, addition (+) and multiplication (.), which satisfy the following eleven (11) axioms for addition and multiplication:

(A1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(A2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(A3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(A4) There exists 0 [member of] F such that a + 0 = a for all a [member of] F; 0 is called the additive identity or zero.

ion (.), which satisfy the following eleven (11) axioms for addition and multiplication:

(A1) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(A2) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(A3) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(A4) There exists 0 [member of] F such that a + 0 = a for all a [member of] F; 0 is called the additive identity or zero.