Operations in free algebras are one to one.

Question

Does anybody know a simple proof that operations in a free algebra of a certain type $\Omega$ have necessarily to be one to one? That is, in other words, a proof that a free $\Omega$-algebra is an $\Omega$-term algebra, without knowing about an explicit construction of an $\Omega$-term algebra itself.

Edit. To be more precise, with free $\Omega$-algebra on a set $X$ I mean a free object in the category $\Omega$-Alg, as such defined by a universal factorization property, whereas an $\Omega$-term algebra $T$ on $X$ is defined by the properties that the inclusion of $X$ in the underlying set of $T$ and all the operations in $T$ are one to one and have disjoint images, and the image of $X$ in the underlying set of $T$ generates $T$. It's easy to prove that the inclusion map $u: X \rightarrow |T|$ must be one to one, but I can't find a way to prove the same for any operation $s_T$ where $s\in\Omega$.

Answer 1

Suppose that $f$ is a $n$-ary operation of the relevant type. If $$f(x_1, \ldots, x_{i-1}, x_i, x_{i+1}, \ldots, x_n) = f(x_1, \ldots, x_{i-1}, y, x_{i+1}, \ldots, x_n),$$ where $y$ is something other than $x_i$, then the above equality is a non-trivial identity of the algebra, which is then not free.

(I am supposing that by a free algebra of a certain type you mean the term algebra without any identities, aka, the completely free algebra. If you mean the free algebra on any variety, then that is just not true.)

Answer 2

I take $\Omega$ to be the set of operation symbols in the language, each symbol recognizing its own arity.

The set of $\Omega$-terms over $X$ is the smallest set $T_X$ of strings in the alphabet $X\cup \Omega$ satisfying the conditions that (i) $X\subseteq T_X$ and (ii) $$ t_1,\ldots,t_m\in T_X\Rightarrow f t_1\ldots t_m\in T_X $$ for every $m$-ary operation symbol $f$ in $\Omega$, for every $m$.

The $\Omega$-term algebra $\mathbb T_X$ over $X$ is the algebra with universe $T_X$ where, for each $m$, and each $m$-ary operation symbol $f$, $f^{\mathbb T_X}$ is the operation $f^{\mathbb T_X}(t_1,\ldots,t_m) = f t_1\ldots t_m$.

The algebra $\mathbb T_X$ satisfies
(i) the universal mapping property over $X$ with respect to the class of $\Omega$-algebras, and
(ii) the operations of $\mathbb T_X$ are 1-1.
These items are proved using induction and the unique readability of terms. (That is, $f t_1,\ldots,t_m = g u_1, \ldots, u_n$ implies these strings are identical: $m=n, f=g, t_i=u_i$ for all $i$.) Since the free $\Omega$-algebra over $X$ is unique up to isomorphism, and $\mathbb T_X$ is free over $X$ and has injective operations, any free $\Omega$-algebra over $X$ must have injective operations.

Answer 3

Suppose $F$ is a free $\Omega$-algebra on $X$ with $i:X\to F$ the inclusion. Let $F_n$ denote the subset of elements of $F$ that can be obtained by starting with the image of $i$ and then applying operations of $\Omega$ at most $n$ times. I claim first that $F=\bigcup_n F_n$. Indeed, note that $\bigcup F_n$ is a subalgebra of $F$ which contains the image of $i$, and thus also has the universal property of a free algebra on $X$ (the uniqueness being satisfied since the image of $i$ generates $\bigcup F_n$). By Yoneda, it follows that the inclusion map $\bigcup F_n\to F$ must be an isomorphism.

Now let us prove every operation of $\Omega$ is injective on $F$. Let $s$ be an $m$-ary operation of $\Omega$ and $x,y\in F^m$ be distinct tuples; we wish to show $s(x)\neq s(y)$. Let $n$ be minimal such that $x,y\in F_n^m$; we may assume without loss of generality that some entry of $x$ is in $F_n\setminus F_{n-1}$. Note also that since we assume $x\neq y$, $F$ must have at least two elements. Now let $F'$ be the algebra with the same underlying set as $F$ and the same algebra structure except that we redefine the value of $s(x)$ in $F'$ to be some element different from $s(y)$ (such an element exists since $F$ has at least two elements). By the universal property of $F$, there is a homomorphism $\varphi:F\to F'$ that is the identity on the image of $i$. Note also that all the operations of $F$ and $F'$ are the same when restricted to $F_{n-1}$, since $x$ has an entry in $F_n\setminus F_{n-1}$. It follows that $\varphi$ is the identity when restricted to $F_n$ (since every element of $F_n$ is obtained by starting with the image of $i$ and repeatedly applying operations, where in each step the inputs to the operations are all in $F_{n-1}$). In particular, $\varphi(x)=x$ and $\varphi(y)=y$, so since $s(x)$ and $s(y)$ are different in $F'$ they must be different in $F$ as well.