# Structures

Definition 1.  A structure is a set $X$ together with an $n$-ary operation $O:X^n\to X.$

We can characterize an operation on a structure: let $O$ be an $n$-ary operation on $X.$  $O$ is associative if

$\begin{array}{lcl}O(O(x_1,...,x_n),x_{n+1},...,x_{2n-1})&=&O(x_1,O(x_2,...,x_{n+1}),...,x_{2n-1})\\&\vdots&\\&=& O(x_1,...,x_{n-1},O(x_n,...,x_{2n-1}))\end{array}$

where $x_i\in X$ for $1\leq i\leq 2n-1.$  The statement is trivial in the nullary and unary case.  In the binary case we have

$(x_1x_2)x_3=x_1(x_2x_3)$

or in the ternary case

$[[x_1,x_2,x_3],x_4,x_5]=[x_1,[x_2,x_3,x_4],x_5]=[x_1,x_2,[x_3,x_4,x_5]].$

More generally if $m\leq n,$ $P$ is an $m$-ary operation, and $O$ is an $n$-ary operation, we say $P$ associates with $O$ if

$\begin{array}{lcl}O(P(x_1,...,x_m),x_{m+1},...,x_{n+m-1})&=&O(x_1,P(x_2,...,x_{m+1}),...,x_{m+n-1})\\&\vdots&\\&=&O(x_1,...,x_{n-1},P(x_n,...,x_{n+m-1}))\end{array}.$

Thus an associative operation is one that associates with itself.

Definition 2.  A nullary operation $N(\,)=1\in X$ that associates with an $n$-ary operation $O$ is called an identity with respect to $O.$

Definition 3.  Let $X$ have an identity $1$ with respect to an $n$-ary operation $O.$  We say an $(n-1)$-ary operation $U$ is unital with respect to $O$ if:

$O(U(x_1,...,x_{n-1}),x_1,...,x_{n-1})=O(x_1,...,x_{n-1},U(x_1,...,x_{n-1}))=1.$

Example 4.  The unary inverse operation in a group is unital with respect to the binary product.

We say an $n$-ary operation $O$ is commutative if

$O(x_1,...,x_n)=O(x_{\sigma(1)},...,x_{\sigma(n)})$

where $\sigma$ is a permutation of $\{1,...,n\}.$

Now let $P$ be an $m$-ary operation.  $O$ is left-distributive with respect to $P$ if

$O(x_1,...,x_{n-1},P(y_1,...,y_m))=P(O(x_1,...,x_{n-1},y_1),...,O(x_1,...,x_{n-1},y_m))$

and right-distributive with respect to $P$ if

$O(P(y_1,...,y_m),x_1,...,x_{n-1})=P(O(y_1,x_1,...,x_{n-1}),...,O(y_m,x_1,...,x_{n-1})).$

$O$ is distributive with respect to $P$ if it is left and right distributive with respect to $P.$

Example 5.  In a ring, multiplication is distributive with respect to addition ($(a+b)c=ac+bc$ and $c(a+b)=ca+cb$).  Addition does not distribute with respect to multiplication though, since that would mean $a+bc=(a+b)(a+c)$ and $ab+c=(a+c)(b+c).$ (Note it does hold in quotient rings: $(a+I)(b+I)=ab+I$).

Definition 6.  The signature of a structure is the sequence $\sigma(X)=(n_k)_{k\geq 0}$ where $n_k$ is the number of $k$-ary operations on $X.$  Let $n_k$ be treated as an ordinal and $f:n_k\to\{O:O\mbox{~is a~}k\mbox{-ary operation}\}$ be a bijection.  We say $f(i)=O_i$ for an ordinal $i\leq n_k$ and $k$-ary operation $O_i.$  If we wish to specify what arity of operation we are discussing, we may write $O_{k_i}$ instead of $O_i$ to clarify that we mean the $i$th $k$-ary operation on $X.$  We call the map $f$ a $k$-ary operational ordering.  A sequence $\{f_k\}_{k\geq 0}$ of $k$-ary operational orderings on a structure $X$ is called an operational ordering.

If $X$ and $Y$ are structures with the same signature and each have operational orderings, then there is bijective map $\Omega$ between each sets’ operations.  It simply sends the $i$th $k$-ary operation of $X$ to the $i$th $k$-ary operation of $Y.$  To distinguish between operations in the structure and costructure, we write

$\displaystyle \Omega(O_{k_i})=O^{k_i}.$

Specifically if $\{f_k\},\{g_k\}$ are the operational orderings of $X$ and $Y$ (i.e. $f_k(i)=O_{k_i}$ and $g_k(i)=O^{k_i}$) we may write $\Omega$ as a map

