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>{{#invoke:citation/CS1|citation |CitationClass=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>

See also

• Friendly-index set