Operasi biner teriterasi

Dalam matematika, operasi biner berulang adalah sebuah perpanjangan dari sebuah operasi biner pada sebuah himpunan $S$ ke sebuah fungsi pada barisan terbatas dari anggota $S$ melalui penggunaan berulang. Contoh saat ini termasuk perpanjangan dari operasi penjumlahan hingga operasi notasi Sigma, dan perpanjangan dari operasi perkalian hingga operasi produk. Operasi lainnya, misalnya, teori-teori himpunan operasi gabungan dan irisan, juga sering diulang, tapi pengulangan tidak diberikan nama terpisah. Dalam cetakan, notasi Sigma dan produk diwakili oleh simbol yang spesial, namun operator berulang lainnya sering kali dilambangkan oleh variasi yang besar dari simbol untuk operator biner biasa. Demikian, pengulangan dari empat operasi disebutkan di atas dilambangkan

$\sum ,\ \prod ,\ \bigcup ,$ dan $\bigcap$, masing-masing.

Lebih umum, pengulangan dari sebuah fungsi biner secara umum dilambangkan oleh sebuah garis miringː pengulangan dari $f$ di barisan $(a_{1},a_{2}\ldots ,a_{n})$ dilambangkan $f/(a_{1},a_{2}\ldots ,a_{n})$, berikut notasi untuk mengurangi dalam formalisme Bird-Meertens.

Secara umum, terdapat lebih daripada satu cara untuk memperpanjang sebuah operasi biner untuk mengoperasikan pada barisan terbatas, tergantung apakah operator asosiatif, dan apakah operator memiliki anggota identitas.

Definisi

Dilambangkan oleh $\mathbf {a} _{j,k}$, dengan $j\geq 0$ dan $k\geq j$, barisan terbatas dari panjang $k-j$ dari anggota $S$, dengan anggota $(a_{i})$, untuk $j\leq i<k$. Catatan bahwa jika $k=j$, barisannya kosong.

Untuk $f:S\times S$, mendefinisikan sebuah fungsi baru $F_{l}$ pada barisan tidak kosong terbatas dari anggota-anggota $S$, dimana

$F_{l}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(F_{l}(\mathbf {a} _{0,k-1}),a_{k-1}),&k>1\end{cases}}.$

Demikian pula, mendefinisikan

$F_{r}(\mathbf {a} _{0,k})={\begin{cases}a_{0},&k=1\\f(a_{0},F_{r}(\mathbf {a} _{1,k})),&k>1\end{cases}}.$

Jika $f$ memiliki sebuah identitas kiri yang unik $e$, definisi dari $F_{l}$ bisa diubah untuk mengoperasikan pada barisan kosong dengan mendefinisikan nilai dari $F_{l}$ pada sebuah barisan kosong menjadi $e$ (kasus dasar sebelumnya pada barisan-barisan dari panjang 1 menjadi redundan). Demikian pula, $F_{r}$ bisa diubah untuk mengoperasikan pada barisan kosong jika $f$ memiliki sebuah identitas kanan yang unik.

Jika $f$ asosiatif. maka $F_{l}$ sama dengan $F_{r}$, dan kita bisa cukup tulis $F$. Bahkan, jika sebuah identitas anggota $e$ada, maka itu adalah unik (lihat Monoid).

Jika $f$ komutatif dan asosiatif, maka $F$ beroperasi pada setiap multihimpunan terbatas tidak kosong dengan menerapkannya ke sebuah enumerasi sembarang dari multihimpunan. Jika $f$ bahkan memiliki sebuah anggota identitas $e$, maka ini didefinisikan menjadi nilai $F$ pada sebuah multihimpunan kosong. Jika $f$ idempoten, maka definisi diatas bisa diperpanjang menjadi himpunan terbatas.

