Index set

In mathematics, the elements of a set "A" may be "indexed" or "labeled" by means of a set "J" that is on that account called 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".

In 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ⁿ, "I" can efficiently select a poly(n)-bit long element from the set. [cite book
title= Foundations of Cryptography: Volume 1, Basic Tools
last= Goldreich
first= Oded
year= 2001
publisher= Cambridge University Press
isbn= 0-521-79172-3]

Examples

*An enumeration of a set "S" gives an index set $J\; sub\; mathbb\{N\}$, where $f:J\; arr\; mathbb\{N\}$ is the particular enumeration of "S".

*Any countably infinite set can be indexed by $mathbb\{N\}$.

*For $r\; in\; mathbb\{R\}$, the indicator function on r, is the function $mathbf\{1\}\_rcolon\; mathbb\{R\}\; arr\; mathbb\{R\}$ given by

:

The set of all the $mathbf\{1\}\_r$ functions is an uncountable set indexed by $mathbb\{R\}$.

References

ee also

* Index
* Indexed family