Editing Index set

{{Short description|Mathematical term}}
{{distinguish|text = [[Indexed set|index'''ed''' sets]], or [[Index set (recursion theory)|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.|title=Topology|volume= 2|location=Upper Saddle River|publisher=Prentice Hall|year=2000}}</ref> For instance, if the elements of a [[Set (mathematics)|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]]