Index set
In mathematics, an index set is a set whose members label (or index) members of another set.
≈ 1 min read
Index set. encyclopegia.org, snapshot enwiki-001350537554. /a/index-set
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 may be indexed or labeled by means of the elements of a set , then is an index set. The indexing consists of a surjective function from onto , and the indexed collection is typically called an indexed family, often written as .
Examples
An enumeration of a set gives an index set J \sub \N , where is the particular enumeration of . Any countably infinite set can be (injectively) indexed by the set of natural numbers \N . For r \in \R , the indicator function on is the function \mathbf{1}_r\colon \R \to \{0,1\} given by \mathbf{1}_r (x) := \begin{cases} 0, & \mbox{if } x \ne r \\ 1, & \mbox{if } x = r. \end{cases} The set of all such indicator functions, \{ \mathbf{1}_r \}_{r\in\R} , is an uncountable set indexed by \mathbb{R} .
Other uses
In computational complexity theory and cryptography, an index set is a set for which there exists an algorithm that can sample the set efficiently; e.g., on input , can efficiently select a poly(n)-bit long element from the set.
See also
Friendly-index set
Text derived from https://en.wikipedia.org/w/index.php?oldid=1350537554 under CC BY-SA 4.0; modifications have been made.