# What is a free $\Omega$-structure generated by $X$

I am reading the book "Notes on logic and set-theory".

It gives the following definition:

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:

$F_\Omega(X)$ is the free $\Omega$-structure generated by $X$, i.e., given any $\Omega$-structure $A$ and any function $f:X \rightarrow A$, there exists a unique homomorphism $\bar{f}:F_\Omega(X) \rightarrow A$ extending $f$

About the preceding definition of "free $\Omega$-structure generated by $X$" I have the following questions:

1. What does it mean that an homomorphism extends a function?
2. What is the general meaning of that definition?
-
It's a little difficult to tell which answer would be appropriate. Did you simply encounter the term free $\Omega$-structure and you can't make sense of it, or have you already seen a description of it, and you are unsure whether you got everything right in understanding it? If the latter should be the case, could you please give us some more context about your understanding, or lack thereof (e.g. what is unclear in the definition)? –  Nils Matthes Jul 24 '13 at 8:21
@NilsMatthes: I added the book definition, I hope now it is clear –  Robbo Jul 24 '13 at 13:33

• Concerning your first question, note that by definition $F_{\Omega}(X)$ contains $X$. Hence given an $\Omega$-structure $A$ and a map $f: X \rightarrow A$, you can of course ask whether there exists a morphism \begin{split} \overline{f}: F_{\Omega}(X) \rightarrow A \end{split} of $\Omega$-structures such that $\overline{f}(x)= f(x)$ for every variable $x \in X \subset F_{\Omega}(X)$. If this is the case, we say that $\overline{f}$ extends $f$. The choice of the wording should be clear, since $\overline{f}$ is the same as $f$ on the set $X$, so that $\overline{f}$ really extends $f$ from $X$ to all of $F_{\Omega}(X)$.
• Concerning your second question, I am not quite sure what you would like to hear, but in some sense $F_{\Omega}(X)$ is the "biggest" $\Omega$-structure containing the given set of variables $X$: for every $\Omega$-structure $A$, which contains the variables $X$ you can find a morphism of $F_{\Omega}(X)$ into $A$. Also, the theorem in your question tells you that whenever you want to construct a morphism $F_{\Omega}(X) \rightarrow A$ of $\Omega$-structures, you only need to define it on $X$, for it will then extend uniquely to all of $F_{\Omega}(X)$. That is one nice thing about free $\Omega$-structures.

• In a more general vein, "free" objects appear in many different contexts in mathematics (free groups, free vector spaces, free monoids etc.), and they can be defined in category-theoretic terms as certain functors, which are (typically left-) adjoint to so-called forgetful functors (you may ignore this last sentence on a first reading, if it confuses you). You maybe want to check out the wikipedia entry to learn more about it.

By the way, just in order to test your understanding of $F_{\Omega}(X)$, here is a little question.

Given a map $f: X \rightarrow A$, where $X$ is a set of variables, and $A$ is an $\Omega$-structure, can you describe the induced map \begin{split} \overline{f}: F_{\Omega}(X) \rightarrow A \end{split} explicitly? That is given some element $w \in F_{\Omega}(X)$, can you tell me what $\overline{f}(w)$ is? If for example $\omega \in \Omega$ with $\alpha(\omega)=n$, $x_1,...,x_n \in X$ are variables, and $w=\omega x_1x_2...x_n$, can you tell me what $\overline{f}(w)$ looks like?

-
Is it possible to explain in more simpler language the meaning of word "free" ? –  Robbo Jul 25 '13 at 3:02
@Robbo mistakenly edited your answer to add in his own comments. I have removed them from your answer and am placing them below. The material below is from Robbo: –  mixedmath Jul 25 '13 at 4:03
1. Describing the induced map is trivial because it is written in the book 2. $\bar f(w)$ is, informally, the evaluation of the expression $w$, replacing each variable $x \in X$ with $f(x)$ 3. $\bar f(w) = \omega_A(f(x_1),f(x_2),\dots, f(x_n))$ –  mixedmath Jul 25 '13 at 4:03
Thank you, @mixedmath. –  Nils Matthes Jul 25 '13 at 6:08
@Robbo: I am afraid I can't explain to you in much simpler language what "free" means, but I have inserted the link to the wikipedia entry on free objects, which might be helpful. Also, I corrected the explanation in the second point: the free $\Omega$-structure $F_{\Omega}(X)$ is not the "smallest", but rather the "biggest" $\Omega$-structure containing the variables $X$. I hope this helps. –  Nils Matthes Jul 25 '13 at 8:19

I believe that Nils Matthes' answer above address completely the first question, I'm not so sure that it also address the second one, so here something more.

I suppose that the best way to understand the inductive definition is to write it down explicitly.

So basically given the operational type $\Omega$ and the set of variables $X$ we can build the following sequence of sets:

• $F_\Omega(X)_0 = X$;

• for every $n \in \mathbb N$ then $$F_\Omega(X)_{n+1} = F_\Omega(X)_n \cup \left\{(\omega t_1 \dots t_k) \mid \omega \in \Omega, \alpha(\omega)=k,t_1,\dots,t_k \in F_\Omega(X)_n\right\}$$

then the set of $\Omega$-terms over the set $X$ is the set $F_\Omega(X) = \bigcup_{n \in \mathbb N} F_\Omega(X)_n$.

Clearly this structure have a $\Omega$-structure where for every $\omega \in \Omega$, with $\alpha(\omega)=k$, we have that for every $t_1,\dots,t_k \in F_\Omega(X)$ then $\omega(t_1,\dots,t_k)=(\omega t_1 \dots t_k)$ (where the expression on the left is the application of the operation $\omega$ to the terms $t_i$ while the expression on the right is just a string which belong to $F_\Omega(X)$).

Basically the set $F_\Omega(X)$ is the set of expressions generated by the (algebraic) grammar over family of symbols given by the elements of $X$ (the variables) and the operation symbols in $\Omega$.

The importance of these structures between the $\Omega$-structures is that there is no relation between the operation of these structures: meaning that any equation of the form $$\omega_1(t_1,\dots,t_k) = \omega_2(t'_1,\dots,t'_m)$$ holds if and only if $m=k$, $\omega_1=\omega_2$ and $t_i=t'_i$ for all $i=1,\dots,k$. This is also the reason why these structures are said free, because they are free from any relation.

Hope this help :)

p.s. What follow is an addendum just to present free object in general:

Of course these are a very particular type of free structures, indeed there's a more general definition of free object which can be stated in the setting of category theory and subsume this definition. Shortly free objects are objects for which holds an equivalent universal property as the theorem you've quoted in the question.
If you interested you can find more about free objects in the link of Nils Matthes' answer, or also

-
Is "The importance of structures between the Ω-structures is the there is no relation between the operation of these structures: meaning that any equation of the form " right, or did you want to write "The importance of functions between the Ω-structures is that there is no relation between the operation of these structures: meaning that any equation of the form " –  Robbo Jul 25 '13 at 16:14
@Robbo neither, I've edited the question. Thanks for pointing out the typo :) –  Giorgio Mossa Jul 25 '13 at 17:13
I meant the answer instead of the question above :P –  Giorgio Mossa Jul 28 '13 at 18:02