TheoremBase

The number of elements is nonzero because the empty interval only enumerates the empty set. Two enumerations differ by a permutation of [n], so the reordering rule for iterated operations shows they give the same value.

Proof

Each result cited below is universally quantified over the data in its own statement, and is applied to the data named where it is cited.

Nonempty. By The Number of Elements of a Finite Set §cardinality, n∈N0n\in\mathbb{N}_{0} and there is a bijection φ\varphi from [n][n] onto AA. If n=0n=0, then [n]=∅[n]=\emptyset by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §segment, so A=φ([n])=∅A=\varphi([n])=\emptyset, contrary to the assumption. Hence n≠0n\neq0, and n∈Nn\in\mathbb{N} because N=N0∖{0}\mathbb{N}=\mathbb{N}_{0}\setminus\{0\} by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §sets.

Independent. Let φ\varphi and ψ\psi be bijections from [n][n] onto AA; here n∈Nn\in\mathbb{N} by the first part. By Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §inverse, Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §composition and Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §preservation, σ=φ−1∘ψ\sigma=\varphi^{-1}\circ\psi is a bijection from [n][n] onto [n][n] with φ(σ(k))=ψ(k)\varphi(\sigma(k))=\psi(k) for all k∈[n]k\in[n]. Put ak=f(φ(k))a_{k}=f(\varphi(k)); then aσ(k)=f(ψ(k))a_{\sigma(k)}=f(\psi(k)), and since ∗\ast is associative and commutative, Iterated Operations: Recursion, Splitting, Reordering, Termwise Combination and Homomorphisms §reordering gives

∗k=1nf(ψ(k))=∗k=1naσ(k)=∗k=1nak=∗k=1nf(φ(k)).\mathop{\ast}\limits_{k=1}^{n}f(\psi(k))=\mathop{\ast}\limits_{k=1}^{n}a_{\sigma(k)}=\mathop{\ast}\limits_{k=1}^{n}a_{k}=\mathop{\ast}\limits_{k=1}^{n}f(\varphi(k)).

Citations

Loading…

Dependencies

Uses0

Loading…

Comments

Log in to comment.

Loading…