Himpunan indeks

Dalam matematika, himpunan indeks adalah himpunan dengan anggota label (atau indeks) merupakan anggota dari himpunan lain.^[1][2] Sebagai contoh, jika anggota dari himpunan A diindeks atau dilabel dengan anggota dari himpunan J, maka J adalah himpunan indeks. Pengindeksan tersebut melibatkan fungsi surjektif dari J ke A, dan kumpulan indeks biasanya disebut keluarga (berindeks), atau secara umum dinyatakan sebagai { A j } j ∈ J {\displaystyle \{A_{j}\}_{j\in J}} .

Contoh

• Enumerasi dari himpunan S menghasilkan himpunan indeks J ⊂ N {\displaystyle J\subset \mathbb {N} } , dengan f : J → S adalah enumerasi khusus dari S.
• Setiap himpunan tak terhingga dan tercacahkan dapat (secara injektif) diindeks dengan himpunan bilangan asli N {\displaystyle \mathbb {N} } .
• Untuk r ∈ R {\displaystyle r\in \mathbb {R} } , fungsi indikator pada r adalah fungsi 1 r : R → { 0 , 1 } {\displaystyle \mathbf {1} _{r}\colon \mathbb {R} \rightarrow \{0,1\}} , yang dinyatakan dengan

1 r ( x ) := { 0 , jika  x ≠ r 1 , jika  x = r . {\displaystyle \mathbf {1} _{r}(x):={\begin{cases}0,&{\mbox{jika }}x\neq r\\1,&{\mbox{jika }}x=r.\end{cases}}}

Himpunan dari semua fungsi indikator, { 1 r } r ∈ R {\displaystyle \{\mathbf {1} _{r}\}_{r\in \mathbb {R} }} , adalah himpunan ketaktercacahan yang diindeks R {\displaystyle \mathbb {R} } .

Kegunaan lain

Dalam teori kompleksitas komputasi dan kriptografi, himpunan indeks adalah himpunan yang di dalamnya terdapat algoritma I yang dapat mengambil percontohan himpunan secara efisien; yaitu pada 1ⁿ, I dapat dengan mudah memilih elemen panjang poli(n)-bit dari himpunan.^[3]

Referensi