Index set

From formulasearchengine
Revision as of 19:32, 26 March 2012 by en>Lifeonahilltop (→‎Examples)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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 (Aj)jJ.

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 1n, I can efficiently select a poly(n)-bit long element from the set. [1]

Examples

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

References

  1. {{#invoke:citation/CS1|citation |CitationClass=book }}

See also

de:Familie (Mathematik) it:Famiglia (matematica) hu:Halmazrendszer nl:Indexverzameling ja:添字記法 no:Familie (matematikk) zh:索引集