$\displaystyle \Omega:\bigoplus_{k\geq 0} O_k\to\bigoplus_{k\geq 0} O^k$

where $O_k$ is the set of $k$-ary operations on $X$ and $O^k$ are those on $Y$ with the map defined by

$\displaystyle\Omega=\bigoplus_{k\geq 0}g_k\circ f_k^{-1}$

since if $O_\alpha$ is some arbitrary operation in $X,$ we have

$\displaystyle\Omega(O_\alpha)=\left(\bigoplus_{k\geq 0}g_k\circ f_k^{-1}\right)(O_\alpha)=g_k(i)=O^{k_i}$

for some $i\leq n_k.$

Definition 7.  Let $X$ and $Y$ be structures with the same signature and possess operational orderings $\{f_k\}$ and $\{g_k\}$ respectively.  A map $\varphi:X\to Y$ is an $(f_k,g_k)$homomorphism, or homomorphism for short, if

$\displaystyle \varphi(O_{k_i}(x_1,...,x_k))=O^{k_i}(\varphi(x_1),...,\varphi(x_k))$

for all $k$ and all $i\leq n_k.$  $\varphi$ is a strong homomorphism if

$\displaystyle \varphi(O_k(x_1,...,x_k))=O^k(\varphi(x_1),...,\varphi(x_k))$

where $O_k$ is any $k$-ary operation on $X$ and $O^k$ is any $k$-ary operation on $Y.$  An $(f_k,g_k)$-homomorphism (or strong) is an $(f_k,g_k)$isomorphism (or strong isomorphism) if it is bijective.

The latter type of homomorphism implies the former (for any choice of operational orderings).  Most homomorphisms studied in algebra are the former type.

Example 8.  A ring homomorphism $\varphi:R\to S$ is a homomorphism where $\Omega(+_R)=+_S,$ $\Omega(\cdot_R)=\cdot_S,$ $\Omega(-_R)=-_S,$ and $\Omega(0_R)=0_S.$  A strong homomorphism between rings would thus additionally require $\varphi(x+y)=\varphi(x)\varphi(y),$ $\varphi(xy)=\varphi(x)+\varphi(y).$  Hence

$\varphi(x)=\varphi(0+x)=\varphi(0)\varphi(x)=0\cdot\varphi(x).$

So $0$ is an identity with respect to multiplication on the range.  Note that on the range we therefore have

$x=x+x-x=0x+0x-x=(0+0)x-x=0x-x=x-x=0.$

Thus in particular a strong isomorphism of rings implies $R=S=0.$  Such a triviality does not always occur in general with strong isomorphisms since an arbitrary structure may not have any identities.  But we do have the following.

Proposition 9.  If $\varphi:X\to Y$ is a strong isomorphism between structures, then $O_{k_i}=O_{k_j}$ and $O^{k_i}=O^{k_j}$ for any $k$ and choice of $i,j\leq n_k.$

Proof.  We have

$\varphi(O_{k_i}(x_1,...,x_k))=O^{k_i}(\varphi(x_1),...,\varphi(x_k))$

as well as

$\varphi(O_{k_i}(x_1,...,x_k))=O^{k_j}(\varphi(x_1),...,\varphi(x_k)),$

which implies $O^{k_i}=O^{k_j}$ on the image of $\varphi.$  But since $\varphi$ is bijective, we have $O^{k_i}=O^{k_j}$ for all elements in $Y.$  For the first case we simply have $O_{k_i}=O^{k_i}=O_{k_j}$ on $X$ for all $i,j\leq n_k.$

Thus if $\varphi:X\to Y$ is a strong isomorphism, then $X$ and $Y$ have a reduced signature where $n_k\in\{0,1\}$ for all $k.$

Proposition 10.  Let $\varphi:X\to Y$ be an isomorphism.

1. If $O_{k_i}$ associates with $O_{m_j},$ then $O^{k_i}$ associates with $O^{m_j}.$
2. If $O_{k_i}$ is commutative, then $O^{k_i}$ is commutative.
3. If $O_{k_i}$ is left (right) distributive with respect to $O_{m_j},$ then $O^{k_i}$ is left (right) distributive with respect to $O^{m_j}.$
4. If $O_{0_i}$ is an identity with respect to $O_{m_j},$ then $O^{0_i}$ is an identity with respect to $O^{m_j}.$  In particular if $O_{(m-1)_k}$ is unital with respect to $O_{m_j},$ then $O^{(m-1)_k}$ is unital with respect to $O^{m_j}.$

These are easy to show and just require a bit of index swapping and parentheses galore, so I leave them to the reader.