Itereret binær operation - Iterated binary operation

I matematik er en itereret binær operation en udvidelse af en binær operation på et sæt S til en funktion på endelige sekvenser af elementer af S gennem gentagen anvendelse. Almindelige eksempler inkluderer udvidelsen af tilføjelsesoperationen til summeringsoperationen og udvidelsen af multiplikationsoperationen til produktoperationen . Andre operationer, fx den indstillede teoretiske operationer union og kryds , er også ofte gentages , men de iterationer er ikke givet særskilte navne. I tryk er summation og produkt repræsenteret af specielle symboler; men andre itererede operatører betegnes ofte med større varianter af symbolet for den almindelige binære operatør. Således er gentagelserne af de fire ovennævnte operationer angivet

{\ displaystyle \ sum, \ \ prod, \ \ bigcup,}

og henholdsvis.

{\ displaystyle \ bigcap}

Mere generelt betegnes iteration af en binær funktion generelt med en skråstreg: iteration af over sekvensen betegnes ved at følge notationen for reduktion i Bird-Meertens formalisme . ${\ displaystyle f}$ ${\ displaystyle (a_ {1}, a_ {2} \ ldots, a_ {n})}$ ${\ displaystyle f / (a_ {1}, a_ {2} \ ldots, a_ {n})}$

Generelt er der mere end en måde at udvide en binær operation til at operere på endelige sekvenser afhængigt af om operatøren er associerende , og om operatøren har identitetselementer .

Definition

Betegn med a _{j , k} , med j ≥ 0 og k ≥ j , den endelige sekvens af længden k - j af elementerne i S , med medlemmer ( a _i ), for j ≤ i < k . Bemærk, at hvis k = j , er sekvensen tom.

For f : S × S , definerer en ny funktion F _l på finite nonempty sekvenser af elementer af S , hvor

{\ 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}}}

Tilsvarende definer

{\ 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}}}

Hvis f har en unik venstre identitet e , definitionen af F _l kan modificeres til at operere på tomme sekvenser ved at definere værdien af F _l på en tom sekvens at være e (den tidligere grundmodel sekvenser af længde 1 bliver overflødigt). Tilsvarende F _r kan modificeres til at operere på tomme sekvenser hvis f har en unik ret identitet.

Hvis f er associativ, så F _l er lig med F _r , og vi kan simpelthen skrive F . Desuden, hvis der findes et identitetselement e , er det unikt (se monoid ).

Hvis f er kommutativ og associerende, kan F fungere på ethvert ikke-tomt endeligt multisæt ved at anvende det på en vilkårlig optælling af multisettet. Hvis f desuden har et identitetselement e , er dette defineret til at være værdien af F på et tomt multisæt. Hvis f er idempotent, kan ovenstående definitioner udvides til endelige sæt .

Hvis S også er udstyret med en metrisk eller mere generelt med topologi, der er Hausdorff , således at begrebet en grænse for en sekvens er defineret i S , så defineres en uendelig iteration på en tællbar sekvens i S nøjagtigt, når den tilsvarende sekvens af endelige iterationer konvergerer. Således, f.eks. Hvis en ₀ , en ₁ , en ₂ , en ₃ , ... er en uendelig rækkefølge af reelle tal , så defineres det uendelige produkt og er lig med, hvis og kun hvis denne grænse eksisterer. ${\ textstyle \ prod _ {i = 0} ^ {\ infty} a_ {i}}$ ${\ textstyle \ lim \ limit _ {n \ to \ infty} \ prod _ {i = 0} ^ {n} a_ {i},}$

Ikke-associerende binær operation

Den generelle, ikke-associerende binære operation er givet af en magma . Handlingen med at gentage en ikke-associerende binær operation kan repræsenteres som et binært træ .

Notation

Itererede binære operationer bruges til at repræsentere en operation, der gentages over et sæt med forbehold for nogle begrænsninger. Typisk er den nedre grænse for en begrænsning skrevet under symbolet, og den øvre grænse over symbolet, skønt de også kan skrives som overskrifter og abonnementer i kompakt notation. Interpolering udføres over positive heltal fra den nedre til den øvre grænse for at producere det sæt, der vil blive erstattet af indekset (nedenfor betegnet som i ) for de gentagne operationer. Det er muligt at specificere sætmedlemskab eller andre logiske begrænsninger i stedet for eksplicitte indekser for implicit at specificere, hvilke elementer i et sæt der skal bruges.

Fælles notationer omfatter den store S igma ( gentaget s um ) og store P i ( gentaget p rodukt ) notationer.

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

{\ displaystyle \ prod _ {i = 0} ^ {n-1} i = 0 \ gange 1 \ gange 2 \ gange \ prikker \ gange (n-1)}

Selvom binære operatorer , herunder men ikke begrænset til udelukkende eller og sæt union kan anvendes.

Lad S være et sæt sæt

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

Lad S være et sæt logiske forslag

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

Lad S være et sæt multivektorer i en Clifford-algebra / geometrisk algebra

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

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

Bemærk hvordan i det ovenstående, ikke nogen øvre bundet anvendes, fordi det er tilstrækkeligt at udtrykke, at elementerne er elementer i sættet S . ${\ displaystyle s_ {i}}$

Det er også at producere en gentagen operation givet et antal begrænsninger forbundet med en sammenhæng (og) , for eksempel:

{\ displaystyle \ sum _ {(i \ i 2 \ mathbb {N}) \ wedge (i \ leq n)} i = 0 + 2 + 4 + \ dots + n,}

som også kan betegnes

{\ displaystyle \ sum _ {\ stackrel {i \ i 2 \ mathbb {N}} {i \ leq n}} i = 0 + 2 + 4 + \ dots + n.}

Se også

Referencer

^ Saunders MacLane (1971). Kategorier for den arbejdende matematiker . New York: Springer-Verlag. s. 142. ISBN 0387900357.
^ Weisstein, Eric W. "Union" . mathworld.wolfram.com . Wolfram Mathworld . Hentet 30. januar 2018 .

eksterne links

[IBO1-1] Saunders MacLane (1971). Kategorier for den arbejdende matematiker . New York: Springer-Verlag. s. 142. ISBN 0387900357.

[2] Weisstein, Eric W. "Union" . mathworld.wolfram.com . Wolfram Mathworld . Hentet 30. januar 2018 .

Languages

In other projects