Iterated binary operation

In mathematics, an iterated binary operation is an extension of a binary operation on a setS to a function on finite sequences of elements of S through repeated application.^[1] Common examples include the extension of the addition operation to the summation operation, and the extension of the multiplication operation to the product operation. Other operations, e.g., the set-theoretic operations union and intersection, are also often iterated, but the iterations are not given separate names. In print, summation and product are represented by special symbols; but other iterated operators often are denoted by larger variants of the symbol for the ordinary binary operator. Thus, the iterations of the four operations mentioned above are denoted

${\displaystyle \sum ,\ \prod ,\ \bigcup ,}$ and ${\displaystyle \bigcap }$, respectively.

More generally, iteration of a binary function is generally denoted by a slash: iteration of ${\displaystyle f}$ over the sequence ${\displaystyle (a_{1},a_{2}\ldots ,a_{n})}$ is denoted by ${\displaystyle f/(a_{1},a_{2}\ldots ,a_{n})}$, following the notation for reduce in Bird–Meertens formalism.

In general, there is more than one way to extend a binary operation to operate on finite sequences, depending on whether the operator is associative, and whether the operator has identity elements.

Denote by a_j,k, with j ≥ 0 and k ≥ j, the finite sequence of length k−j of elements of S, with members (a_i), for j ≤ i<k. Note that if k = j, the sequence is empty.

For f : S × S → S, define a new function F_l on finite nonempty sequences of elements of S, where $${\displaystyle 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}}}$$

Similarly, define $${\displaystyle 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}}}$$

إذا كان للدالة f عنصر محايد أيسر فريد e ، فيمكن تعديل تعريف F _l ليعمل على المتتاليات الفارغة بتحديد قيمة F _l على متتالية فارغة لتكون e (وتصبح الحالة الأساسية السابقة على المتتاليات ذات الطول 1 زائدة). وبالمثل، يمكن تعديل F _r ليعمل على المتتاليات الفارغة إذا كان للدالة f عنصر محايد أيمن فريد.

إذا كانت f تجميعية، فإن F _l يساوي F _r ، ويمكننا ببساطة كتابة F. علاوة على ذلك، إذا كان هناك عنصر محايد e ، فإنه يكون وحيدًا (انظر Monoid ).

إذا كانت الدالة f تبديلية وتجميعية، فيمكن تطبيقها على أي مجموعة متعددة منتهية غير فارغة بتطبيقها على أي تعداد من عناصر تلك المجموعة. وإذا كانت f تحتوي على عنصر محايد e ، فإنه يُعرَّف بأنه قيمة F على مجموعة متعددة فارغة. وإذا كانت f دالة متطابقة، فيمكن تعميم التعريفات السابقة على المجموعات المنتهية .

إذا كانت المجموعة S مزودة أيضًا بمقياس، أو بشكل أعم، بطوبولوجيا هاوسدورف ، بحيث يُعرَّف مفهوم نهاية متتالية في S _، فإن التكرار اللانهائي على متتالية قابلة للعد في S يُعرَّف تحديدًا عندما تتقارب المتتالية المقابلة من التكرارات المحدودة. على سبيل المثال، إذا كانت a₀ _, a₁ , a₂ _, a₃ , ... متتالية لانهائية من _{الأعداد} الحقيقية ، فإن حاصل الضرب اللانهائي  ${\textstyle \prod _{i=0}^{\infty }a_{i}}$يتم تعريفها، وهي تساوي${\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n}a_{i},}$إذا وفقط إذا كان هذا الحد موجودًا.

تُعطى العملية الثنائية العامة غير الترابطية بواسطة ماغما . ويمكن تمثيل عملية التكرار على عملية ثنائية غير ترابطية بشجرة ثنائية .

تُكتب عملية العد الثنائي المتكررة على النحو التالي:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}}$

معنى الرموز:

رمز	معنى
${\displaystyle \bigstar }$	رمز العملية الثنائية المتكررة
${\displaystyle k}$	متغير المؤشر
${\displaystyle k=1}$	الحد الأدنى
${\displaystyle k=n}$أو${\displaystyle n}$	الحد الأعلى
${\displaystyle a_{k}}$	العنصر رقم k

مثال:

${\displaystyle \mathop {\bigstar } _{k=1}^{4}a_{k}=\mathop {\bigstar } _{k=1}^{k=4}a_{k}=a_{1}\star a_{2}\star a_{3}\star a_{4}}$

الشكل العام:

${\displaystyle \mathop {\bigstar } _{k\in K}a_{k}}$

نموذج مقيد:

${\displaystyle \mathop {\bigstar } _{1\leq k\leq n \atop k\equiv 0{\pmod {2}}}a_{k}}$

النسخة اللانهائية:

${\displaystyle \mathop {\bigstar } _{k=1}^{\infty }a_{k}=\mathop {\bigstar } _{k=1}^{k\to \infty }a_{k}}$

يترك${\displaystyle (S,\star )}$أن يكون هيكلًا ذا عملية تجميعية${\displaystyle \star }$:

• عنصر واحد:

${\displaystyle \mathop {\bigstar } _{k=n}^{n}a_{k}=a_{n}}$

• توسع:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star a_{2}\star \dots \star a_{n}}$

• التكرار:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\left(\mathop {\bigstar } _{k=1}^{n-1}a_{k}\right)\star a_{n}}$

• الاستدعاء الذاتي الأيمن:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=a_{1}\star \left(\mathop {\bigstar } _{k=2}^{n}a_{k}\right)}$

• التقسيم:

${\displaystyle \left(\mathop {\bigstar } _{k=1}^{m}a_{k}\right)\star \left(\mathop {\bigstar } _{k=m+1}^{n}a_{k}\right)=\mathop {\bigstar } _{k=1}^{n}a_{k}}$

• ثبات التبديل:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a_{k}=\mathop {\bigstar } _{k=1}^{n}a_{\sigma (k)}}$

• المنتج الفارغ (المونويد):

${\displaystyle \mathop {\bigstar } _{k=1}^{0}a_{k}=e}$

• التكرار:

لو${\displaystyle a\star a=a}$، ثم${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a}$

• تسلسل ثابت:

${\displaystyle \mathop {\bigstar } _{k=1}^{n}a=a\star \cdots \star a}$

لو${\displaystyle (S,\star ,e)}$إذا كان أحاديًا ، فإن:

• المنتج الفارغ = عنصر الهوية
• المجموع الفارغ = 0 (في أحاديات الحساب)

في البرمجة الوظيفية، تتوافق العمليات الثنائية المتكررة مع الدوال ذات الرتبة الأعلى مثل الطي أو الاختزال .

• عملية أحادية
• دالة أحادية
• العملية الثنائية
• الدالة الثنائية
• عملية جراحية ثالثية

• إجراءات جماعية
• عملية البادئة المتوازية. مؤرشفة بتاريخ 3 يونيو 2013 في أرشيف الإنترنت (Wayback Machine) .
• عمليات ثنائية متكررة باستخدام Nuprl. مؤرشف بتاريخ 3 مارس 2016 في Wayback Machine.