Universal Algebra

Based on the Johnstone notes.

There is some good discussion on singleton sets here.

Nullary Set

We denote the nullary set as \(G^0\) as \(\left\{ \emptyset \right\}\).

Finary Operation

A finary operation is a map from a set \(G\) to any of $$ G^0, G^1=G, G^2 = G \times G, ... $$

Operational Type

An operational type is a pair \((\Omega, \alpha)\) with

• set of operation symbols \(\Omega\)
• a map \(\alpha : \Omega \mapsto \mathbb{N}\) that assigns each \(\omega \in \Omega\) it's arity \(\alpha(\omega)\).

Operational Structure

An operational structure \((\Omega, \alpha)\) is

• a set \(A\) with an operational type \((\Omega, \alpha)\)

• a function \(\omega_A : A^{\alpha(\omega)} \mapsto A\) for each \(\omega \in \Omega\)

\(\omega_A\) is the interpretation of abstract symbol \(\omega\) in the structure \(A\).

Homomorphism

A map \(f:A\mapsto B\) is a homomorphism of \(\Omega\) structures \(A\) & \(B\) if

\[ f(\omega_A (a_1,..., a_n)) = \omega_B (f(a_1),...,f(a_n)) \]

where \(\alpha(\omega)=n\) and \(\forall a_1,...,a_n \in A\)

The set of \(\Omega\)-terms in \(X\)

Let \(\Omega\) be an opertaional type and \(X\) be a set.

The set \(F_{\Omega}(X)\) of \(\Omega\) terms is defined inductively:

1. If \(x \in X\) then \(x \in F_{Ω}(X)\)
2. If \(w \in \Omega\) with \(\alpha(w)=n\) and \(t_1,...,t_n \in \Omega\) then \(wt_1...t_n \in F_{Ω}(X)\).

Note that this really the intersection of all operation structures that contain \(X\).

\(F_\Omega(X)\) is a sigma structure

1. The set of \(\Omega\)-terms in \(X\), \(F_{\Omega}(X)\) has a \(\Omega\) structure.
2. Given any \(\Omega\) structure \(F_\Omega(X)\) and any map \(f:X \mapsto A\) there exists a unique homomorphism \(\hat{f}:F_\Omega(X) \mapsto A\)

In other words \(F_\Omega(X)\) is the free structure generated by \(X\)

Proof of Theorem: \(F_\Omega(X)\) is a sigma structure

Need to define the interpretation of \(\omega\) on FX via $$ \omega_{FX}(t_1,...,t_n) = \omega t_1 ... t_n $$

X terms from finite

\(F_{\Omega}(X)=\bigcup \lbrace F_{\Omega}(X^\prime) \mid X^\prime \subset X \text{ is finite} \rbrace\)

Derived Operations

Let \(X_n= \lbrace x_1,...,x_n \rbrace\), \(t \in F_{\Omega}(X_n)\), \(A\) be a \(\Omega\) structure.

The n-ary derived operation corresponding to \(t \in F_{\Omega}(X)\), \(t_A : A^n \rightarrow A\) is defined as

\(\forall \underline{a} \in A^n\)

\[ t_A(\underline{a}) = \begin{cases} a_i &\text{if } t = x_i \in X_n \\ \omega_A \lparen t_1(\underline{a}) ,..., t_m(\underline{a}) \rparen &\text{if } t = \omega t_1 ... t_m, \text{ for } t_1,...,t_m \in F_{\Omega}(X_n), \alpha(\omega)=m \end{cases} \]

Note this really does just mean we keep applying the standard operations until we get to the X terms.

Therefore a derived operation really is just the map it represents

Derived Operations are literally themselves

If \(t=mx_1 m x_2 x_3\) then \(t_A(\underline{a})= m \left( a_1, m \left( a_2, a_3) \right) \right)\)

More generally if \(t = \dots \omega x_1 \dots x_m \dots\) then \(t_A(\underline{a}) = \left( \dots, \omega \left( a_1, \dots a_m \right), \dots \right)\)

In particular when \(t \in A = F_{\Omega}(X_n)\), \(\underline{u}=\left( u_1,\dots, u_n \right)\) $$ t_A(\underline{u}) = \dots \omega u_1 \dots u_n \dots = t[u_1/x_1, \dots, u_n/x_n] \ \forall \underline{u} \in F_{\Omega}(X_n) $$

Where \(t[u / x_i]\) denote replacing symbol \(x_i\) with \(u\) where \(x_i\) appears in \(t\).

This also means that $$ t_{F_{\Omega}(X)}(x_1,\dots, x_n) = t $$

n-ary Equation

An n-ary equation in operational type \((\Omega, \alpha)\) is an expression \((s=t)\) for \(s,t \in F_{\Omega}(X_n)\)

Satisfied

An n-ary equation is satisfied in operational structure A iff \(t_A \equiv s_A\)

Algebraic Theory

An Algebraic Theory \(T=(\Omega, E)\) is an operational type \((\Omega, \alpha)\) and set \(E\) of equations in \(\Omega\)

