# MATH 409 Lecture 5

« previous | *Tuesday, September 10, 2013* | next »

## Review

## Inductive Definition

Now we can use induction to define structures recursively. For example,

- The power of a number is , where .
- Factorial is , where .
- Fibonacci numbers: , where .

## Binomial Coefficients

For any integers , we define the **binomial coefficient** ( choose ) by

If , then

" choose " refers to the fact that is the number of all -element subsets of an -element set.

**Lemma.** A helpful recursive form

*Proof.*

### Pascal's Triangle

The lemma formula above allows us to compute coefficients recursively. The results are usually formatted in a triangular array called **Pascal's Triangle**, where is the ^{th} number in the ^{th} row of the triangle. (numbering starts from 0)

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1

### Binomial Expansion

**Theorem.** For any and ,

*Proof by induction.* *Basis.* In the case , the formula is trivial.

*Induction.* Assume that the formula holds for a particular value of . Then

Which completes the induction step.

## Functions

*(See MATH 409 Lecture 4#Functions→)*

### Composition

The **composition** of functions and is a function from to denoted , that is defined by for .

#### Properties

- If and are one-to-one (injective), then composition is also one-to-one. (converse is not necessarily true; if is injective, then we only know that is injective)
- Similarly, if and are onto (surjective), then the composition is also onto. (converse is not necessarily true; if is surjective, then we only know that is surjective)
- and are bijective if and only if their composition is bijective
- If and are invertible, then their composition is also invvertible, and
- If denotes the identity function on set , then for any function.
- for any functions and , we have iff and

### Images and Preimages

Given a function , the **image** of a set under , denoted is a subset of defined by .

The **preimage** (or **inverse image**) of a set under , denoted , is a subset of defined by

**Remark:** If the function is invertible, then the pre-image is also the image of under the inverse function . However, is well-defined even if is not invertible.

#### Properties

- ,
- Same as previous for and

### Cardinality

Given two sets and , ew say that is of the same **cardinality** as if there exists a bijective function . Notation: .

**Theorem.** The relation "is of the same cardinality as" is an equivalence relation. In other words, it is:

**reflexive**()**symmetric**( implies ), and**transitive**( and implies )

*Proof.* Since bijective functions show that two sets are of the same cardinality,

**Reflexivity:**The identity map is bijective.**Symmetry:**If is a bijection of onto , then the inverse map is a bijection of onto .**Transitivity:**If and are bijections, then the composition is a bijection of .

## Countable and Uncountable Sets

A nonempty set is **finite** if it is of the same cardinality as for some . Otherwise, it is **infinite**.

An infinite set is called **countable** (or **countably infinite**) if it is of the same cardinality as . Otherwise it is **uncountable** (or **uncountably infinite**).

An infinite set is countable if it is possible to arrange all elements of into a single sequence (an infinite list) .

### Countable Sets

Examples:

- (natural numbers)
- (even numbers)
- (integers)
- (pairs of natural numbers)
- (rational numbers, extension of above)
- Algebraic Numbers (roots of nonzero
^{[1]}polynomials with integer coefficients)

The last bullet will be a problem on the next homework, and the hint is to count the number of polynomials first then count the roots. The third property below will also be useful

#### Properties

- Any infinite set contains a countable subset
- Any infinite subset of a countable set is also countable.
- The union of any finite or countable sets is also finite or countable

### Uncountable Sets

**Theorem.** The set is uncountable.

*Proof.* It is enough to prove that the interval is uncountable. Assume the contrary. Then all numbers from can be arranged into an infinite list . Any number admits a decimal expansion of the form , where each digit is in . In particular,

Now for any , choose a decimal digit such that and is neither nor . Then is the decimal expansion of some number . By construction, it is different from all expansions in the list. Although some real numbers admit two decimal expansions (e.g. ), the condition ensures that is not such a number. Thus is not listed. CONTRADICTION!

## Footnotes

- ↑ Not identical to zero, but it can cross the -axis