Набор индексов

Не путать с индексированными наборами наборами индексов в или теории вычислимости .

В математике индексный набор — это набор, члены которого обозначают (или индексируют) элементы другого набора. Например, если элементы набора A могут быть проиндексированы или помечены с помощью элементов набора J , то J является набором индексов. Индексирование состоит из сюръективной функции из J на ​​A индексированный набор обычно называется индексированным семейством , часто записываемым как { A _j } _{j ∈ J.} , а

Примеры

• Перечисление S набора дает набор индексов $J\subset \mathbb {N}$, где : J → S — частная нумерация S. f
• Любое счетное бесконечное множество может быть (инъективно) проиндексировано множеством натуральных чисел . $\mathbb {N}$.
• Для $r\in \mathbb {R}$, индикаторной функцией на 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 , который может эффективно выбирать набор; например, на входе 1 ^н , я могу эффективно выбрать поли(n)-битный длинный элемент из набора.

См. также

• Набор дружественных индексов