CSci 271 Lecture Notes

Week Three, Wednesday: Sequences and Summations

Introduction

Sequences are used to represent ordered lists.

An infinite set is called countable if its elements can be listed. Such a set is also called countably infinite (to distinguish it from the uncountably infinite sets such as the set of real numbers).

Sequences

A sequence is a discrete structure used to represent an ordered list, a function from a subset of the integers to another set. The notation an, a term of the sequence, denotes the image of the integer n.

Examples 1, 2, and 3.

Summations

We introduce the summation notation, capital sigma. The summation is from a lower limit to an upper limit using the index of summation, which can be a part of the expression being summed.

Examples 4 through 10.

Cardinality

Sets A and B have the same cardinality iff there is a one-to-one correspondence from A to B. Recall that a one-to-one correspondence means the function mapping from A to B is both one-to-one and onto (also called a bijection).

Finite sets and infinite sets with the same cardinality as the set of natural numbers are called countable. Sets with some other cardinality are called uncountable (or uncountably infinite).

Example 11: show that the set of odd positive integers is countable.

Consider the function f(n) = 2n - 1 from N to the set of odd positive integers. It's one-to-one because f(x) = f(y) implies x = y for all x and y in the domain of F. It's onto because for each odd positive integer t we can find a natural number k such that t = f(k). Therefore we can list the odd positive integers in a sequence indexed by the natural numbers so the set of odd positive integers is countable by definition.

Example 12: Show that the set of real numbers is uncountable.

(see text)

Homework Assignment

Assigned Wednesday, September 23, due Wednesday, September 30, at beginning of class.

Chapter 1.5: 18.
Chapter 1.6: 4, 10.
Chapter 1.7: 4, 6.

This page established September 22, 1998; last updated September 23, 1998.