Misplaced Pages

Index set

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Index sets) Mathematical term Not to be confused with 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. 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.

Examples

  • An enumeration of a set S gives an index set J ⊂ N {\displaystyle J\subset \mathbb {N} } , where f : J → S is the particular enumeration of S.
  • Any countably infinite set can be (injectively) indexed by the set of natural numbers N {\displaystyle \mathbb {N} } .
  • For r ∈ R {\displaystyle r\in \mathbb {R} } , the indicator function on r is the function 1 r : R → { 0 , 1 } {\displaystyle \mathbf {1} _{r}\colon \mathbb {R} \to \{0,1\}} given by 1 r ( x ) := { 0 , if  x ≠ r 1 , if  x = r . {\displaystyle \mathbf {1} _{r}(x):={\begin{cases}0,&{\mbox{if }}x\neq r\\1,&{\mbox{if }}x=r.\end{cases}}}

The set of all such indicator functions, { 1 r } r ∈ R {\displaystyle \{\mathbf {1} _{r}\}_{r\in \mathbb {R} }} , is an uncountable set indexed by R {\displaystyle \mathbb {R} } .

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 1, I can efficiently select a poly(n)-bit long element from the set.

See also

References

  1. Weisstein, Eric. "Index Set". Wolfram MathWorld. Wolfram Research. Retrieved 30 December 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.
Categories: