Index Set

From GM-RKB
Jump to navigation Jump to search

An Index Set is a set that ...



References

2009

  • http://en.wikipedia.org/wiki/Index_set
    • In mathematics, the elements of a set [math]\displaystyle{ A }[/math] 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 [math]\displaystyle{ A }[/math] and the indexed collection is typically called an (indexed) family, often written as (Aj)jJ.
    • 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 1n, $I$ can efficiently select a poly(n)-bit long element from the set.
    • An enumeration of a set [math]\displaystyle{ S }[/math] gives an index set [math]\displaystyle{ J \sub \mathbb{N} }[/math], where [math]\displaystyle{ f:J \rarr \mathbb{N} }[/math] is the particular enumeration of S.
    • Any countably infinite set can be indexed by [math]\displaystyle{ \mathbb{N} }[/math].