index set
{{Short description|Mathematical term}}
{{distinguish|text = indexed sets, or index sets in computability theory}}
In mathematics, an index set is a set whose members label (or index) members of another set.{{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}}{{cite book|last=Munkres|first=James R.|title=Topology|volume= 2|location=Upper Saddle River|publisher=Prentice Hall|year=2000}} 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|{Aj}j∈J}}.
Examples
- An enumeration of a set {{mvar|S}} gives an index set , 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 .
- For , the indicator function on {{math|r}} is the function given by
The set of all such indicator 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 {{mvar|I}} that can sample the set efficiently; e.g., on input {{math|1n}}, {{mvar|I}} can efficiently select a poly(n)-bit long element from the set.
{{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
}}