TheoremBase

Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms

An iterated operation obeys its recursion; for an associative operation it splits into the iterated operations of two consecutive blocks; for an associative and commutative operation it is unchanged by reordering the terms and combines termwise; and maps preserving the operation preserve iterated operations.

Statement

In the setting of The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion, let ∗\ast be a binary operation on a set XX, let m,n∈Nm,n\in\mathbb{N}, and let iterated operations be as in Iterated Operations: Finite Sums and Finite Products §iterated and Iterated Operations: Finite Sums and Finite Products §restriction.

For a:[n]→Xa:[n]\to X, ∗k=11ak=a1\mathop{\ast}\limits_{k=1}^{1}a_{k}=a_{1}; and for a:[n+1]→Xa:[n+1]\to X, ∗k=1n+1ak=(∗k=1nak)∗an+1\mathop{\ast}\limits_{k=1}^{n+1}a_{k}=\Big(\mathop{\ast}\limits_{k=1}^{n}a_{k}\Big)\ast a_{n+1}.

Let ⋄\diamond be a binary operation on a set YY and φ:X→Y\varphi:X\to Y a map with φ(x∗y)=φ(x)⋄φ(y)\varphi(x\ast y)=\varphi(x)\diamond\varphi(y) for all x,y∈Xx,y\in X. For a:[n]→Xa:[n]\to X, φ(∗k=1nak)=⋄k=1nφ(ak)\varphi\Big(\mathop{\ast}\limits_{k=1}^{n}a_{k}\Big)=\mathop{\diamond}\limits_{k=1}^{n}\varphi(a_{k}).

If ∗\ast is associative, then for a:[n+m]→Xa:[n+m]\to X,

∗k=1n+mak=(∗k=1nak)∗(∗j=1man+j).\mathop{\ast}\limits_{k=1}^{n+m}a_{k}=\Big(\mathop{\ast}\limits_{k=1}^{n}a_{k}\Big)\ast\Big(\mathop{\ast}\limits_{j=1}^{m}a_{n+j}\Big).

If ∗\ast is associative and commutative, then for a:[n]→Xa:[n]\to X and every bijection σ:[n]→[n]\sigma:[n]\to[n], ∗k=1naσ(k)=∗k=1nak\mathop{\ast}\limits_{k=1}^{n}a_{\sigma(k)}=\mathop{\ast}\limits_{k=1}^{n}a_{k}.

If ∗\ast is associative and commutative, then for a,b:[n]→Xa,b:[n]\to X, ∗k=1n(ak∗bk)=(∗k=1nak)∗(∗k=1nbk)\mathop{\ast}\limits_{k=1}^{n}(a_{k}\ast b_{k})=\Big(\mathop{\ast}\limits_{k=1}^{n}a_{k}\Big)\ast\Big(\mathop{\ast}\limits_{k=1}^{n}b_{k}\Big).

Proofs

Log in to submit a proof.

Loading...

Citations

Loading…

Dependencies

Loading…

Related

0 relations

Curated associations between results. These are editable and subjective — they do not replace the dependency graph, which is derived from the references in the text.

No relations recorded yet.

Comments

Log in to comment.

Loading…