# Index set

Index set

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 ("A""j")"j"&isin;"J".

In 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. [cite book
title= Foundations of Cryptography: Volume 1, Basic Tools
last= Goldreich
first= Oded
year= 2001
publisher= Cambridge University Press
isbn= 0-521-79172-3
]

Examples

*An enumeration of a set "S" gives an index set $J sub mathbb\left\{N\right\}$, where $f:J arr mathbb\left\{N\right\}$ is the particular enumeration of "S".

*Any countably infinite set can be indexed by $mathbb\left\{N\right\}$.

*For $r in mathbb\left\{R\right\}$, the indicator function on r, is the function $mathbf\left\{1\right\}_rcolon mathbb\left\{R\right\} arr mathbb\left\{R\right\}$ given by

:

The set of all the $mathbf\left\{1\right\}_r$ functions is an uncountable set indexed by $mathbb\left\{R\right\}$.

References

ee also

* Index
* Indexed family

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Index set (recursion theory) — In the field of recursion theory, index sets describe classes of partial recursive functions, specifically they give all indices of functions in that class according to a fixed enumeration of partial recursive functions (a Gödel… …   Wikipedia

• index set — Math. a set whose elements are used to indicate the order of the elements of a sequence, series, etc. * * * …   Universalium

• index set — Math. a set whose elements are used to indicate the order of the elements of a sequence, series, etc …   Useful english dictionary

• Index (mathematics) — The word index is used in variety of senses in mathematics.* In perhaps the most frequent sense, an index is a superscript or subscript to a symbol. Superscript indices are often, but not always, used to indicate powers. Subscript indices are… …   Wikipedia

• Set for Life — Infobox Television show name = Set For Life caption = format = Game show starring = Jimmy Kimmel runtime = 60 Minutes creator = Dick de Rijk country = United States network = ABC executive producer = Scott St. John director = R. Brian DiPirro… …   Wikipedia

• SET Index — Stammdaten Staat Thailand Börse Stock Exchange of Thailand ISIN XC0009655199 WKN 965519 Symbol SETI RIC …   Deutsch Wikipedia

• Index of industrial production — (IIP) in simplest terms is index which details out the growth of various sectors in an economy. E.g. Indian IIP will focus on sectors like mining, electricity, Manufacturing General.Also base year needs to be decided on the basis of which all the …   Wikipedia

• Set — has 464 separate definitions in the Oxford English Dictionary, the most of any English word; its full definition comprises 10,000 words making it the longest definition in the OED. Set may refer to:In mathematics and science:*Set (mathematics), a …   Wikipedia

• index — in·dex 1 n: a numerical measure or indicator (as of inflation or economic performance) see also consumer price index index 2 vt: to link (as wages, rates, or investments) to an index under the contract wages were index ed to inflation M …   Law dictionary

• set-off — index counterclaim, drawback Burton s Legal Thesaurus. William C. Burton. 2006 set off …   Law dictionary