# MATH 409 Lecture 4

« previous | *Thursday, September 5, 2013* | next »

## Solutions to Challenges

### Challenge 2

Construct a strict linear order on the set such that implies for all

Given complex numbers and , where and . Define if:

- and
- and

### Challenge 3

Construct a strict linear order on of rational functions in variable with real coefficients that makes into an ordered field.

Given rational functions , we let if there exists such that for all .

Showing strict order is easy, and verifying axioms of addition and multiplication is also easy. Hard part is proving linearity:

Assume and let . Then , where and are nonzero polynomials. Since any nonzero polynomial has only finitely many roots, there exists such that and have no roots in the interval . is continuous and nowhere zero on . Therefore it maintains its sign on this interval, i.e. either for all or for all . In the first case, . In the second case, .

**Note:**This field does not follow the Archimedean principle

## General Intervals

Suppose is a stet endowed with a strict linear order .

A subset is called an **interval** if with any two elements it contains all elements of that lie between them. To be precise, and imply that for all .

Examples:

- The empty set and all one-element subsets of are trivially intervals.
- Open finite interval , where and .
- Closed and semi-open intervals
- Open semi-infinite intervals
- , where .

- Closed semi-infinite intervals
- Complete infinite interval

### Intervals of the Real Line

**Theorem 1.** Suppose is a bounded interval of that consists of more than one point. Then there exist with such that or or , or .

**Theorem 2.** Suppose is an interval of bounded above but unbounded below. Then such that or .

**Theorem 3.** Suppose is an interval of bounded below but unbounded above. Then such that or .

**Theorem 4.** Suppose is an interval of that is neither bounded above nor bounded below. Then .

**Note:**Next challenge: Prove theorems 1 and 4

## Natural Numbers, Integers, and Rationals

A set is called **inductive** if and, for any real number , implies . The set of **natural numbers** is the smallest inductive subset of .

**Note:**The set is well defined. Namely, it is the intersection of all inductive subsets of .

**Integers** are defined as

**Rationals** are defined as

### Properties of Natural Numbers

- 1 is the least natural number: the interval is an inductive set. Hence .

- If , then : Let be set of all such that . Then as . Besides, for any we have so that . Therefore is an inductive set. Then , which implies that .

- If , then the open interval contains no natural numbers: Let be the set of all such that . Then as . Now assume and take any . We have since , and since . By the above, . Thus is an inductive set, which implies .

### Principle of Well-Ordering

Suppose is a set endowed with a strict linear order . We say that a subset is **well-ordered** with respect to if any nonempty subset of has a least element.

**Theorem.** The set is well-ordered with respect to the natural ordering of the real line .

*Proof.* Let be an arbitrary nonempty subset of . The set is bounded below since 1 is a lower bound of . Therefore exists. Since is a lower bound of while is not, we can find such that . As shown before, the interval is disjoint from . Then is disjoint from , which implies that is a lower bound of . Hence , so by weak antisymmetry. Thus is the least element of .

### Principle of Mathematical Induction

**Theorem.** Let be an assertion depending on a natural variable . Suppose that

- holds,
- whenever holds, so does .

Then holds for all .

*Proof.* Let be the set of all natural numbers such that holds. Clearly is an inductive set. Therefore which implies that .

**Note:**The assertion is called the

**basis of induction**. The implication is called the

**induction step**.

Examples of assertions :

- is divisible by 6
- for some

We can use mathematical induction for by starting with a different (shifted) base.

### Strong Induction

**Theorem.** Let be an assertion depending on a natural variable . Suppose that holds whenever holds for all natural . Then holds for all .

In other words, for , the assuption of the theorem means that holds unconditionally. For , it means that implies . For , it means that and imply . And so on...

*Proof.* For any we define a new assertion " holds for any natural ". Then is equivalent to , in particular, it holds. By assumption implies for any . Moreover, holds if and only if both and hold. Therefore implies for all . By the principle of mathematical induction, holds for all and thus holds as well.

## Functions

A **function** (or **map**) is an assignment: to each we assign an element .

The **graph** of the function is defined as the subset of consisting of all pairs of the form for . Two functions are considered the same if their graphs coincide

### Properties

A function is **surjective** (or **onto**) if for each , there exists at least one such that .

The function is **injective** (or **one-to-one**) if implies . This can be tested with a horizontal line on graph: for all horizontal lines, the graph of should intersect only once.

A function is **bijective** if and only if it is both injective and surjective.

### Inverse Function

Suppose we have two functions and . We say that is the **inverse function** of (denoted ) if if and only if for all and .

**Theorem 1.** The inverse function exists if and only if is bijective

**Theorem 2.** A function is an inverse function of a function if and only if for all and for all .