Itererad binär operation

I matematik är en itererad binär operation en förlängning av en binär operation på en mängd S till en funktion på ändliga sekvenser av element i S genom upprepad tillämpning. Vanliga exempel inkluderar utvidgningen av additionsoperationen till summeringsoperationen och utvidgningen av multiplikationsoperationen till produktoperationen . Andra operationer, t.ex. den mängdteoretiska operationsunionen och skärningspunkten , itereras också ofta , men iterationerna ges inte separata namn. I tryck representeras summering och produkt av speciella symboler; men andra itererade operatorer betecknas ofta med större varianter av symbolen för den vanliga binära operatorn. Således betecknas iterationerna av de fyra ovan nämnda operationerna

$\sum ,\ \prod ,\ \bigcup ,$ respektive $\bigcap$ .

Mer allmänt betecknas iteration av en binär funktion i allmänhet med ett snedstreck: iteration av $f$ över sekvensen $(a_{1},a_{2} \ldots ,a_{n})$ betecknas med $f/(a_{1},a_{2}\ldots ,a_{n})$ , efter notationen för reducera i Bird–Meertens formalism .

I allmänhet finns det mer än ett sätt att utöka en binär operation till att fungera på ändliga sekvenser, beroende på om operatorn är associativ och om operatorn har identitetselement .

Definition

Beteckna med a _{j , k} , med j ≥ 0 och k ≥ j , den ändliga sekvensen av längden k − j av element av S , med medlemmar ( a _i ), för j ≤ i < k . Observera att om k = j är sekvensen tom.

För f : S × S , definiera en ny funktion F _l på ändliga icke-tomma sekvenser av element i S , där

$$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}}$$

På samma sätt, definiera

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

Om f har en unik vänsteridentitet e , kan definitionen av Fl modifieras så att den fungerar på tomma sekvenser genom _att definiera värdet på Fl på en tom sekvens till e (det tidigare basfallet på sekvenser med längd 1 blir redundant) _. På liknande sätt kan F _r modifieras för att fungera på tomma sekvenser om f har en unik rätt identitet.

Om f är associativ, är F _l lika med F _r , och vi kan helt enkelt skriva F . Dessutom, om ett identitetselement e existerar, är det unikt (se Monoid ).

Om f är kommutativ och associativ, så kan F verka på vilken icke-tom finit multimängd som helst genom att applicera den på en godtycklig uppräkning av multimängden. Om f dessutom har ett identitetselement e , så definieras detta som värdet av F på en tom multiset. Om f är idempotent kan ovanstående definitioner utvidgas till finita mängder .

₀  Om S också är utrustad med en metrik eller mer allmänt med topologi som är Hausdorff , så att begreppet en gräns för en sekvens definieras i S , så definieras en oändlig iteration på en räknebar sekvens i S exakt när motsvarande sekvens av ändliga iterationer konvergerar. Således, t.ex. om a , a ₁ , a ₂ , a ₃ , … är en oändlig sekvens av reella tal , då är den oändliga produkten ${\textstyle \prod _{i=0}^{\infty }a_{i}}$ är definierad och lika med ${\textstyle \lim \limits _{n\to \infty }\prod _{i=0}^{n} a_{i},}$ om och bara om den gränsen finns.

Icke-associativ binär operation

Den allmänna, icke-associativa binära operationen ges av en magma . Handlingen att iterera på en icke-associativ binär operation kan representeras som ett binärt träd .

Notation

  Itererade binära operationer används för att representera en operation som kommer att upprepas över en uppsättning med vissa begränsningar. Vanligtvis skrivs den nedre gränsen för en begränsning under symbolen och den övre gränsen över symbolen, även om de också kan skrivas som upphöjda och nedsänkta i kompakt notation. Interpolation utförs över positiva heltal från den nedre till den övre gränsen, för att producera mängden som kommer att ersättas i indexet (nedan betecknat i ) för de upprepade operationerna.

notationerna big S igma ( upprepad produkt ) upprepad summa ) . och big Pi (

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

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

Det är möjligt att specificera uppsättningsmedlemskap eller andra logiska begränsningar istället för explicita index, för att implicit specificera vilka element i en uppsättning som ska användas:

$$\sum _{x\in S}x=x_{1}+x_{2}+x_{3}+\dots +x_{n}$$

Flera villkor kan skrivas antingen sammanfogade med en logisk och eller separat:

$$\sum _{(i\in 2\mathbb {N} )\wedge (i\leq n)}i=\summa _{\stackrel {i\in 2\mathbb {N} }{i\leq n}}i=0+2+4+\dots +n$$

Mindre vanligt kan alla binära operatorer som exklusiv eller ( $\oplus$ ) eller set union ( ${\displaystyle \cup } )$ också användas. Till exempel, om S är en uppsättning logiska propositioner :

$$\bigwedge _{p\in S}p=p_{1}\wedge p_{2}\wedge \dots \wedge p_{N}$$

vilket är sant om alla element i S är sanna.

Se även

• Fortsatt bråkdel
• Vik (högre ordningsfunktion)
• Oändlig produkt
• Oändlig serie

externa länkar

• Bulkåtgärd
• Parallell prefixoperation Arkiverad 2013-06-03 på Wayback Machine
• Nuprl itererade binära operationer