Definitions

and denote reals and naturals, respectively. All subscripts are in , unless otherwise specified. If is a set, denotes its power set, i.e., the set of all subsets of , and denotes its cardinality. The subset relationship is denoted by . The logical if is denoted by ; the logical if and only if is denoted by or iff. If V is a vector space, dim(V) denotes the dimension of V. For example, if V is a plane, dim(V)=2.

Elements forming a sequence are written inside a pair of matching square brackets: . The empty sequence is written as [] (Settle 99). Elements forming a set are written inside curly braces: . The empty set is written as . Elements forming a vector are written inside angular brackets: < >. For example, [0,1,2], , <0,1,2> denote a sequence, a set, and a vector, respectively. Let v be a variable, , [v], , v denote that v is bound to a set, a sequence, a vector, and an element, respectively. For example, can denote ; [v] can denote [0,1,2]; can denote <0,1,2>; v can denote 1. Furthermore, denotes a set of one element ; denotes an i-th set of elements; denotes a sequence with one element ; denotes an i-th sequence of elements (Kulyukin, Hammond, and Burke 1996). If is a set, is the set of all possible sequences over . For example, is the set of all sequences of reals.

The following functions are defined on sets and sequences. head and tail return the first element and the rest of the elements in a sequence respectively, that is, head([])=[], , ,..., = , tail([]) =   = [], , ,..., = ,..., . conc stands for concatenation which appends its first argument onto its second argument. For example, = , = , and conc([v], [])=[[v]]. apnd stands for append and is defined by apnd([v], [w]) = ,..., , ,..., , , ,..., , [w]= ,..., , apnd([],[v])=[v], apnd([v],[])=[v]. If , , ..., are sequences,  =  . A sequence completes a sequence iff is a subsequence of . For example, if , , and , completes , but does not complete . Any sequence completes [].