DM-05

Course 5

Sequences and Cardinality

Master sequences, summations, and the theory of infinite sets. Learn to compare the sizes of infinite sets and understand the profound distinction between countable and uncountable infinities.

Learning Objectives

Understand sequences and their representations
Apply summation formulas for arithmetic and geometric series
Solve basic recurrence relations
Define and compare cardinalities of sets
Prove sets are countable or uncountable
Apply Cantor's diagonalization argument

1. Sequences

Definition 5.1: Sequence

A sequence is an ordered list of elements. Formally, a sequence is a function from a subset of integers (usually $\mathbb{N}$ or $\mathbb{Z}^+$ ) to a set $S$ .

We write $\{a_n\}$ or $a_1, a_2, a_3, \ldots$ to denote a sequence.

$a_n$ is called the n-th term of the sequence
The sequence may be finite or infinite

Example: Common Sequences

Arithmetic Sequence:

$a_n = a_1 + (n-1)d$ where $d$ is the common difference

Example: 2, 5, 8, 11, 14, ... (d = 3)

Geometric Sequence:

$a_n = a_1 \cdot r^{n-1}$ where $r$ is the common ratio

Example: 3, 6, 12, 24, 48, ... (r = 2)

Fibonacci Sequence:

$F_n = F_{n-1} + F_{n-2}$ with $F_1 = F_2 = 1$

1, 1, 2, 3, 5, 8, 13, 21, ...

Definition 5.2: Recurrence Relation

A recurrence relation defines each term of a sequence in terms of previous terms.

To fully specify a sequence, a recurrence relation must be paired with initial conditions.

2. Summations

Definition 5.3: Summation Notation

The summation (or sigma notation) represents the sum of terms:

\sum_{i=m}^{n} a_i = a_m + a_{m+1} + \cdots + a_n

Here $i$ is the index of summation, $m$ is the lower bound, and $n$ is the upper bound.

Theorem 5.1: Summation Formulas

Sum of first n positive integers:

\sum_{i=1}^{n} i = \frac{n(n+1)}{2}

Sum of squares:

\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}

Sum of cubes:

\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2

Geometric series:

\sum_{i=0}^{n} r^i = \frac{r^{n+1} - 1}{r - 1} \text{ for } r \neq 1

Proof of Sum of first n integers

Let $S = 1 + 2 + \cdots + n$ .

Write the sum forwards and backwards:

$S = 1 + 2 + 3 + \cdots + n$

$S = n + (n-1) + (n-2) + \cdots + 1$

Adding column by column:

$2S = (n+1) + (n+1) + \cdots + (n+1) = n(n+1)$

Therefore, $S = \frac{n(n+1)}{2}$ .

∎

Example: Evaluating Sums

Problem: Evaluate $\sum_{i=1}^{100} i$

Solution:

$\sum_{i=1}^{100} i = \frac{100 \cdot 101}{2} = \frac{10100}{2} = 5050$

3. Cardinality of Sets

Definition 5.4: Cardinality

The cardinality of a set $A$ , denoted $| A |$ , is a measure of the "size" of the set.

Two sets $A$ and $B$ have the same cardinality, written $|A| = |B|$ , if there exists a bijection $f: A \to B$ .

Definition 5.5: Countable Sets

A set is countably infinite if it has the same cardinality as $\mathbb{N}$ .

A set is countable if it is either finite or countably infinite.

The cardinality of $\mathbb{N}$ is denoted $\aleph_0$ (aleph-null).

Theorem 5.2: Countable Sets

The following sets are countably infinite:

$\mathbb{Z}$ (integers)
$\mathbb{Q}$ (rational numbers)
$\mathbb{N} \times \mathbb{N}$ (pairs of natural numbers)
Any countable union of countable sets

Proof of ℤ is countable

Define $f: \mathbb{N} \to \mathbb{Z}$ by:

f(n) = \begin{cases} n/2 & \text{if } n \text{ is even} \\ -(n+1)/2 & \text{if } n \text{ is odd} \end{cases}

