Index set

<h2 id="examples">Examples</h2>
<ul><li>An <a href="/facts/Enumeration/EFmP9zL6">enumeration</a> of a set S gives an index set 
  
    
      
        J
        ⊂
        
          N
        
      
    
    {\displaystyle J\subset \mathbb {N} }
  
, where <i>f</i> : <i>J</i> → <i>S</i> is the particular enumeration of <i>S</i>.</li>
<li>Any <a href="/facts/Countably_infinite/Wj4DmWPv">countably infinite</a> set can be (injectively) indexed by the set of <a href="/facts/Natural_numbers/u65og8JE">natural numbers</a> 
  
    
      
        
          N
        
      
    
    {\displaystyle \mathbb {N} }
  
.</li>
<li>For 
  
    
      
        r
        ∈
        
          R
        
      
    
    {\displaystyle r\in \mathbb {R} }
  
, the <a href="/facts/Indicator_function/QEuh04NM">indicator function</a> on <i>r</i> is the function 
  
    
      
        
          
            1
          
          
            r
          
        
        :
        
          R
        
        →
        {
        0
        ,
        1
        }
      
    
    {\displaystyle \mathbf {1} _{r}\colon \mathbb {R} \to \{0,1\}}
  
 given by 
  
    
      
        
          
            1
          
          
            r
          
        
        (
        x
        )
        :=
        
          
            {
            
              
                
                  0
                  ,
                
                
                  
                    
                      if 
                    
                  
                  x
                  ≠
                  r
                
              
              
                
                  1
                  ,
                
                
                  
                    
                      if 
                    
                  
                  x
                  =
                  r
                  .
                
              
            
            
          
        
      
    
    {\displaystyle \mathbf {1} _{r}(x):={\begin{cases}0,&{\mbox{if }}x\neq r\\1,&{\mbox{if }}x=r.\end{cases}}}
  
</li></ul>
<p>The set of all such indicator functions, 
  
    
      
        {
        
          
            1
          
          
            r
          
        
        
          }
          
            r
            ∈
            
              R
            
          
        
      
    
    {\displaystyle \{\mathbf {1} _{r}\}_{r\in \mathbb {R} }}
  
, is an <a href="/facts/Uncountable_set/zl2WqyJQ">uncountable set</a> indexed by 
  
    
      
        
          R
        
      
    
    {\displaystyle \mathbb {R} }
  
.
</p>
<h2 id="other-uses">Other uses</h2>
<p>In <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity theory</a> and <a href="/facts/Cryptography/e94PEVau">cryptography</a>, an index set is a set for which there exists an algorithm I that can sample the set efficiently; e.g., on input 1<i>n</i>, I can efficiently select a poly(n)-bit long element from the set.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Friendly-index_set/nvmC907e">Friendly-index set</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Weisstein, Eric. "Index Set". Wolfram MathWorld. Wolfram Research. Retrieved 30 December 2013. <a href="http://mathworld.wolfram.com/IndexSet.html" target="_blank">http://mathworld.wolfram.com/IndexSet.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Munkres, James R. (2000). Topology. Vol. 2. Upper Saddle River: Prentice Hall. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Goldreich, Oded (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press. ISBN 0-521-79172-3. <a href="0-521-79172-3" target="_blank">0-521-79172-3</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
</ol>

Index set open-in-new

Index set