Indexed family


In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a family of real numbers, indexed by the set of integers, is a collection of real numbers, where a given function selects one real number for each integer (possibly the same) as indexing.

More formally, an indexed family is a mathematical function together with its domain and image (that is, indexed families and mathematical functions are technically identical, just points of view are different). Often the elements of the set are referred to as making up the family. In this view, indexed families are interpreted as collections of indexed elements instead of functions. The set is called the index set of the family, and is the indexed set.

Sequences are one type of families indexed by natural numbers. In general, the index set is not restricted to be countable. For example, one could consider an uncountable family of subsets of the natural numbers indexed by the real numbers.

Formal definition edit

Let   and   be sets and   a function such that

where   is an element of   and the image   of   under the function   is denoted by  . For example,   is denoted by   The symbol   is used to indicate that   is the element of   indexed by   The function   thus establishes a family of elements in   indexed by   which is denoted by   or simply   if the index set is assumed to be known. Sometimes angle brackets or braces are used instead of parentheses, although the use of braces risks confusing indexed families with sets.

Functions and indexed families are formally equivalent, since any function   with a domain   induces a family   and conversely. Being an element of a family is equivalent to being in the range of the corresponding function. In practice, however, a family is viewed as a collection, rather than a function.

Any set   gives rise to a family   where   is indexed by itself (meaning that   is the identity function). However, families differ from sets in that the same object can appear multiple times with different indices in a family, whereas a set is a collection of distinct objects. A family contains any element exactly once if and only if the corresponding function is injective.

An indexed family   defines a set   that is, the image of   under   Since the mapping   is not required to be injective, there may exist   with   such that   Thus,  , where   denotes the cardinality of the set   For example, the sequence   indexed by the natural numbers   has image set   In addition, the set   does not carry information about any structures on   Hence, by using a set instead of the family, some information might be lost. For example, an ordering on the index set of a family induces an ordering on the family, but no ordering on the corresponding image set.

Indexed subfamily edit

An indexed family   is a subfamily of an indexed family   if and only if   is a subset of   and   holds for all  

Examples edit

Indexed vectors edit

For example, consider the following sentence:

The vectors   are linearly independent.

Here   denotes a family of vectors. The  -th vector   only makes sense with respect to this family, as sets are unordered so there is no  -th vector of a set. Furthermore, linear independence is defined as a property of a collection; it therefore is important if those vectors are linearly independent as a set or as a family. For example, if we consider   and   as the same vector, then the set of them consists of only one element (as a set is a collection of unordered distinct elements) and is linearly independent, but the family contains the same element twice (since indexed differently) and is linearly dependent (same vectors are linearly dependent).

Matrices edit

Suppose a text states the following:

A square matrix   is invertible, if and only if the rows of   are linearly independent.

As in the previous example, it is important that the rows of   are linearly independent as a family, not as a set. For example, consider the matrix

The set of the rows consists of a single element   as a set is made of unique elements so it is linearly independent, but the matrix is not invertible as the matrix determinant is 0. On the other hands, the family of the rows contains two elements indexed differently such as the 1st row   and the 2nd row   so it is linearly dependent. The statement is therefore correct if it refers to the family of rows, but wrong if it refers to the set of rows. (The statement is also correct when "the rows" is interpreted as referring to a multiset, in which the elements are also kept distinct but which lacks some of the structure of an indexed family.)

Other examples edit

Let   be the finite set   where   is a positive integer.

  • An ordered pair (2-tuple) is a family indexed by the set of two elements,   each element of the ordered pair is indexed by each element of the set  
  • An  -tuple is a family indexed by the set  
  • An infinite sequence is a family indexed by the natural numbers.
  • A list is an  -tuple for an unspecified   or an infinite sequence.
  • An   matrix is a family indexed by the Cartesian product   which elements are ordered pairs; for example,   indexing the matrix element at the 2nd row and the 5th column.
  • A net is a family indexed by a directed set.

Operations on indexed families edit

Index sets are often used in sums and other similar operations. For example, if   is an indexed family of numbers, the sum of all those numbers is denoted by


When   is a family of sets, the union of all those sets is denoted by


Likewise for intersections and Cartesian products.

Usage in category theory edit

The analogous concept in category theory is called a diagram. A diagram is a functor giving rise to an indexed family of objects in a category C, indexed by another category J, and related by morphisms depending on two indices.

See also edit

  • Array data type – Data type that represents an ordered collection of elements (values or variables)
  • Coproduct – Category-theoretic construction
  • Diagram (category theory) – Indexed collection of objects and morphisms in a category
  • Disjoint union – In mathematics, operation on sets
  • Family of sets – Any collection of sets, or subsets of a set
  • Index notation – Manner of referring to elements of arrays or tensors
  • Net (mathematics) – A generalization of a sequence of points
  • Parametric family – family of objects whose definitions depend on a set of parameters
  • Sequence – Finite or infinite ordered list of elements
  • Tagged union – Data structure used to hold a value that could take on several different, but fixed, types

References edit

  • Mathematical Society of Japan, Encyclopedic Dictionary of Mathematics, 2nd edition, 2 vols., Kiyosi Itô (ed.), MIT Press, Cambridge, MA, 1993. Cited as EDM (volume).