Index Set
Get Index Set essential facts below. View Videos or join the Index Set discussion. Add Index Set to your topic list for future reference or share this resource on social media.
Index Set

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 the elements 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 {Aj}j?J.


  • 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 (injectively) indexed by the set of natural numbers .
  • For , the indicator function on 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 I that can sample the set efficiently; e.g., on input 1n, I can efficiently select a poly(n)-bit long element from the set.[3]

See also


  1. ^ Weisstein, Eric. "Index Set". Wolfram MathWorld. Wolfram Research. Retrieved 2013.
  2. ^ Munkres, James R. (2000). Topology. Vol. 2. Upper Saddle River: Prentice Hall.
  3. ^ Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3.

  This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.



Music Scenes