HOME

TheInfoList




In
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, 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 In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

surjective function
from onto , and the indexed collection is typically called an '' (indexed) family'', 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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and r ...
of a set gives an index set J \sub \N, where is the particular enumeration of . *Any
countably infinite In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
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 total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...

natural numbers
\N. *For r \in \R, the
indicator function In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...
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 Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
indexed by \mathbb.


Other uses

In
computational complexity theory 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 by a computer. A computation problem is solvable by ...
and
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia ''-logy'' is a suffix in the English language, used with words originally adapted from Ancient Greek ending in (''- ...

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 *
Indexed family In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It h ...


References

{{Reflist Mathematical notation
Basic concepts in set theory{{Commons This category is for the foundational concepts of naive set theory, in terms of which contemporary mathematics is typically expressed. Mathematical concepts ...