# Difference between revisions of "Index set"

Jump to navigation
Jump to search

en>Lifeonahilltop m (→Examples) |
en>Brirush (Added reference) |
||

(One intermediate revision by one other user not shown) | |||

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'' | + | {{distinguish|Indexed set}} |

− | + | 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><ref>Munkres, James R. Topology. Vol. 2. Upper Saddle River: Prentice Hall, 2000.</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>. | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

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

Line 25: | Line 14: | ||

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

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

+ | {{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 | ||

+ | }}</ref> | ||

==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]] | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− |

## Latest revision as of 12:34, 25 November 2014

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 }}