1.3: Sequences

By an infinite sequence (briefly sequence) we mean a mapping (call it $u )$ whose domain is $N$ (all natural numbers $1,2,3, \dots ) ; D_{u}$ may also contain $0 .$

A finite sequence is a map $u$ in which $D_{u}$ consists of all positive (or non-negative) integers less than a fixed integer $p .$ The range $D_{u}^{\prime}$ of any sequence $u$ may be an arbitrary set $B ;$ we then call $u$ a sequence of elements of $B,$ or in $B .$ For example,

$$u=\left( \begin{array}{lllllll}{1} & {2} & {3} & {4} & {\ldots} & {n} & {\ldots} \\ {2} & {4} & {6} & {8} & {\ldots} & {2 n} & {\dots}\end{array}\right)$$

is a sequence with

$$D_{u}=N=\{1,2,3, \ldots\}$$

and with function values

$$u(1)=2, u(2)=4, u(n)=2 n, \quad n=1,2,3, \ldots$$

Instead of $u(n)$ we usually write $u_{n}$ ("index notation"), and call $u_{n}$ the $n^{th}$ term of the sequence. If $n$ is treated as a variable, $u_{n}$ is called the general term of the sequence, and $\left\{u_{n}\right\}$ is used to denote the entire (infinite) sequence, as well as its range $D_{u}^{\prime}$ (whichever is meant, will be clear from the context). The formula $\left\{u_{n}\right\} \subseteq B$ means that $D_{u}^{\prime} \subseteq B,$ i.e., that $u$ is a sequence in $B$. To
determine a sequence, it suffices to define its general term $u_{n}$ by some formula or rule. In $(1)$ above, $u_{n}=2 n$.

Often we omit the mention of $D_{u}=N$ (since it is known) and give only the range $D_{u}^{\prime} .$ Thus instead of $(1),$ we briefly write

$$2,4,6, \ldots, 2 n, \ldots$$

or, more generally,

$$u_{1}, u_{2}, \dots, u_{n}, \dots$$

Yet it should be remembered that $u$ is a set of pairs (a map).

If all $u_{n}$ are distinct (different from each other), $u$ is a one-to-one map. However, this need not be the case. It may even occur that all $u_{n}$ are equal (then $u$ is said to be constant); e.g., $u_{n}=1$ yields the sequence $1,1,1, \ldots, 1, \ldots,$ i.e.

$$u=\left( \begin{array}{cccccc}{1} & {2} & {3} & {\ldots} & {n} & {\ldots} \\ {1} & {1} & {1} & {\ldots} & {1} & {\ldots}\end{array}\right)$$

Note that here$u$ is an infinite sequence (since $D_{u}=N$), even though its range $D_{u}^{\prime}$ has only one element, $D_{u}^{\prime}=\{1\} .$ (In sets, repeated terms count as one element; but the sequence $u$ consists of infinitely many distinct pairs $(n, 1) .$ ) If all $u_{n}$ are real numbers, we call $u$ a real sequence. For such sequences, we have the following definitions.

Definition 1

A real sequence $\left\{u_{n}\right\}$ is said to be monotone (or monotonic) iff it is either nondecreasing, i.e.

$$(\forall n) \quad u_{n} \leq u_{n+1}$$

or nonincreasing, i.e.,

$$(\forall n) \quad u_{n} \geq u_{n+1}$$

Notation: $\left\{u_{n}\right\} \uparrow$ and $\left\{u_{n}\right\} \downarrow,$ respectively. If instead we have the strict inequalities $u_{n}<u_{n+1}$ (respectively, $u_{n}>u_{n+1} ),$ we call $\left\{u_{n}\right\}$ strictly monotone (increasing or decreasing).

A similar definition applies to sequences of sets.

Definition 2

A sequence of sets $A_{1}, A_{2}, \ldots, A_{n}, \ldots$ is said to be monotone iff it is either expanding, i.e.,

$$(\forall n) \quad A_{n} \subseteq A_{n+1}$$

or contracting, i.e.,

$$(\forall n) \quad A_{n} \supseteq A_{n+1}$$

Notation: $\left\{A_{n}\right\} \uparrow$ and $\left\{A_{n}\right\} \downarrow,$ respectively. For example, any sequence of concentric solid spheres (treated as sets of points), with increasing radii, is expanding; if the radii decrease, we obtain a contracting sequence.

Definition 3

Let $\left\{u_{n}\right\}$ be any sequence, and let

$$n_{1}<n_{2}<\cdots<n_{k}<\cdots$$

be a strictly increasing sequence of natural numbers. Select from $\left\{u_{n}\right\}$ those terms whose subscripts are $n_{1}, n_{2}, \ldots, n_{k}, \ldots$ Then the sequence $\left\{u_{n_{k}}\right\}$ so selected (with $k$ th term equal to $u_{n_{k}} ),$ is called the subsequence of $\left\{u_{n}\right\},$ determined by the subscripts $n_{k}, k=1,2,3, \ldots$.

Thus (roughly) a subsequence is any sequence obtained from $\left\{u_{n}\right\}$ by dropping some terms, without changing the order of the remaining terms (this is ensured by the inequalities $n_{1}<n_{2}<\cdots<n_{k}<\cdots$ where the $n_{k}$ are the subscripts of the remaining terms). For example, let us select from (1) the subsequence of terms whose subscripts are primes (including 1). Then the subsequence is

$$2,4,6,10,14,22, \dots$$

i.e.,

$$u_{1}, u_{2}, u_{3}, u_{5}, u_{7}, u_{11}, \dots$$

All these definitions apply to finite sequences accordingly. Observe that every sequence arises by "numbering" the elements of its range (the terms): $u_{1}$ is the first term, $u_{2}$ is the second term, and so on. By so numbering, we put the terms in a certain order, determined by their subscripts $1,2,3, \ldots$ (like the numbering of buildings in a street, of books in a library, etc. $) .$ The question now arises: Given a set $A,$ is it always possible to "number" its elements by integers? As we shall see in $\$ 4,$ this is not always the case. This leads us to the following definition.

Definition 4

A set $A$ is said to be countable iff $A$ is contained in the range of some sequence (briefly, the elements of $A$ can be put in a sequence).

If, in particular, this sequence can be chosen finite, we call $A$ a finite set. (The empty set is finite.)

Sets that are not finite are said to be infinite.

Sets that are not countable are said to be uncountable.

Note that all finite sets are countable. The simplest example of an infinite countable set is $N=\{1,2,3, \ldots\}$.