Discrete Mathematics (H) Lecture 5 Notes

Basic Discrete Mathematics Objects (Continued)

Sequence

Definitions and Notations

Definition: Sequence

A sequence is a function from a subset of the set of integers to a set . We use the notation to denote the image of the integer , and represents the ordered list .

Definition: Arithmetic Progression

An arithmetic progression is a sequence of the form , where the initial term and common difference are real numbers.

Definition: Geometric Progression

A geometric progression is a sequence of the form , where the initial term and the common ratio are real numbers.

Definition: Recursively Defined Sequences

The -th element of the sequence is defined recursively in terms of the previous elements of the sequence and the initial elements of the sequence.

Example

• Arithmetic progression:
• Geometric progression:
• Recursively defined sequence:

Summations

Definition: Summation of Sequences

The summation of the terms of a sequence is The variable is referred to as the index of summation and the choice of the letter is arbitrary. is the lower limit of the summation, and is the upper limit of the summation.

Two useful properties of summations:

The sum of the first terms of the arithmetic progression is The sum of the first terms of the geometric progression is

Example

• Solution 1
• Solution 2
• Solution 3
• Solution 4
• Solution 5

Solution 1. Using the summation formula for the arithmetic progression:

Solution 2. Again, using the summation formula for the arithmetic progression:

Solution 3. The inner sum for fixed is Then

Solution 4. Using the summation formula for the geometric progression:

Solution 5. The inner sum for fixed is Then the outer sum is

Infinite Series

Infinite geometric series can be computed in the closed form for :

Some Useful Summation Formulas

Sum	Closed Form

• Proof 1
• Proof 2
• Proof 3
• Proof 4
• Proof 5
• Proof 6

Proof for formula 1. Let , then , then

Proof for formula 2. A useful trick is the write the sum twice, once in increasing order and once in decreasing order Adding both expressions:

Proof for formula 3. We use the telescoping method. Consider the identity And we write this for Adding all these equations up, we get Substitute : Simplify the equation we get

Proof for formula 4. We can notice that

Then we only need to calculate :

Proof for formula 5.

Proof for formula 6. Notice that Then the closed form is

Cardinality of Sets, Redux

Definition: Cardinality (Continued)

The sets and have the same cardinality if there is a one-to-one correspondence between elements in and .

If there is a one-to-one function from to , the cardinality of is less than or the same as the cardinality of , denoted by . Moreover, when and and have different cardinalities, we say that the cardinality of is less than the cardinality of , denoted by .

Cantor-Bernstein Theorem

Assume are two (possibly infinite) sets, then

Proof. If and are both finite, then the proof is trivial. If and are both infinite. ### Countable Sets

Definition: Countable Sets

A set that is either finite or has the same cardinality as the set of positive integers is called countable. A set that is not countable is called uncountable.

Example

Prove that the set of even numbers is countable.

Proof. We define a function , then we need to prove is a bijection: - Injective: If , then . - Surjective: is the preimage in .

Theorem

The set of integers is countable.

Proof. We can list a sequence: or define a bijection from to :

Theorem

The set of (positive) rational numbers is countable.

Proof. We construct a list by first list all with , then list all with , etc.

Lemma

If is a countable set, then is also a countable set.

Theorem

The set of finite string over a finite alphabet is countably infinite. (Assume an alphabetical ordering of symbols in )

Proof. We show that the strings can be listed in a sequence by follows:

1. First list all the strings of length in alphabetical order,
2. then all the strings of length in lexicographic order,
3. etc.

This implies a bijection from to .

Uncountable Sets

Theorem

The set of real numbers is uncountable.

Proof. Assume that is countable, then every subset of is countable, in particular, the interval is countable. This implies that the elements of this set can be listed as , where all . We want to show that not all read numbers in the interval are in the list. We do this by form a new number called , where if , and if . We claim that is different from each number in the list. Each expansion is unique, if we exclude an infinite string of ’s. and differ in the -th decimal place for all . This proof method is the famous Cantor diagonalization argument.

Theorem

The set is uncountable.

Proof. Assume that is countable. This implies that the elements of this set can be listed as , where , and each can be uniquely by the bit string , where if and if . Then we can construct the list with all . We form a new set called , where if , and if . We claim that is different from each set in the list. Each bit string is unique, and and differ in -th bit for all .

Computable vs. Uncomputable

Definition: Computability

We say that a function is computable (or Turing-computable) if we can use a Turing machine to find the values of this function. If a function is not computable, we say it is uncomputable. Intuitively, a function is computable if there is a computer program that finds the values of this function.

Theorem

There are functions that are not computable.

Proof. Since we know that the set of finite strings on finite alphabet is countable, it is trivial to prove that the set of computer programs is countably finite. To prove this theorem, we only need to prove the set of functions is uncountable. We assume that the set of functions is countable, then the set of functions from to the set is countable. This implies we can list all the functions in the set as a sequence We define a new function We claim that is different from all functions in the sequence. We prove this by contradiction. Assume that for some , then This is a contradiction, since . So the set of functions is uncountable.

Cantor’s Theorem

Theorem

If is a set, then .