Difference between revisions of "Index set"

From formulasearchengine
Jump to navigation Jump to search
en>APerson
m (Moved a phrase into parentheses in first sentence)
en>Brirush
(Added reference)
 
Line 1: Line 1:
{{one source|date=December 2013}}
+
{{distinguish|Indexed set}}
In [[mathematics]], an '''index set''' is a set whose members label (or index) members of another set.<ref>{{cite web|last=Weisstein|first=Eric|title=Index Set|url=http://mathworld.wolfram.com/IndexSet.html|work=Wolfram MathWorld|publisher=Wolfram Research|accessdate=30 December 2013}}</ref> For instance, if the elements of a [[Set (mathematics)|set]] ''A'' may be ''indexed'' or ''labeled'' by means of a set ''J'', then ''J'' is an index set.  The indexing consists of a [[surjective function]] from ''J'' onto ''A'' and the indexed collection is typically called an ''[[indexed family|(indexed) family]]'', often written as (''A''<sub>''j''</sub>)<sub>''j''∈''J''</sub>.
+
In [[mathematics]], an '''index set''' is a set whose members label (or index) members of another set.<ref>{{cite web|last=Weisstein|first=Eric|title=Index Set|url=http://mathworld.wolfram.com/IndexSet.html|work=Wolfram MathWorld|publisher=Wolfram Research|accessdate=30 December 2013}}</ref><ref>Munkres, James R. Topology. Vol. 2. Upper Saddle River: Prentice Hall, 2000.</ref> For instance, if the elements of a [[Set (mathematics)|set]] ''A'' may be ''indexed'' or ''labeled'' by means of a set ''J'', then ''J'' is an index set.  The indexing consists of a [[surjective function]] from ''J'' onto ''A'' and the indexed collection is typically called an ''[[indexed family|(indexed) family]]'', often written as (''A''<sub>''j''</sub>)<sub>''j''∈''J''</sub>.
 
 
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 1<sup>n</sup>, ''I'' can efficiently select a poly(n)-bit long element from the set.<ref>
 
{{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
 
}}</ref>
 
  
 
==Examples==
 
==Examples==
Line 23: Line 13:
  
 
The set of all the <math>\mathbf{1}_r</math> functions <!--(which happens to be a [[basis]] for the [[vector space]] of all functions on <math>\mathbb{R}</math> over <math>\mathbb{R}</math>)--> is an [[uncountable set]] indexed by <math>\mathbb{R}</math>.
 
The set of all the <math>\mathbf{1}_r</math> functions <!--(which happens to be a [[basis]] for the [[vector space]] of all functions on <math>\mathbb{R}</math> over <math>\mathbb{R}</math>)--> is an [[uncountable set]] indexed by <math>\mathbb{R}</math>.
 +
 +
==Other uses==
 +
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 1<sup>n</sup>, ''I'' can efficiently select a poly(n)-bit long element from the set.<ref>
 +
{{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
 +
}}</ref>
  
 
==See also==
 
==See also==

Latest revision as of 12:34, 25 November 2014

Template:Distinguish In mathematics, an index set is a set whose members label (or index) members of another set.[1][2] For instance, if the elements of a set A may be indexed or labeled by means of a set J, then J is 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)jJ.

Examples

The set of all the functions is an uncountable set indexed by .

Other uses

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.[3]

See also

References

  1. Template:Cite web
  2. Munkres, James R. Topology. Vol. 2. Upper Saddle River: Prentice Hall, 2000.
  3. {{#invoke:citation/CS1|citation |CitationClass=book }}