Jika $S$ juga dilengkapi dengan sebuah metrik atau lebih umumnya dengan topologi yaitu Hausdorff, jadi konsep dari sebuah limit pada sebuah barisan didefinisikan dalam $S$, maka sebuah pengulangan tak terbatas pada sebuah barisan yang dapat dihitung dalam $S$ didefinisikan dengan tepat ketika barisan yang sesuai dari pengulangan terbatas konvergen. Demikian, misalnya, jika $a_{0},a_{1},a_{2},a_{3},\dots$ adalah barisan tak terbatas dari bilangan real, maka produk tak terbatas $\prod _{i=0}^{\infty }a_{i}$ didefinisikan, dan sama dengan $\lim _{n\to \infty }\prod _{i=0}^{\infty }a_{i}$, jika dan hanya jika limit itu ada.

Operasi biner non-asosiatif

Hal yang umum, operasi biner non-asosiatif diberikan oleh sebuah magma. Tindakan pengulangan pada sebuah operasi biner berulang dapat diwakili sebagai sebuah pohon biner.

Notasi

Operasi biner berulang digunakan untuk mewakili sebuah operasi yang akan berulang-ulang sebuah subjek himpunan untuk beberapa kendala. Biasanya batas bawah dari sebuah batasan ditulis di bawah simbol, dan batas atas di atas simbol, meskipun mereka mungkin juga ditulis sebagai superskrip dan subskrip dalam notasi kompak. Interpolasi dilakukan selama bilangan bulat positif dari batas bawah ke batas atas, untuk menghasilkan himpunan yang akan diganti menjadi indeks (di bawah dilambangkan sebagai $i$) untuk operasi pengulangan. Ini mungkin untuk menentukan keanggotaan himpunan atau kendala logis lainnya di tempat indeks yang eksplisit, untuk menentukan implikasinya dimana anggota-anggota dari sebuah himpunan akan digunakan.

Notasi-notasi umum termasuk notasi Sigma besar (penjumlahan berulang) dan notasi Pi besar (perkalian berulang).

$\sum _{i=0}^{n-1}i=0+1+2+\dots +(n-1)$

$\prod _{i=0}^{n-1}i=0\times 1\times 2\times \dots \times (n-1)$

Meskipun operator biner termasuk tidak terbatas pada eksklusif atau dan gabungan himpunan dapat digunakan.

Misalkan $S$ adalah sebuah himpunan dari himpunan-himpunan

$\bigcup _{s\in S}s_{i}=s_{1}\cup s_{2}\cup \dots \cup s_{N}$.

Misalkan $S$ adalah himpunan dari proposisi logis

$\bigoplus _{s\in S}s_{i}=s_{1}\oplus s_{2}\oplus \dots \oplus s_{N}$.

Misalkan $S$ adalah himpunan dari multivektor dalam sebuah aljabar Clifford/aljabar geometris

$\bigwedge _{s\in S}s_{i}=s_{1}\wedge s_{2}\wedge \dots \wedge s_{N}$

$\prod _{s\in S}s_{i}=s_{1}s_{2}\dots s_{N}$

Perhatikan caranya di atas, tidak ada batas atas digunaan, karena itu sudah cukup untuk mengekspresikan bahwa anggota $s_{i}$ adalah anggota dari himpunan $S$.

Ini juga untuk menghasilkan sebuah operasi berulang diberikan sebuah jumlah kendala yang digabungkan oleh sebuah konjungsi (dan), sebagai contohː

$\sum _{(i\in 2\mathbb {N} )\wedge (i\leq n)}i=0+2+4+\dots +n$, yang mungkin juga dilambangkan $\sum _{\begin{array}{c}i\in 2\mathbb {N} \\i\leq n\end{array}}i=0+2+4+\dots +n$.

Lihat pula

• Deret produk
• Fold (fungsi tingkat tinggi)
• Pecahan berlanjut
• Produk tak terbatas

Pranala luar

• Bulk action
• Parallel prefix operation Diarsipkan 2013-06-03 di Wayback Machine.
• Nuprl iterated binary operations