In mathematics, an index set is a set whose members label (or index) members of another set. For instance, if the elements of a set may be ''indexed'' or ''labeled'' by means of the elements of a set , then is an index set. The indexing consists of a surjective function from onto , and the indexed collection is typically called an '' (indexed) family'', often written as .

Examples

*An enumeration of a set gives an index set

J \sub \N

, where is the particular enumeration of . *Any countably infinite set can be (injectively) indexed by the set of natural numbers

\N

. *For

r \in \R

, the

indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , one has \mathbf_(x)=1 if x ...

on is the function

\mathbf_r\colon \R \to \

given by

\mathbf_r (x) := \begin 0, & \mbox  x \ne r  \\ 1,  & \mbox x = r. \end

The set of all such indicator functions,

\_

, is an uncountable set indexed by

\mathbb

Other uses

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

and

cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...

, an index set is a set for which there exists an algorithm that can sample the set efficiently; e.g., on input , can efficiently select a poly(n)-bit long element from the set.

References

{{Reflist Mathematical notation Basic concepts in set theory

Examples

Other uses

See also

References