インデックスセット

数学において、添字集合とは、その要素が別の集合の要素にラベル（または添字）を付ける集合のことである。 ^[1]^[2]例えば、集合 $Aの要素が集合$ $J$ の要素によって添字付けまたはラベル付けできる場合、 $J$ は添字集合である。添字付けは $J$ から $A$ への射影関数から成り、添字付けされた集合は一般に添字族と呼ばれ、しばしば ${$ $A$ $j$ $}$ $j$ $\in$ $J$ と表記される。

例

集合 $S$ の列挙はインデックス集合を与える。ここで $f$ $:$ $J$ $\to$ $Sは$ $S$ の特定の列挙である。 $J\subset \mathbb {N}$
任意の可算無限集合は、自然数の集合によって（単射的に）インデックス付けできます。 $\mathbb {N}$
の場合、 $r$ 上の指示関数は次式で与えられる関数である。 $r\in \mathbb {R}$ $\mathbf {1} _{r}\colon \mathbb {R} \to \{0,1\}$ $\mathbf {1} _{r}(x):={\begin{cases}0,&{\mbox{if }}x\neq r\\1,&{\mbox{if }}x=r.\end{cases}}$

このような指示関数すべての集合は、でインデックス付けされた不可算集合です。 $\{\mathbf {1} _{r}\}_{r\in \mathbb {R} }$ $\mathbb {R}$

その他の用途

計算複雑性理論と暗号学において、インデックスセットとは、そのセット $を$ 効率的にサンプリングできるアルゴリズム $Iが存在するセットのことである。例えば、入力$ $1n$ に対して、そのセットからポリ(n)ビット長の要素を効率的に選択することが $できる$ 。^[3]

参照

フレンドリーインデックスセット

参考文献

^ Weisstein, Eric. 「Index Set」. Wolfram MathWorld . Wolfram Research . 2013年12月30日閲覧。
^ マンクレス、ジェームズ・R. (2000).トポロジー第2巻. アッパーサドルリバー: プレンティスホール.
^ Goldreich, Oded (2001). 『暗号の基礎：第1巻、基本ツール』ケンブリッジ大学出版局. ISBN 0-521-79172-3。

[1] Weisstein, Eric. 「Index Set」. Wolfram MathWorld . Wolfram Research . 2013年12月30日閲覧。

[2] マンクレス、ジェームズ・R. (2000).トポロジー第2巻. アッパーサドルリバー: プレンティスホール.

[3] Goldreich, Oded (2001). 『暗号の基礎：第1巻、基本ツール』ケンブリッジ大学出版局. ISBN 0-521-79172-3。