Difference between revisions of "Index set"

From formulasearchengine
Jump to navigation Jump to search
en>Lifeonahilltop
 
en>APerson
m (Moved a phrase into parentheses in first sentence)
Line 1: Line 1:
In [[mathematics]], the elements of a [[Set (mathematics)|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|(indexed) family]]'', often written as (''A''<sub>''j''</sub>)<sub>''j''∈''J''</sub>.
+
{{one source|date=December 2013}}
 +
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 [[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.
+
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>
<ref>
 
 
{{cite book  
 
{{cite book  
 
   | title= Foundations of Cryptography: Volume 1, Basic Tools
 
   | title= Foundations of Cryptography: Volume 1, Basic Tools
Line 10: Line 10:
 
   |publisher= Cambridge University Press
 
   |publisher= Cambridge University Press
 
   |isbn= 0-521-79172-3
 
   |isbn= 0-521-79172-3
}}
+
}}</ref>
</ref>
 
  
 
==Examples==
 
==Examples==
Line 24: Line 23:
  
 
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>.
 
==References==
 
<references/>
 
  
 
==See also==
 
==See also==
 
 
* [[Friendly-index set]]
 
* [[Friendly-index set]]
 
* [[Indexed family]]
 
* [[Indexed family]]
  
 +
==References==
 +
{{Reflist}}
  
 
[[Category:Mathematical notation]]
 
[[Category:Mathematical notation]]
 
[[Category:Basic concepts in set theory]]
 
[[Category:Basic concepts in set theory]]
 
[[de:Familie (Mathematik)]]
 
[[it:Famiglia (matematica)]]
 
[[hu:Halmazrendszer]]
 
[[nl:Indexverzameling]]
 
[[ja:添字記法]]
 
[[no:Familie (matematikk)]]
 
[[zh:索引集]]
 

Revision as of 22:53, 30 December 2013

Template:One source In mathematics, an index set is a set whose members label (or index) members of another set.[1] 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.

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

Examples

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

See also

References

  1. Template:Cite web
  2. {{#invoke:citation/CS1|citation |CitationClass=book }}