Index set
Encyclopedia
In mathematics
, the elements of a set A may be indexed or labeled by means of a set J that is on that account called 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.
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; i.e., on input 1n, I can efficiently select a poly(n)-bit long element from the set.
The set of all the
functions is an uncountable set
indexed by
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the elements of a set A may be indexed or labeled by means of a set J that is on that account called an index set. The indexing consists of a surjective function
Surjective function
In mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...
from J onto A and the indexed collection is typically called an (indexed) family
Indexed family
In mathematics, an indexed family is a collection of values that are associated with indexes. For example, a family of real numbers, indexed by the integers is a collection of real numbers, where each integer is associated with one of the real numbers....
, often written as (Aj)j∈J.
In computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, an index set is a set for which there exists an algorithm I that can sample the set efficiently; i.e., on input 1n, I can efficiently select a poly(n)-bit long element from the set.
Examples
- An enumerationEnumerationIn mathematics and theoretical computer science, the broadest and most abstract definition of an enumeration of a set is an exact listing of all of its elements . The restrictions imposed on the type of list used depend on the branch of mathematics and the context in which one is working...
of a set gives an index set
, where is the particular enumeration of .
- Any countably infinite set can be indexed by
.
- For
, the indicator function on is the function 
given by
The set of all the
functions is an uncountable setUncountable set
In mathematics, an uncountable 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 number is larger than that of the set of all natural numbers.-Characterizations:There...
indexed by
.