# Index set

Jump to navigation
Jump to search

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Template:Distinguish
In mathematics, an **index set** is a set whose members label (or index) members of another set.^{[1]}^{[2]} For instance, if the elements of a set *A* may be *indexed* or *labeled* by means of a set *J*, then *J* is an index set. The indexing consists of a surjective function from *J* onto *A* and the indexed collection is typically called an *(indexed) family*, often written as (*A*_{j})_{j∈J}.

## Examples

- An enumeration of a set
*S*gives an index set , where*f*:*J*→*S*is the particular enumeration of*S*.

- Any countably infinite set can be indexed by .

- For , the indicator function on
*r*is the function given by

The set of all the functions is an uncountable set indexed by .

## Other uses

In computational complexity theory and cryptography, an index set is a set for which there exists an algorithm *I* that can sample the set efficiently; i.e., on input 1^{n}, *I* can efficiently select a poly(n)-bit long element from the set.^{[3]}

## See also

## References

- ↑ Template:Cite web
- ↑ Munkres, James R. Topology. Vol. 2. Upper Saddle River: Prentice Hall, 2000.
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}