Model

A model for an Algebraic Theory \(T=(\Omega, E)\) or T-algebra is an Operational Structure \(\Omega\) where all equations in \(E\) are satisfied.

Group Theory Model

A group \(G\) is a \(\left( \Omega, E \right)\) model where \(\Omega = \{ m,i,e\}\) and

\[ E=\{(m x_1 m x_2 x_3 = m m x_1 x_2 x_3), (mex_1=x_1), (m i x_1 x_1 = e)\} \]

Derived Equations

Let \(E\) be a set of equations. The set \(\tilde{E}\) of derived equation satisfies:

1. \(E \subset \tilde{E}\)

2. \(\tilde{E}\) defines an equivalence relation \(s \sim_E t \iff (s=t) \in \tilde{E}\) on the set of terms \(F_{\Omega}(X)\)

   1. reflexive: \((t=t) \in \tilde{E} \ \forall t \in F_{\Omega}(X)\)
   2. symmetric: \((s=t) \implies (t=s)\)
   3. transitive: \((s=t),(t=u) \implies (s=u)\)

3. Substitution rules:

   1. \((s=t) \in \tilde{E} \implies (s[u / x_i] = t[u / x_i])\)
   2. \((s=t), u \in F_{\Omega}(X_n) \implies u[s/x_i] = u[t/x_i]\)

This is just the smallest subset of all possible equations \((s=t)\) such that it is closed under a,b,c.

Group Theory Example

1. \(t = m e x_1 = x_1 = s \in \tilde{E} \implies m e u = u \forall u \in F_{\Omega}(X)\)
2. \(u = m x_1 x_2\), \(t=s\) as before, \(\implies m x_1 \textcolor{red}{mex_1} = m x_1 \textcolor{red}{x_1}\)

Equivalence Classes of Equations on X

The equivalence classes of \(\sim_E\) on \(F_{\Omega}(X)\) is \(F_{(\Omega, E)}(X)\)

The set of equivalence classes satisfies the equations in E

1. \(F_{(\Omega, E)}(X)\) inherits \(\Omega\)-structure from \(F_{\Omega}(X)\) and satisfies the equations in \(E\).

2. \(F_{(\Omega, E)}(X)\) is the free model generated by X.

   i.e. For any homomorphism \(f: X \to (\Omega, E) \text{ model } A\) there is a unique homomorphism \(\tilde{f}: F_{(\Omega, E)}(X) \to A\)

Let \([t]\) denote the equivalence class of \(t \in F_{\Omega}(X)\)

Proof of Theorem: Equivalence classes satisfy E

Part I

We need to show that this indeed an \(\Omega\) structure. This requires showing that the interpretation of \(\Omega\) operations in \(F_{\Omega}(X)\) respects the equivalence relation.

Let \(FX=F_{\Omega}(X)\) and \(EX=F_{(\Omega, E)}(X)\).

In other words we need to show that the interpretation \(\omega_{EX}([\underline{u}])=[\omega_{FX}(\underline{u})]\) is well defined, \(\underline{u} = \left( u_1, u_2, \dots, u_n \right), u_i \in FX\).

Consider operation \(\omega \in \Omega\) with \(\alpha(\omega)=n\) and symbols \(t_1,\dots, t_n\) and \(s_1, \dots, s_n\) where \(t_i \sim_{E} s_i\).

We need to show that the operations result is the same regardless of the representative picked for each equivalence class:

\[ \begin{align*} \text{[definition] } \omega([t_1], \dots, [t_n]) &= & [\omega t_1 \dots t_n] \\ \text{[substitution rule 3b]} & = & [\omega s_1 \dots t_n] \\ &\vdots \\ \text{[substitution rule 3b]} & = & [\omega s_1 \dots s_n] \\ \text{[definition]} &= &\omega([s_1],\dots,[s_n]) \end{align*} \]

Hence we have a valid interpretation that respects the equivalence relation.

It then follows by induction that the derived operations also have a well defined interpretation.

Let \(t=\omega t_1 \dots t_m\), then for any \(\underline{u} \in FX^n\)

\[ \begin{align*} \text{[definition of derived operation] } t_{EX} \left( \underline{u} \right) &= \omega_{EX} \left( {t_1}_{EX} \left( \underline{u} \right) ,\dots, {t_m}_{EX} \left( \underline{u} \right) \right) \\ \text{[inductive hypothesis] } &= \omega_{EX} \left( [{t_1}_{FX} \left( \underline{u} \right)] ,\dots, [{t_m}_{FX} \left( \underline{u} \right)] \right) \\ \text{[definition of operations in } EX \text{] } &= \left[ \omega_{FX} \left({t_1}_{FX} \left( \underline{u} \right) ,\dots, {t_m}_{FX} \left( \underline{u} \right) \right) \right] \\ &= [t_{FX}(\underline{u})] \end{align*} \]

Hence \(t_{EX}(\underline{u}) = [t_{FX}(\underline{u})]\). \((\text{**})\)

