mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, an index set is a set whose members label (or index) members of another set. For instance, if the elements of a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

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 In mathematics, a surjective function (also known as surjection, or onto function ) is a function such that, for every element of the function's codomain, there exists one element in the function's domain such that . In other words, for a ...

from onto , and the indexed collection is typically called an ''

indexed family In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a family of real numbers, indexed by the set of integers, is a collection of real numbers, wher ...

'', often written as .

Examples

*An

enumeration An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the element (mathematics), elements of a Set (mathematics), set. The pre ...

of a set gives an index set

J \sub \N

, where is the particular enumeration of . *Any

countably infinite In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbe ...

set can be (injectively) indexed by the set of

natural numbers In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positiv ...

\N

. *For

r \in \R

, the

indicator function In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if is a subset of some set , then the indicator functio ...

on is the function

\mathbf_r\colon \R \to \

given by

\mathbf_r (x) := \begin 0, & \mbox x \ne r \\ 1, & \mbox x = r. \end

The set of all such indicator functions,

\_

, is an

uncountable set In mathematics, an uncountable set, informally, is an infinite set that contains too many elements to be countable. The uncountability of a set is closely related to its cardinal number: a set is uncountable if its cardinal number is larger t ...

indexed by

\mathbb

Other uses

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

and

cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (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.

References

{{Reflist Mathematical notation Basic concepts in set theory

Examples

Other uses

See also

References