# Free objects in several constructs.

Let C be one of these constructs (in the sense that this is a concrete category over Set): Alg$(\Omega)$ or Set$^{op}$. Set$^{op}$ is a concrete category through a contravariant power-set functor. And I’m trying to find free objects in each of these categories.

How to use the definition of a free object to deduce them in these cases?

A free object over a set $X$ is an C-object $A$ such that there exists a universal arrow over $X$.

A universal arrow over a set $X$ is a structured arrow $X\overset{u}\longrightarrow |A|$ with domain $X$ that has the following universal property: for each structured arrow $X\overset{f}\longrightarrow |B|$ with domain $X$ there exists a unique C-morphism $f’:A\longrightarrow B$ such that $X\overset{u}\longrightarrow |A|\overset{f’}\longrightarrow |B|=X\overset{f}\longrightarrow |B|$.

• What's $\Omega$? – Clive Newstead Nov 30 '17 at 21:49
• @CliveNewstead, Alg $(\Omega)$ is a category of all $\Omega$-algebras, so $\Omega = (n_{i})_{i\in I}$ is a family of natural numbers $n_{i}$, indexed by a set $I$. And a $\Omega$-algebra is a pair $(X, (\omega_{i})_{i\in I})$ consisting of a set $X$ and a family of functions $\omega_{i}:X^{n_{i}}\rightarrow X$. – A. Gonus Nov 30 '17 at 22:09
• Gotcha. The intuition I'd suggest in that case is that the free way of turning a set $X$ into an $\Omega$-algebra is probably going to be fairly trivial since there isn't much structure to work with. I haven't checked, but my hunch is that the free $\Omega$-algebra on $X$ will be $(X, ())$, where $()$ is the empty sequence. – Clive Newstead Nov 30 '17 at 22:25
• Shouldn't the free $\Omega$-algebra on $X$ simply be... the free $\Omega$-algebra on $X$ ? That is, the set of $\Omega$-terms with evident operations ? – Max Nov 30 '17 at 23:31
• @Max, yes, you're right, but I was interested in how to get this from definition and how to show that this is exactly true. – A. Gonus Dec 8 '17 at 11:20

Using the definition you provide, a free object of $\mathbf{Set}^{\mathrm{op}}$ over a set $X$ is a set $A$ together with a function $u : X \to \mathcal{P}(A)$ such that, for all sets $B$ and functions $f : X \to \mathcal{P}(B)$, there is a unique function $f' : B \to A$ such that $$f = X \xrightarrow{u} \mathcal{P}(A) \xrightarrow{(f')^{-1}} \mathcal{P}(B)$$ where ${f'}^{-1}$ is the function sending each $U \subseteq A$ to its preimage ${f'}^{-1}[U]$ under $f'$.

This is a bit technical, so let's consider the case when $X=1=\{0\}$ is a singleton set.

In this case, specifying a free object of $\mathbf{Set}^{\mathrm{op}}$ over $X$ is then equivalent to specifying a set $A$ and a subset $U \subseteq A$ such that, for all subsets $V \subseteq B$, there is a unique function $f' : B \to A$ such that ${f'}^{-1}[U] = V$.

This looks like a characteristic function. So let's define $A=2=\{0,1\}$ and $U=\{1\}$. Given a subset $V \subseteq B$, there is indeed a unique function $f' : B \to 2$ such that ${f'}^{-1}(\{1\})=V$, namely the characteristic function $\chi_V : B \to 2$.

So when $X=1$, the free object on $X$ is $2$ equipped with the map $1 \to \mathcal{P}(2)$ which picks out the singleton subset $\{1\}$.

Since $2 \cong \mathcal{P}(1)$ suggests that, in general you should take $A=\mathcal{P}(X)$ and take $u : X \to \mathcal{P}(\mathcal{P}(X))$ to be "the only thing it can be": define $u$ by $$u(x) = \mathcal{F}_x := \{ U \subseteq X \mid x \in U \}$$ Given $f : X \to \mathcal{P}(B)$, define $f' : B \to \mathcal{P}(X)$ by $$f'(b) = f^{-1}(\{b\}) = \{ x \in X \mid b \in f(x) \}$$ Then \begin{align*} f'^{-1}[u(x)] &= {f'}^{-1}[\mathcal{F}_x] \\ &= \{ b \in B \mid f'(b) \in \mathcal{F}_x \} \\ &= \{ b \in B \mid \{ y \in X \mid b \in f(y) \} \in \{ U \subseteq X \mid x \in U \} \} \\ &= \{ b \in B \mid x \in \{ y \in X \mid b \in f(y) \} \} \\ &= \{ b \in B \mid b \in f(x) \}\\ &= f(x) \end{align*} I'll leave it up to you to check uniqueness.

I imagine the argument for $\mathbf{Alg}(\Omega)$ will take on a similar form. My general advice would be to look at a special case when $X$ is some simple, easy-to-understand set, such as the empty set or a singleton.