Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've just started reading about universal algebra, and have already hit a problem (see the two bullet points at the bottom).

My book gives the following definitions (paraphrased):


  1. An operational type is a pair $ (\Omega,\alpha) $, where $ \Omega $ is a set of operational symbols and $\alpha$ is an 'arity' function which assigns to each operational symbol a natural number (including 0).

  2. Given an operational type $ (\Omega, \alpha) $ and a set $A$, an $ \Omega$-structure on $A$ is a family of functions $ (\omega_A | \omega \in \Omega) $, where $ \omega_A : A^{\alpha(\omega)} \to A $ for each $\omega \in \Omega$ is the interpretation of the symbol $\omega$ in the structure $A$.

  3. A homomorphism $f : A \to B $ of $\Omega$-structures is a function such that $f(\omega_A(a_1,...,a_{\alpha(\omega)})) = \omega_B(f(a_1),..., f(a_{\alpha(\omega)}) $

  4. Given a set $X$ of variables and operational type $\Omega$ ($X \cap \Omega = \emptyset $), the set $ F_\Omega (X) $ of $\Omega$-terms is defined inductively:

a) If $x \in X$, then $x \in F_\Omega (X) $

b) If $\omega \in \Omega$, with $\alpha(\omega) = n$ and $t_1, t_2, ..., t_n \in F_\Omega(X) $, then $\omega t_1 t_2 ... t_n \in F_\Omega(X) $.

It then states the following theorem:

i) $F_\Omega(X) $ has an $\Omega$-structure

ii) $F_\Omega(X) $ is the free $\Omega$-structure generated by $X$


Now, my problem is with the second part of this theorem. Suppose we have a function $f: X \to A$, where $A$ is some $\Omega$-structure. I can see that we can define a homomorphism $ \bar{f} $ such that

if $ t = x \in X $, $\bar{f}(t) = f(x)$,

and if $ t = \omega t_1 t_1 ... t_n $, then $ \bar{f}(t) = \omega_A(\bar{f}(t_1), ... , \bar{f}(t_n)) $.

  • I think, but am not 100% sure, that because we've defined the set $F_\Omega(X) $ inductively, all $\Omega$-terms are either in $X$ or are in the form $ \omega t_1 ... t_n $ for some $\omega, t_i$. Is this correct?

  • I can see that this $\bar{f}$ is a homomorphism, but why is it the unique homormorphism extending $f$? I tried constructing a uniqueness argument, but it didn't really get anywhere: suppose we have some homomorphism $g : F_\Omega (X) \to A $ such that $g(x) = f(x) \ \forall x \in X $. If $ t = \omega t_1 ... t_n $ for some $ \omega \in \Omega $ and $ t_i \in F_\Omega (X) $, then $ g(t) = g(\omega t_1 ... t_n) = g( \omega_{F_\Omega(X)} (t_1, ... , t_n) ) = \omega_A ( g(t_1), ... , g(t_n)) $. Then I'm unsure how to finish the argument. I've thought about continuing this idea on $g(t_1), ... g(t_n) $ inductively until the arguments are contained in $X$, and then use the fact that $ \bar{f}(x) = g(x) \ \forall x \in X$. I feel it should be easier than this and so think I'm missing something obvious.

Thanks a lot!

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

As for your first question - the recursive definition is "shorthand" for the property you mention. The precise formal way of "making it go through" is unimportant (in my view). The idea is that each term in the free algebra as a "derivation" - a "proof" that it belongs to the free algebra. The proof starts with "axioms" - the elements of $X$ - and the derivation rules are given by $\Omega$. In particular, every term in the free algebra is either "basic" or "composite", as you indicate.

As for your second question, the axioms of homomorphism force your construction of the extension. It is always the case that $g(\omega t_1\ldots t_n) = \omega g(t_1) \ldots g(t_n)$, by definition of homomorphism. Formally, the uniqueness proof goes by structural induction, starting with the axioms - these are easy, since the values are given by the original mapping $f$ - and continuing with the derivation rules, where you use the homomorphism axioms as just outlined.

share|improve this answer
2  
So is this analogous to defining a linear map (homomorphism) uniquely by specifying it on a basis (the analogy of the basis is $X$ in this case) and extending linearly? –  TRY Aug 25 '11 at 22:35
    
Yes, that's a good analogy. –  Yuval Filmus Aug 26 '11 at 8:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.