# Difference between revisions of "Index set"

Jump to navigation
Jump to search

en>Lifeonahilltop m (→Examples) |
en>APerson m (Moved a phrase into parentheses in first sentence) |
||

Line 1: | Line 1: | ||

− | In [[mathematics]], the elements of a [[Set (mathematics)|set]] ''A'' may be ''indexed'' or ''labeled'' by means of a set ''J'' | + | {{one source|date=December 2013}} |

+ | In [[mathematics]], an '''index set''' is a set whose members label (or index) members of another set.<ref>{{cite web|last=Weisstein|first=Eric|title=Index Set|url=http://mathworld.wolfram.com/IndexSet.html|work=Wolfram MathWorld|publisher=Wolfram Research|accessdate=30 December 2013}}</ref> For instance, if the elements of a [[Set (mathematics)|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|(indexed) family]]'', often written as (''A''<sub>''j''</sub>)<sub>''j''∈''J''</sub>. | ||

− | 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<sup>n</sup>, ''I'' can efficiently select a poly(n)-bit long element from the set. | + | 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<sup>n</sup>, ''I'' can efficiently select a poly(n)-bit long element from the set.<ref> |

− | <ref> | ||

{{cite book | {{cite book | ||

| title= Foundations of Cryptography: Volume 1, Basic Tools | | title= Foundations of Cryptography: Volume 1, Basic Tools | ||

Line 10: | Line 10: | ||

|publisher= Cambridge University Press | |publisher= Cambridge University Press | ||

|isbn= 0-521-79172-3 | |isbn= 0-521-79172-3 | ||

− | }} | + | }}</ref> |

− | </ref> | ||

==Examples== | ==Examples== | ||

Line 24: | Line 23: | ||

The set of all the <math>\mathbf{1}_r</math> functions <!--(which happens to be a [[basis]] for the [[vector space]] of all functions on <math>\mathbb{R}</math> over <math>\mathbb{R}</math>)--> is an [[uncountable set]] indexed by <math>\mathbb{R}</math>. | The set of all the <math>\mathbf{1}_r</math> functions <!--(which happens to be a [[basis]] for the [[vector space]] of all functions on <math>\mathbb{R}</math> over <math>\mathbb{R}</math>)--> is an [[uncountable set]] indexed by <math>\mathbb{R}</math>. | ||

− | |||

− | |||

− | |||

==See also== | ==See also== | ||

− | |||

* [[Friendly-index set]] | * [[Friendly-index set]] | ||

* [[Indexed family]] | * [[Indexed family]] | ||

+ | ==References== | ||

+ | {{Reflist}} | ||

[[Category:Mathematical notation]] | [[Category:Mathematical notation]] | ||

[[Category:Basic concepts in set theory]] | [[Category:Basic concepts in set theory]] | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− |

## Revision as of 22:53, 30 December 2013

Template:One source
In mathematics, an **index set** is a set whose members label (or index) members of another set.^{[1]} 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}.

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.^{[2]}

## 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 .

## See also

## References

- ↑ Template:Cite web
- ↑ {{#invoke:citation/CS1|citation |CitationClass=book }}