2.2 Formal Definition

More formally, an expression written in indexed notation can be noted as follows:

⊙
    Ei
 i∈I
(4)

It consists of the following elements:

  1. An index operator, here written as . This operator can be any associative and commutative operator, such as (summation), for example.

  2. An index set, represented by I, being any countable (finite or infinite) collection of elements. The elements can be any indivisible item. Often they are integers.

  3. An active index i (in i I), attached to the index operator.

  4. An indexed expression Ei, that normally contains the same index name again. We call this index passive index. The reason for that will be clear later on.

(1) The index operator: It is clear why the index operator must be commutative and associative: A mathematical set is unordered and its elements can be “traversed” in any order. As an example, the does not specify in which order the indexed expressions Ei are added up. Various operators fulfill these requirements. Besides the addition, represented by the operator , the following index operators are commonly used (examples will be given later on):

(2) The index set: In the simplest case, the elements of the index set are integers, as in :

I = {1, ...,n},   where  n > 0

However, they can also be identifiers (symbolic names), strings or any other items and even sets representing elements of a set. In the following index set I with the four elements are identifiers :

J =  { spring , summer  , autumn  , winter }

Ordering: Sets are unordered in mathematics as mentioned above. In modeling environments, however, we often must impose a specific order, for example, if a set consists of a number of time periods or time points. Then the natural order is the sequence of these periods. For example, the weekdays:

K  = { Mon,  Tue, Wen  , Thu, Fri, Sat, Son }

Example: Suppose that ai is the quantity of sells in time period i I. To know the difference di from one time period to the next, we might use the expression:

di = ai+1 - ai   forall k ∈ {1, ...,n - 1}

(Note that the last value dn is not defined!).

In modeling, the order of index sets is important in such a context, because we often need to refer to the “previous”, the “next”, the “last” or the “first” period in an indexed expression. In spacial arrangements the order might also be important. Consider a chessboard with I = {18} rows and columns, then it makes sense to refer to the “neighbor” columns at the left or right and the “neighbor” rows above or below a given cell. In another context, the ordering might have a semantical meaning. For example, if we want – for a specific purpose – impose an order on a list of products. We can order the product by “importance” or whatever criterion we need. Without ordering the statement to generate a “list with the first 10 products” would have no meaning. Without any externally imposed criterion the ordering of the products would have no meaning, as in:

I = { bred, cheese, meat, eggs }

Tuples: The elements of an index-set may also be tuples, which is extremely common in modeling. A tuple is an ordered list of components which are separated by a comma and surrounded by parentheses. For example “(lion, mammal)” is a tuple that may express the fact that a lion belongs to the category of mammals. A list of such tuples can build a (large) index-set:

J = { (lion,mammal   ),(sparrow, bird),(snake, reptile),(cow, mammal   ),...}

Another example is the (infinite) list of all positive integer grid points in a Euclidean space, written as :

                    +
I = {(x,y) | x, y ∈ ℤ }

= {(0,0 ),(1,0),(1,1),(0,1),(0,2),(1,2),(2,2),(2,1),...}

Set of sets: Another important case in modeling is “set of sets”. As a concrete example, certain clients are served from certain warehouses. Let I = {1,,m} be a set of warehouses and let J = {1,,n} be a set of clients, then the set S:

S  = {Qi | i ∈ I , Qi ⊆ J }

This set S tells us which client j J is served from which warehouse i I. Note that the elements of the index-set S are themselves index-sets (Qi)

Example:

                                        Q1 =  {1,2,3}
                                        Q2 =  {2,3}
S =  {{1,2,3},{2, 3},{},{2 }}  , hence  Q3 =  {}

                                        Q4 =  {2}

says, that warehouse 1 serves client 1, 2, 3, warehouse 2 serves clients 2, 3, warehouse 3 do not serve any client, and warehouse 4 serves client 2, that is, Qi is the set of clients served by warehouse i I.

Alternatively, this kind of data (set of set) can also be formulated as a tuple list:

S =  {(i,j)|(i,j) ∈ {(1,1 ),(1,2 ),(1,3),(2,2),(2,3),(4,2)}}   forall i ∈ I,j ∈ J

(3) The active index: The active index is a (dummy) name (or an identifier) representing an arbitrary element in the index set. The passive index is also an identifier used in the indexed expression which must have the same spelling as the active index. The term i I, consisting of the active index and the index set, is called an indexing term. The active index and the passive index are used as place-holders to define a bijective mapping between the index set and a set of indexed expressions. Each element i in the index set maps to an indexed expression by replacing the passive index with the corresponding element i in the index set. This mapping is called the index mechanism. In fact, it defines the (bijective) function f : i f -→ Ei with i I. This mapping supposes that the corresponding indexed expressions Ei exist. The domain of this function f contains the elements of the index set {1, 2,,n}, and the codomain (or the range) is the set of indexed expressions {E1,E2,,En}.

(4) The index expression: The indexed expression is an arbitrary expression. It is not necessary that it contains a passive index. For example, in the expression:

∑   3  with   I = {1, ...,n}

 i∈I

the indexed expression is just 3. The whole expression then reduces simply to:

3 + 3 + ...+ 3=  3 ⋅ n
◟-----◝◜-----◞
    n- times

The indexed expression can also be reduced to a passive index as in:

∑
   i  with   I = {1,...,n }
i∈I

in which case the indexed expression is just i. The whole expression reduces to:

1 + 2 + ...+ n

The indexed expression can itself contain index operators. For example:

   (        )
∑    ∑
         Fi,j     forall I = {1,..., n},J = {1, ...,m }
i∈I  j∈J

In this case, the expression first expands to:

∑
   (Fi,1 + Fi,2 + ⋅⋅⋅ + Fi,m)  forall I = {1,...,n }
i∈I

Finally, the outer sum is applied to get the expression

F1,1 + F1,2 + ⋅⋅⋅ + F1,m + F2,1 + F2,2 + ...⋅⋅⋅ + Fn,m

Definition: An indexed notation is a formula expressing the fact that the index operator is applied to the set of indexed expressions constructed by the index mechanism., that is, a bijective mapping between the elements of the index set and the indexed expressions.