It is kind of immediate that this follow by induction. I wanted to be really verbose.

The next part we need to show is that all equations in \(E\) are satisfied.

Consider equation \(\left( s=t \right) \in E\) where \(s,t \in F = F_{\Omega}(X_n)\).

We want to show that this equation is satisfied in \(EX=F_{(\Omega, E)}(X)\), i.e \(s_{EX}=t_{EX}\)

For any \(\underline{u} \in FX^n\)

\[ \begin{align*} \text{[by (**)] } s_{EX}(\underline{u}) &= \left[ s_{FX} (\underline{u}) \right] \\ \text{[see example]} &= \left[ s\left[ u_1/x_1, \dots u_n/x_n \right] \right] \\ \text{[substitution 3a repeated } n \text{ times]} &= \left[ t\left[ u_1/x_1,\dots,u_n/x_n \right] \right] \\ &= \left[ t_{FX} \left( \underline{u} \right) \right] \\ &= t_{EX} \left( \underline{u} \right) \end{align*} \]

Part II

Let \(\hat{E} = \left\{ \left( s=t \right) : h(s)=h(t) \text{ for any homomorphism } h: F_{\Omega}(X) → \left( \Omega, E \right) -\text{Model } A \right\}\)

Let's recall some facts:

• All homomorphisms from \(F_{\Omega}(X)\) to \(A\) just fill in the symbols \(x_1,\dots x_n\) from template \(t \in F_{\Omega}(X_n)\) with some choice of \(a_1, \dots, a_n\).

• Any homomorphism from \(F_{\Omega}(X)\) to some structure \(A\) is uniquely defined by \(h(x_i)\) for \(i=1,\dots,n\)

We shall show that the closure properties of \(\tilde{E}\) definition are satisfied.

Definition part 1.

It is kind of obvious that \(s=s_{FX} \left( x_1, \dots, x_i, \dots, x_n \right)\).

Suppose \(s=t \in \tilde{E}\) then

\[ \begin{align*} h(s) &= h(s_{FX}(x_1, \dots, x_n)) \\ &= s_A \left( h(x_1), \dots, h(x_n) \right) \\ [\text{equations in } \tilde{E} \text{ are true for model } A] &= t_A \left( h(x_1), \dots, h(x_n) \right) \\ &= h(t) \end{align*} \]

Definition part 2 RST is easy.

Definition part 3a.

Fix \(i\), let \(\left( s=t \right) \in \hat{E}\), \(h\) be some homomorphism from \(F_{\Omega}(X)\) to \(A\) and \(h'\) be the uniquely defined homomorphism that sends \(x_i\) to \(h(u)\) and \(x_j\) to \(h(x_j)\) for \(i \neq j\).

It is also kinda obvious that \(s[u/x_i]= s_{FX} \left( x_1,\dots,u,\dots x_n \right)\).

Therefore,

\[ \begin{align*} h \left( s \left[ u/x_i \right] \right) &= h \left( s_{FX} \left( x_1,\dots,u,\dots,x_n \right) \right) \\ \text{[homomorphism]} &= s_{A} \left( h(x_1), \dots, h(u), \dots, h(x_n) \right) \\ &= s_{A} \left( h'(x_1), \dots, h'(x_i), \dots h'(x_n) \right) \\ \text{[homomorphism]} &= h' \left( s_{FX} \left( x_1,\dots,x_i,\dots,x_n \right) \right) \\ &= h'(s) \\ \text{[s and t agree on any homomorphism]} &= h'(t) \\ \dots \\ &= h \left( t \left[ u/x_i \right] \right) \end{align*} \]

Definition part 3b.

Given \(s=t \in \hat{E}\) we want to show that \(h \left( u \left[ t/x_i \right] \right) = h \left( u \left[ s/x_i \right] \right)\)

\[ \begin{align*} h \left( u \left[ t/x_i \right] \right) &= h \left( u_{FX} \left( x_1, \dots, t, \dots, x_n \right) \right) \\ &= u_A \left( h(x_1), \dots, h(t), \dots, h(x_n) \right) \\ [ \text{since }h(s)=h(t)] &= u_A \left( h(x_1), \dots, h(s), \dots, h(x_n) \right) \\ &= h \left( u \left[ t/x_i \right] \right) \end{align*} \]

By satisfying the definition we have shown that \(\tilde{E} \subseteq \hat{E}\). This means that if we take elements \(s \in F_{\Omega}(X)\) and factor then through the quotient map to \([s] \in F_{(\Omega, E)}(X)\) we can define \(\tilde{f}\) as \(\hat{f}\) applied to any representative of \([s]\).

In particular let $\hat{f}: F_{\Omega}(X) → A $ be the unique homomorphism extending homomorphism \(f: X → A\), defined in previous theorem.

Define \(\tilde{f}: F_{(\Omega, E)}(X) → A\) by \(\tilde{f}([s]) = \hat{f}(s)\). This is a uniquely defined homomorphism that extends \(f\).