Algebraic operations on sets

Most ordered algebraic structures arise from the generalisation of algebra from operations on elements to operations on sets, but this is by no means exclusive. There are of course ordered rings and semirings like $\mathbb{N}$ and $\mathbb{Z}$ that emerge from basic arithmetic. In the former case, the algebra on sets will be constructed from the ground up from simple foundations.

The covariant power set functor
Let $f : A \to B$ be a function of sets. Then the power set functor converts $f$ into a function which takes the image of $f$ with respect to a set. Although this is a simple construction, it is the fundamental building block of all operations on sets: \[ \wp(f) : \wp(A) \to \wp(B) \] An important property is that $\wp$ is a union homomorphism. Therefore, $wp(f)(A \cup B) = \wp(f)(A) \cup \wp(f)(B)$. It also preserves identities $\wp(f)(\emptyset) = \emptyset$.

A property of cartesian products:
The cartesian product of sets distributes over unions and it preserves emptyness. This exactly matches the case of the power set functor, which also preserves unions and the empty set. \[ A \times \emptyset = \emptyset \times A = \emptyset \] \[ A \times (B \cup C) = A \times B \cup A \times C \] \[ (A \cup B) \times C = A \times C \cup B \times C \] This can be generalized to any number of variables, so that the cartesian product of sets always distributes over unions. An immediate consequence of this and the same property over images means that the algebraic operations on sets distribute over unions.

Algebraic operations on subsets:
Let $\circ : A^2 \to A$ be a semigroup. Let $S,T \subseteq A$ then the product is typically defined as $AB = \{ab : a \in A, b \in B\}$, but it is much more conventient to define it by using the image functor and the cartesian product: \[ AB = \wp_\circ(A \times B) \] It is now very easy to see that the product of subsets of a semigroup distributes over unions, and hence it forms an idempotent semiring. All we need to do is combine the fact that the image preserves unions and the product distributes over them.

Theorem. let $\circ : A^2 \to A$ be a semigroup then the product of sets $\wp(A)^2 \to \wp(A)$ distributes over unions.

Proof. let $S,T,U \subseteq A$ then we have the following sequence of equalities: \[ S(T \cup U) \] \[= \wp_{\circ}(S \times T \cup U) \] \[ = \wp_{\circ}(S \times T \cup S \times U) \] \[ = \wp_{\circ}(S \times T) \cup \wp_{\circ}(S \times U) \] \[ = ST \cup SU \] This can easily be dualized to the other order $(S \cup T)U$. Additionally, the product of sets preserves emptyness: $A\emptyset = \emptyset A = \emptyset$. $\square$

An important consequence of this formulation using the image functor and the distributivity of products over unions is that it can be generalized to any n-ary operation.

Theorem. let $f: A^n \to A$ be an n-ary operation. Then the power algebra $f' : \wp(A)^n \to \wp(A)$ distributes over unions and preserves emptyness.

A ternary operation on subsets produces a different kind of algebraic structures then the familiar idempotent semirings of structure like semigroups. In the case that we have a partial operation, then operations on subsets can be defined by intersection with the domain. For example, consider the partial semigroup composition function $\circ$ of a category: \[ \circ : Arrows(C)^2_* \to Arrows(C) \] In order to define the composition of morphism systems of a category, we simply get the image of morphism compsoition of $S \times T \cap Arrows(C)^2_*$. The intersection simply means that we don't want to return a value when a composition doesn't exist. This of course means that the idempotent semiring of a category can have non-trivial zero divisors.

Hyperoperations:
To make things a little bit interesting, I will cover hyperoperations here using the same idea of dealing with images over products. Let $f : A^2 \to \wp(A)$ be a hypermagma. Then we can define the the product of sets $S$ and $T$ in the hypermagma by the union of the image: \[ \bigcup \wp_f(S \times T) \] This produces a magma $f' : \wp(A)^2 \to \wp(A)$. It is often more convenient to work with hyperoperations by algebraic operations on sets then on elements, which creates a uniform process. Then $f'$ is simply a hypersemigroup provided that it is associative. This clearly has the same properties of preserving unions and emptyness.