Index set
Template:Short description Template:Distinguish
In mathematics, an index set is a set whose members label (or index) members of another set.<ref>Template:Cite web</ref><ref>Template:Cite book</ref> For instance, if the elements of a set Template:Mvar may be indexed or labeled by means of the elements of a set Template:Mvar, then Template:Mvar is an index set. The indexing consists of a surjective function from Template:Mvar onto Template:Mvar, and the indexed collection is typically called an indexed family, often written as Template:Math.
Examples
- An enumeration of a set Template:Mvar gives an index set <math>J \sub \N</math>, where Template:Math is the particular enumeration of Template:Math.
- Any countably infinite set can be (injectively) indexed by the set of natural numbers <math>\N</math>.
- For <math>r \in \R</math>, the indicator function on Template:Math is the function <math>\mathbf{1}_r\colon \R \to \{0,1\}</math> given by <math display="block">\mathbf{1}_r (x) := \begin{cases} 0, & \mbox{if } x \ne r \\ 1, & \mbox{if } x = r. \end{cases} </math>
The set of all such indicator functions, <math>\{ \mathbf{1}_r \}_{r\in\R}</math>, is an uncountable set indexed by <math>\mathbb{R}</math>.
Other uses
In computational complexity theory and cryptography, an index set is a set for which there exists an algorithm Template:Mvar that can sample the set efficiently; e.g., on input Template:Math, Template:Mvar can efficiently select a poly(n)-bit long element from the set.<ref> Template:Cite book</ref>