HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, 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 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 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 number ...
set can be (injectively) indexed by the set of
natural numbers In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called '' cardinal ...
\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 , one has \mathbf_(x)=1 if x\i ...
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 (or uncountably infinite set) 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 nu ...
indexed by \mathbb.


Other uses

In
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
and
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
, 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 * Indexed family


References

{{Reflist Mathematical notation Basic concepts in set theory