1.3 Sequences

sequence

a list of objects arranged in definite order: such as a first, second, and third element.

recursive formula

defines each term of the sequence based on previous terms (c_n-1) and includes at least one starting value.

• ex: c₁ = 5, c_n = 2c_n-1

• means each term is twice the previous term, starting with the first term being 5.

explicit formula

provides the n-th term of a sequence directly as a function of its position n.

set corresponding to a sequence

the set containing all distinct elements founds within the sequence, regardless of their order or repetition.

• ex: sequence a, b, a, b

• set: {a,b}

array

a sequence of positions or “boxes,” either finite or infinite to which elements from a set may be assigned.

characteristic function

a function that indicates membership of an element in a set, defined as 1 if the element is in the set and 0 otherwise.

• F_a(x) = 1 if x ∈ A

• F_a(x) = 0 if x ∉ A

characteristic function of intersection A ∩ B

F_A∩B = F_AB_B

• the function of intersection A∩B is the product of the results of characteristic function A times characteristic function B.

• if an element is in both sets, the characteristic function will return 1; otherwise, it will return 0.

characteristic function of A ∪ B

F_A∪B = F_A + F_B - F_A∩B

• the function of union A∪B is the sum of the results of the characteristic functions of A and B, minus the product of the intersection A∩B to avoid double counting.

• if it return 1 the element is in either set, if it returns 0, the element is in neither set.

characteristic function of F_A ⊕ F_B

F_A + F_B - 2F_A∩B

• the characteristic function of the symmetric difference A⊕B is the sum of the characteristic functions of A and B, minus double the product of characteristic function intersection A∩B.

• if it returns 1 the element is in either set A or B, but not both.

countable set

the members of the set can be arranged in a sequence, either finite or infinite, they have a specific natural number position such as 1st, 2nd, 3rd.

cantor’s diagonal argument

the set of real numbers is uncountable.

A* in strings

the set of all finite sequences (strings or words) formed using elements the alphabet A, including the empty string ϵ.

catenation of strings w₁ and w₂

the operation of joining strings (words) w₁ (s1, s2, … sn) and w₂ (t1, t2, … tk) to form a single string w₁*w₂

• equals (s1…sn)*(t1…tk)

regular expression over A

any string built from the elements of A and the symbols (,) or + or * or ϵ

regular expression RE1

ϵ is a regular expression.

regular expression RE2

if x∈A, then x is a regular expression.

regular expression RE3

if α and β are regular expressions, then the concatenation αβ is also a regular expression.

regular expression RE4

if α and β are regular expressions, then (α + β) is also a regular expression.

regular expression RE5

if α is a regular expression, then (α)* is also a regular expression.

(α)*

denotes zero or more finite repetitions of the string “α”

regular set RE1

regular expression ϵ corresponds to {ϵ}

regular set RE2

regular expression x∈A corresponds to {x}

regular set RE3

regular expression αβ corresponds to M, N, ⊆ A* then αβ corresponds to MN or {st | s ∈ M, t ∈ N}

regular set RE4

if α corresponds to M and β corresponds to N, regular expression (α+β) corresponds to M∪N. or {st | s ∈ M or t ∈ N}.

regular set RE5

if α* corresponds to M, then α* corresponds to M*, where M is a set of strings from A and elements from M* are finite sequences of such strings.