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|$.

  • $\begingroup$ What's $\Omega$? $\endgroup$ – Clive Newstead Nov 30 '17 at 21:49
  • $\begingroup$ @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$. $\endgroup$ – A. Gonus Nov 30 '17 at 22:09
  • $\begingroup$ 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. $\endgroup$ – Clive Newstead Nov 30 '17 at 22:25
  • 1
    $\begingroup$ 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 ? $\endgroup$ – Maxime Ramzi Nov 30 '17 at 23:31
  • $\begingroup$ @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. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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