Index set

In mathematics

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 (A_j)_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 1ⁿ, I can efficiently select a poly(n)-bit long element from the set.

Examples

• An enumeration
  Enumeration
  In 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 set

Uncountable 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 .