{{Short description|Mathematical term}} {{distinguish|text = index'''ed''' sets, or index sets in computability theory}}
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|access-date=30 December 2013}}</ref><ref>{{cite book|last=Munkres|first=James R.|author-link=James Munkres|title=Topology|volume= 2|location=Upper Saddle River|publisher=Prentice Hall|year=2000}}</ref> For instance, if the elements of a set {{mvar|A}} may be ''indexed'' or ''labeled'' by means of the elements of a set {{mvar|J}}, then {{mvar|J}} is an index set. The indexing consists of a surjective function from {{mvar|J}} onto {{mvar|A}}, and the indexed collection is typically called an ''indexed family'', often written as {{math|{''A''<sub>''j''</sub>}<sub>''j''∈''J''</sub>}}.
==Examples== *An enumeration of a set {{mvar|S}} gives an index set <math>J \sub \N</math>, where {{math|''f'' : ''J'' → ''S''}} is the particular enumeration of {{math|''S''}}. *Any countably infinite set can be (injectively) indexed by the set of natural numbers <math>\N</math>. *For <math>r \in \R</math>, the indicator function on {{math|''r''}} is the function <math>\mathbf{1}_r\colon \R \to \{0,1\}</math> given by <math display="block">\mathbf{1}_r (x) := \begin{cases} 0, & \mbox{if } x \ne r \\ 1, & \mbox{if } x = r. \end{cases} </math>
The set of all such indicator functions, <math>\{ \mathbf{1}_r \}_{r\in\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 {{mvar|I}} that can sample the set efficiently; e.g., on input {{math|1''<sup>n</sup>''}}, {{mvar|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== * Friendly-index set
==References== {{Reflist}}
Category:Mathematical notation Category:Basic concepts in set theory