This gives the enumeration: 0, -1, 1, -2, 2, -3, 3, ...

Since f is a bijection, $| \mathbb{N} | = | \mathbb{Z} |$ .

∎

4. Uncountable Sets

Definition 5.6: Uncountable

A set is uncountable if it is infinite but not countably infinite (i.e., no bijection with $\mathbb{N}$ exists).

Theorem 5.3: Cantor's Theorem

The set of real numbers $\mathbb{R}$ is uncountable. In fact, the interval $(0, 1)$ is uncountable.

Proof of Cantor's Diagonalization

Assume for contradiction that $(0, 1)$ is countable.

Then we could list all reals in $(0, 1)$ :

$r_1 = 0.d_{11}d_{12}d_{13}d_{14}\ldots$

$r_2 = 0.d_{21}d_{22}d_{23}d_{24}\ldots$

$r_3 = 0.d_{31}d_{32}d_{33}d_{34}\ldots$

...

Construct a new number $x = 0.x_1x_2x_3...$ where $x_i \neq d_{ii}$ for each $i$ .

Then $x$ differs from every $r_i$ in the i-th digit, so $x$ is not in our list.

This contradicts our assumption that all reals were listed. Therefore $(0, 1)$ is uncountable.

∎

Theorem 5.4: Power Set Cardinality

For any set $A$ , the power set $\mathcal{P}(A)$ has strictly greater cardinality:

|\mathcal{P}(A)| = 2^{|A|} > |A|

Remark

Hierarchy of Infinities:

$\aleph_0 = |\mathbb{N}| < 2^{\aleph_0} = |\mathbb{R}| < 2^{2^{\aleph_0}} < \cdots$

There are infinitely many different sizes of infinity!

Practice Quiz

Sequences and Cardinality Quiz

Questions

Correct

Accuracy

What is the closed form of

\sum_{i=1}^{n} i

Easy

Not attempted

Which set has the same cardinality as

\mathbb{N}

Medium

Not attempted

A set is countable if:

Easy

Not attempted

The geometric series

\sum_{i=0}^{n} r^i

equals:

Medium

Not attempted

Cantor's diagonalization proves that:

Medium

Not attempted

a_n = 2a_{n-1}

with

a_0 = 3

, what is

a_n

Medium

Not attempted

The cardinality of

\mathcal{P}(\mathbb{N})

is:

Hard

Not attempted

What is

\sum_{i=1}^{n} i^2

Hard

Not attempted

Two sets have the same cardinality if:

Easy

Not attempted

Which of the following is countably infinite?

Hard

Not attempted

Frequently Asked Questions

What's the intuition behind countable vs uncountable?

A set is countable if you can list all its elements in a sequence (1st, 2nd, 3rd, ...), even if the list is infinite.

A set is uncountable if no matter how you try to list elements, you'll always miss some (proven by diagonalization).

Surprisingly, adding more elements (like going from $\mathbb{N}$ to $\mathbb{Z}$ to $\mathbb{Q}$ ) doesn't make a set uncountable. You need a qualitatively different kind of infinity.

Why is ℚ countable but ℝ uncountable?

$\mathbb{Q}$ is countable because each rational $p/q$ is determined by two integers. We can systematically list all fractions by organizing them in a grid and traversing diagonally.

$\mathbb{R}$ is uncountable because real numbers have infinite decimal expansions that can't be captured by any listing scheme (Cantor's diagonal argument).

How do I prove a set is countable?

Common strategies:

Construct an explicit bijection with $\mathbb{N}$
Show it's a subset of a known countable set
Show it's a countable union of countable sets
Show it can be listed systematically

What are summation formulas used for?

Summation formulas are essential for:

Algorithm analysis: Computing time complexity (e.g., nested loops)
Probability: Expected values and variances
Combinatorics: Counting arguments
Mathematical proofs: Especially induction proofs

What's the practical importance of cardinality?

Cardinality theory has deep implications in computer science:

Computability: Not all functions are computable (there are uncountably many functions but only countably many programs)
Formal languages: Understanding the power of different computational models
Cryptography: Security based on computational intractability