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

Question

I am reading the book "Notes on logic and set-theory" from P.T Johnstone.

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?

Answer 1

• 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?

Answer 2

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