The Zappa-Szép product, strict factorization systems and distributive laws

$\newcommand{\con}{\mathbf{Set}} \newcommand{\uno}{\mathbf{1}} \newcommand{\Cat}{\mathbf{Cat}}\newcommand{\mon}{\mathbf{Mon}} \newcommand{\ab}{\mathbf{Ab}} \newcommand{\an}{\mathbf{An}}\newcommand {\matcon}{\mathbf{Set\text{-}Mat}} \newcommand{\grp}{\mathbf{Grp}} \newcommand{\ob}{\mathrm{Ob}}$

The Zappa-Szép product and distributive laws

The Zappa-Szép product, strict factorization systems and distributive laws are related in a certain way. Let us talk first about the Zappa-Szép product (also known as knit product or matched pair of groups).
     The Zappa-Szép product is a generalization of the semidirect product for groups in the same way as this product is a generalization of the direct product for groups, and the zappa-szép product is the most general way in which a group is presented as a product of two groups.
     The internal Zappa-Szép product is defined as follows. Given a group $G$ and two subgroups $H$ and $K$ of $G$, the following statements are equivalent:

• $G=KH$ y $K\cap H=\{e\}$,
• for every $g\in G$ there is a unique $k\in K$ and a unique $h\in H$ such that $g=kh$.

If either of these statements is satisfied, then $G$ is said to be an internal Zappa-Szép product of $K$ and $H$.
     There is an external version of the Zappa-Szép product, which is the one we are interested in, because it's by means of this product that a link between distributive laws and strict factorization systems is established.
     Given two groups $K$ and $H$, suppose there are funtions $\alpha:H\times K\rightarrow K$ and $\beta:H\times K\rightarrow H$ such that

1. $\alpha(h_1h_2,k)=\alpha(h_1,\alpha(h_2,k))$,
2. $\beta(h_1h_2,k)=\beta(h_1,\alpha(h_2,k))\beta(h_2,k)$,
3. $\beta(h,k_1k_2)=\beta(\beta(h,k_1),k_2)$,
4. $\alpha(h,k_1k_2)=\alpha(h,k_1)\alpha(\beta(h,k_1),k_2)$,
5. $\alpha(e,k)=k$,
6. $\beta(h,e)=h$

for every $h,h_1,h_2\in H$ y $k,k_1,k_2\in K$ (cf. [4]). Note that from (ii) and (v) and from (iv) and (vi) follows respectively:

7. $\beta(e,k)=e$ and
8. $\alpha(h,e)=e$.

We can define from (i)-(vi) a multiplication and an inverse on $K\times H$ as $$(k_1,h_1)\gamma(k_2,h_2):=(k_1\alpha(h_1,k_2),\beta(h_1,k_2)h_2))$$ and $$(k,h)^{-1}:=(\alpha(h^{-1},k^{-1}),\beta(h^{-1},k^{-1})).$$ $(\gamma,K\times H)$ is called an external Zappa-Szép product of $K$ and $H$.
     Note that if $G$ is an internal Zappa-Szép product of its subgroups $K$ y $H$, then there are funtions $\alpha:H\times K\rightarrow K$ and $\beta:H\times K\rightarrow H$ such that (i), (ii), (iii), (iv), (v) and (vi) in the previous definition are satisfied: their existence follows from the fact that every element $g\in G$ can be written uniquely as a product $kh$, and the fact that if $G$ is an external Zappa-Szép product of the groups $K$ and $H$, then $G$ is an internal Zappa-Szép product of its subgroups $K\times e_H$ and $e_K\times H$.
     Let $H,K\in\grp$. Let $S$ and $T$ be the endofunctors $H\times(-)$ and $K\times(-)$ on $\con$, respectively. Then we have the monads $$H\times X,\quad\xymatrix{X\ar[r]^(.4){e_H\times 1_X} & H\times X},\quad\xymatrix{H\times H\times X\ar[r]^(.6){m_H\times 1_X} & H\times X}$$ and $$K\times X,\quad\xymatrix{X\ar[r]^(.4){e_K\times 1_X} & K\times X},\quad\xymatrix{K\times K\times X\ar[r]^(.6){m_K\times 1_X} & K\times X}.$$ Denote their units and multiplicationss as $\eta',\mu'$ y $\eta,\mu$, resp. Let $\gamma$ be a group structure on $K\times H$ such that $K\times e_H,e_K\times H$ are subgroups of $(\gamma,K\times H)$ and $(K\times e_H)\gamma(e_K\times H)=(\gamma,K\times H)$. In other words, such that $(\gamma,K\times H)$ is an internal Zappa-Szép product of $K\times e_H$ and $e_k\times H$, or that $(\gamma, K\times H)$ is an external Zappa-Szép product of $K$ and $H$.
     Without loss of generality, we can assume $(k,h)=(k,e_H)\gamma(e_K,h)$ for any $k\in K$ and $h\in H$ (consider the definition of external Zappa-Szép product and the properties of $\alpha$ and $\beta$). Then we have the monad $$(K\times H\times(-),(e_K,e_H)\times 1_{(-)}, \gamma\times 1_{(-)})$$ on $\con$. Since $K\times e_H$ and $e_K\times H$ are subgroups of $(\gamma,K\times H)$, then $\eta S$ and $T\eta'$ are morphisms of monads, and since $(k,h)=(k,e_H)\gamma(e_K,h)$, the previous monad satisfies the middle unitary law, so the monad above induces a distributive law $ST\Rightarrow TS$; namely, $$(\gamma\times 1_{(-)})\cdot\eta ST\eta':H\times K\times(-)\Rightarrow K\times H\times(-);$$ explicitly, $$\xymatrix{(h,k,-)\ar@{|->}[r] & (e_K,h,k,e_H,-)\ar@{|->}[r] & ((e_K,h)\gamma(k,e_H),-)}.$$
     Conversely, let $\lambda:ST\Rightarrow TS$ be a distributive law of $S$ over $T$, and consider $\lambda 1:H\times K\times 1\rightarrow K\times H\times 1$. Neglect the singleton, and put $$\lambda 1=(\alpha,\beta),$$ where $\alpha$ and $\beta$ are determined by the following commutative diagram: $$\xymatrix{ & H\times K\ar[d]^{\lambda 1}\ar[dr]^\alpha\ar[dl]_\beta &\\ K & K\times H\ar[l]^{p_K}\ar[r]_{p_H} & H. }$$ Then, by the compatibility of $\lambda$ with the unit of $S$, $$\xymatrix{ & H\times K\times 1\ar[dd]^{\lambda 1}\\ K\times 1\ar[ur]^{e_H\times K\times 1}\ar[dr]_{K\times e_H\times 1} &\\ & K\times H\times 1 }$$ commutes; hence, $\alpha(e_H,k)=k$ y $\beta(e_H,k)=e_H$.
     Now, by the compatibility of $\lambda$ with the multiplication of $S$, $$\xymatrix{ H\times H\times K\times 1\ar[rr]^{H\times\lambda 1}\ar[d]_{m_H\times K\times 1} & & H\times K\times H\times 1\ar[rr]^{\lambda_{H\times 1}} & & K\times H\times H\times 1\ar[d]^{K\times m_H\times 1}\\ H\times K\times 1\ar[rrrr]_{\lambda 1} & & & & K\times H\times 1 }$$ commutes; whence, $$\alpha(h_1h_2,k)=\alpha(h_1,\alpha(h_2,k))\quad\text{y}\quad \beta(h_1h_2,k)=\beta(h_1,\alpha(h_2,k))\beta(h_2,k).$$ Similarly, by the compatibility of $\lambda$ with the unit and the multiplication of $T$, $\alpha(h,e_K)=e_K$, $\beta(h,e_K)=h$ and $$\alpha(h,k_1k_2)=\alpha(h,k_1)\alpha(\beta(h,k_1),k_2)\quad\text{y}\quad\beta(h,k_1k_2)=\beta(\beta(h,k_1),k_2).$$
     Therefore, we have a Zappa-Szép product of $K$ and $H$.
     Thus we have a correspondence between the Zappa-Szép products of $K$ and $H$, and the distributive laws of $H\times(-)$ over $K\times(-)$. Indeed, define $L:\mathbf{Zappa\text{-}Sz\acute{e}p}(K,H)\rightarrow\mathbf{DistLaw}(H,K)$, a function which goes from the Zappa-Szép products of $K$ and $H$ to the distributive laws of $H\times(-)$ ovoer $K\times(-)$ (let $\alpha:H\times K\rightarrow K$ and $\beta:H\times K\rightarrow H$ be the functions which define a Zappa-Szép product of $K$ and $H$): $$\xymatrix{ \mathbf{Zappa\text{-}Sz\acute{e}p}(K,H)\ar[r]^(.55)L & \mathbf{DistLaw}(H,K) }\qquad\qquad\quad$$ $$\xymatrix{ (\alpha,\beta)\ar@{|->}[r] & (\alpha,\beta)\times 1_{(-)}. }$$ Define $N:\mathbf{DistLaw}(H,K)\rightarrow\mathbf{Zappa\text{-}Sz\acute{e}p}(K,H)$ as $$\xymatrix{ \mathbf{DistLaw}(H,K)\ar[r]^(.45)N & \mathbf{Zappa\text{-}Sz\acute{e}p}(K,H) }\qquad\qquad\quad$$ $$\xymatrix{ \lambda\ar@{|->}[r] & (p_K\circ\lambda 1,p_H\circ\lambda 1). }$$ Obviously $NL=1$. Less obvious is that $LN=1$. Since $\con$ is a distributive category, \begin{equation}\label{D:distcatset} Z\times X=\sum\nolimits_{x\in X}Z\times H\times\{x\}. \end{equation}
     Consider now the injection $i_x:\{x\}\rightarrow X$; then by naturality of $\lambda$, the following diagram commutes: $$\xymatrix{ H\times K\times\{x\}\ar[rr]^{H\times K\times i_x}\ar[d]_{\lambda_{\{x\}}} & & H\times K\times X\ar[d]^{\lambda_X}\\ K\times H\times\{x\}\ar[rr]_{K\times H\times i_x} & & K\times H\times X. }$$ On the other hand, since $H\times K\times i_x$ is the injection $$\xymatrix{H\times K\times\{x\}\ar[r] & \sum_{x\in X}H\times K\times\{x\}},$$ $K\times H\times i_x$ is the injection $$\xymatrix{K\times H\times\{x\}\ar[r] & \sum_{x\in X}K\times H\times\{x\}}$$ and the equality \eqref{D:distcatset} holds, $\lambda_X=\sum_{x\in X}\lambda_{\{x\}}$. However $\lambda_{\{x\}}=\lambda 1\times 1_{\{x\}}$ for every $x\in X$, so $\lambda_X=\lambda 1\times 1_X$. Hence, $\lambda_X=(p_K\circ\lambda 1,p_H\circ\lambda 1)\times 1_X$.

The bicategory of set-valued matrices

The Zappa-Szép product is generalized in [3] by showing the equivalence of the concept of distributive law in the bicategory of set-valued matrices and the concept of strict factorization system. Let's see how that is done. First describe the bicategory of set-valued matrices $\matcon$ as follows: the objects (the 0-cells) of $\matcon$ are sets, a 1-cell $M:A\rightarrow B$ is a set-valued matrix, i. e., $M(b,a)\in\con$ for every $a\in A$ and $b\in B$, a 2-cell $\tau:M\Rightarrow N:A\rightarrow B$ is a matrix of functions $\tau(b,a):M(b,a)\rightarrow N(b,a)$. The composite of 1-cells $$\xymatrix{ A\ar[r]^M & B\ar[r]^E & C\ar@{}|{=}[r] & A\ar[r]^{EM} & C }$$ is defined as $$EM(c,a):=\sum_{a\in A}E(c,b)\times M(b,a).$$ Given $A\in\matcon$, we define $$1_A(b,a):= \begin{cases} 1,\text{ the singleton, if $b=a$};\\ \emptyset,\text{ if $b\neq a$}. \end{cases}$$ It is clear that $M 1_A\overset{r}{\cong} M$ and $1_B M\overset{l}{\cong} M$.
     A monad $T$ on an object $A$ in this bicategory is precisely a category with set of objects $A$. Let's shed some light on what is happening. Diagrammatically $T$ is determined by the following commutative diagrams: $$\xymatrix{ (TT)T\ar@{}|{\cong}[r]\ar[d]_{\mu T} & T(TT)\ar[r]^(.55){T\mu} & TT\ar[d]^\mu\\ TT\ar[rr]_\mu & & T }$$ and $$\xymatrix{ 1_AT\ar[r]^{\eta T}\ar[dr]_l & TT\ar[d]^\mu & T1_A\ar[l]_{T\eta}\ar[ld]^r\\ & T &, }$$ where $l$ and $r$ are the isomorphisms above induced by the product and the terminal object of $\con$. Now, what $T$ does is to assign to each pair of elements $b,a\in A$ a set $T(b,a)$ of arrows, to give a composite to each composable pair by means of $\mu$, to choose an identity for each element $a\in A$ via $\eta$ and finally, with the previous diagrams, to make composition associative and make composition with an identity a unit law for the arrows of the small category $A$ with objects its elements and its arrows in $T(b,a)$; put differently, a monad in $\matcon$ is a category.
     Now let $M$ and $E$ be two categories with set of objects $A$ and let $\lambda:ME\Rightarrow EM$ be a distributive law of $M$ over $E$; $\lambda$ yields a function $$\xymatrix{ ME(a,c)\ar[r]^{\lambda(a,c)} & EM(a,c) }$$ for every pair $(a,c)\in A\times A$. Thus we have a family of functions $$(\xymatrix{ M(a,b)\times E(b,c)\ar[r] & \sum_{i\in A}E(a,i)\times M(i,c) })_{b\in A}.$$ If we write $m:\xymatrix{a\ \ar@{>->}[r] & b}$ for an arrow in $M$ and $e:\xymatrix{b\ar@{->>}[r] & c}$ for an arrow in $E$, then $\lambda$ yields an object $e_\lambda m$ and a composable pair $(e_\alpha m,e_\beta m)$ as shown by: $$\xymatrix{ a\; \ar@{>->}[r]^m\ar@{->>}[d]_{e_\alpha m}\ar@{}|{\triangleleft\scriptscriptstyle{\dashv}}[dr] & b\ar@{->>}[d]^e\\ e_\lambda m\;\ar@{>->}[r]_{e_\beta m} & c. }$$ We call a diagram such as this a $\lambda$-square. Consider the compatibility diagrams for the distributive law $\lambda:ME\Rightarrow EM$: \begin{equation} \vcenter{\xymatrix{ & ME\ar[dd]^\lambda\\ E\ar[ru]^{1E}\ar[dr]_{E1} & \\ & EM, }}\quad\text{compatibility of $\lambda$ with $1$ (CuM)}\notag \end{equation} \begin{equation} \vcenter{\xymatrix{ & ME\ar[dd]^\lambda\\ M\ar[ur]^{M1}\ar[dr]_{1 M} &\\ & EM, }}\quad\text{compatibility of $\lambda$ with $1$ (CuE)}\notag \end{equation} \begin{equation} \vcenter{\xymatrix{ MME\ar[r]^{M\lambda}\ar[d]_{\bullet E} & MEM\ar[r]^{\lambda M} & EMM\ar[d]^{E\bullet}\\ ME\ar[rr]_\lambda & & EM, }}\quad\text{compatibility of $\lambda$ with $\bullet$ (CmM)}\notag \end{equation} \begin{equation} \vcenter{\xymatrix{ MEE\ar[r]^{\lambda E}\ar[d]_{M\bullet} & EME\ar[r]^{E\lambda} & EEM\ar[d]^{\bullet M}\\ ME\ar[rr]_\lambda & & EM, }}\quad\text{compatibility of $\lambda$ with $\bullet$ (CmE)}\notag \end{equation} where we denote by 1 the transformations that provide identities and by $\bullet$ the transformations that provide the composites (the units and the multiplications of the monads $M$ and $E$). Now, in terms of $\lambda$-squares, the compatibility of $\lambda$ with the units is expressed by $$\xymatrix{ b\;\ar@{>->}[r]^{1_b}\ar@{->>}[d]_e\ar@{}|{\triangleleft\scriptscriptstyle{\dashv}}[dr] & b\ar@{->>}[d]^e & & a\;\ar@{>->}[r]^m\ar@{->>}[d]_{1_a}\ar@{}|{\triangleleft\scriptscriptstyle{\dashv}}[dr] & b\ar@{->>}[d]^{1_b}\\ c\;\ar@{>->}[r]_{1_c} & c & & a\;\ar@{>->}[r]_m & b; }$$ i. e., CuM and CuE state that ${1_b}_\lambda e=c,m_\lambda 1_b=a$ and that

1. ${1_b}_\alpha e=e$,
2. ${1_b}_\beta e=1_c$,
3. $m_\alpha 1_b=1_a$,
4. $m_\beta 1_b=m$.

Chasing the upper right path of the diagram of CmM yields $$\xymatrix{ a\;\ar@{>->}[rr]^m\ar@{->>}[d]_{m_\alpha(n_\alpha e)}\ar@{}|{\triangleleft\scriptscriptstyle{\dashv}}[drrrr] & & b\;\ar@{>->}[rr]^n & & b''\ar@{->>}[d]^e\\ m_\lambda(n_\alpha e)\;\ar@{>->}[rr]_{m_\beta(n_\alpha e)} & & n_\lambda e\;\ar@{>->}[rr]_{n_\beta e} & & c; }$$ chasing the left lower path, $(mn)_\lambda e=m_\lambda(n_\alpha e)$ and

5. $(mn)_\alpha e=m_\alpha(n_\alpha e)$,
6. $(mn)_\beta e=m_\beta(n_\alpha e)\bullet n_\beta e$.

Similarly, for CmE, if we chase the upper right paht of the diagram, then $$\xymatrix{ a\;\ar@{>->}[rr]^m\ar@{->>}[d]_{m_\alpha e}\ar@{}|{\triangleleft\scriptscriptstyle{\dashv}}[ddrr] & & b\;\ar@{->>}[d]^e\\ m_\lambda e\ar@{->>}[d]_{(m_\beta e)_\alpha f} & & b'\ar@{->>}[d]^f\\ (m_\beta e)_\lambda f\;\ar@{>->}[rr]_(.55){(m_\beta e)_\beta f} & & c; }$$ chasing the left lower path, $m_\lambda(ef)=(m_\beta e)_\lambda f$ and

7. $m_\alpha(ef)=m_\alpha e\bullet(m_\beta e)_\alpha f$,
8. $m_\beta(ef)=(m_\beta e)_\beta f$.

If $A$ has a single element, then $M$ and $E$ are monoids, the equations (I)-(VIII) are the equations (i)-(viii) and the equalities for objects are trivial.
     From the general theory of distsributive law [1], $\lambda$ induces a composite monad $E_\lambda M$, a category with set of objects $A$ in which an arrow from $a$ to $c$ is given by specifying a third object $b$ and a pair $$\xymatrix{ a\ar@{->>}[r]^e & b\;\ar@{>->}[r]^m & c }$$ with $e$ in $E$ and $m$ in $M$; i. e., the arrows in $E_\lambda M$ are described as a formal composition $e\circ m$. The composition in $E_\lambda M$ is given by the multiplication for the monad $E_\lambda M$; namely, by $$\xymatrix{ & & EEM\ar[dr]^{\bullet M} & \\ EMEM \ar[r]^{E\lambda M} & EEMM\ar[ur]^{EE\bullet}\ar[dr]_{\bullet MM}\ar[rr]^(.55){\bullet\;\bullet} & & EM\\ & & EMM\ar[ur]_{E\bullet} &, }$$ thus the composite of $a\overset{e}{\twoheadrightarrow} b\overset{m}{\rightarrowtail} c$ and $c\overset{f}{\twoheadrightarrow} d\overset{n}{\rightarrowtail} x$ is given by $$\xymatrix{ a\ar@{->>}[r]^e\ar@{->>}[dr]_{e\bullet m_\alpha f} & b\;\ar@{>->}[r]^m\ar@{->>}[d]_(.35){m_\alpha f}\ar@{}|{\triangleleft\scriptscriptstyle{\dashv}}[dr] & c\ar@{->>}[d]^f\\ & m_\lambda f\;\ar@{>->}[r]_(.6){m_\beta f}\ar@{>->}[dr]_{m_\beta f\bullet n} & d\ar@{>->}[d]^n\\ & & x; }$$ i. e., $(e\circ m)\bullet(f\circ n)=(e\bullet m_\alpha f)\circ(m_\beta f\bullet n)$.
     It is easy to check that the unit of the composite monad $E_\lambda M$ characterizes the identities in $E_\lambda M$ by $$a\overset{1_a}{\twoheadrightarrow}a\overset{1_a}{\rightarrowtail}a.$$
     The morphisms of monads $1M:M\rightarrow E_\lambda M$ and $E1:E\rightarrow E_\lambda M$ are given by $m\mapsto 1\circ m$ and $e\mapsto e\circ 1$, resp. The middle unitary law yields that for every $e\circ m$ in $E_\lambda M$, $$(e\circ 1)\bullet(1\circ m)=e\circ m$$ holds.
     Note that if $M$ and $E$ are monoids, the composition in $E_\lambda M$ is the multiplication defined in the case of the Zappa-Szép product for groups.
     There is a greater generalization of the Zappa-Szép product in [2]; however, things there are done more à la Ehresmann.

Strict factorization systems

Given a category $C$ with $\ob(C)=:A$, a strict factorization system on $C$ is a pair of subcategories $S:=(E,M)$ of $C$ such that $\ob(M)=\ob(E)=\ob(C)$ and such that for every $f$ in $C$, there is a unique factorization $f=e_fm_f$ with $e_f$ in $E$ and $m_f$ in $M$. Consider $M$ and $E$ as monads on $A$ in $\matcon$. The pair $(E,M)$ induces a distributive law $\lambda_S:ME\Rightarrow EM$; indeed, define $\lambda_S$ by $$\xymatrix{ ME\ar[r]^{\lambda_S} & EM }$$ $$\xymatrix{ a\ar[r]^n & b\ar[r]^f & c\ar@{|->}[r] & a\ar[r]^{e_{n\cdot f}} & i\ar[r]^{m_{n\cdot f}} & c. }\ $$ Its compatibility with the unit of $M$ is obvious, for $m\cdot 1_b=m$. Now, the upper right path of the compatibility diagram of $\lambda_S$ with respect to the multiplication of $M$ (check the diagram above) produces the following diagram: $$\xymatrix{ a\ar[rr]^f\ar[dr]_{e_{f\cdot e_{g\cdot h}}} & & b\ar[r]^g\ar[dr]_(.45){e_{g\cdot h}} & c\ar[r]^h & d\\ & k\ar[rr]_{m_{f\cdot e_{g\cdot h}}} & & j\ar[ur]_{m_{g\cdot h}} &\ ; }$$ so $f\cdot g\cdot h$ has as factorization $e_{f\cdot e_{g\cdot h}}\cdot m_{f\cdot e_{g\cdot h}}\cdot m_{g\cdot h}$, which is unique; whence, the left lower path in the compatibility diagram of $\lambda_S$ with respect to the multiplication of $M$ produces the same result, and in consequence the compatibility of $\lambda_S$ with $M$ is satisfied. Similarly, the compatibility of $\lambda_S$ with $E$ is satisfied.
     Conversely, let $\lambda:ME\Rightarrow EM$ be a distributive law in $\matcon$, and consider the subcategories of $E_\lambda M$ defined by $$\lambda E:=\{e\circ 1\mid e\in E\}\quad\text{y}\quad M\lambda:=\{1\circ m\mid m\in M\}.$$ Each of these subcategories contains all the identities of $E_\lambda M$ and thus each contains all the objects of $E_\lambda M$. By the middle unitary law, $e\circ m$ is factorized as $(e\circ 1)\bullet(1\circ m)$. It is clear that this factorization is unique, and therefore $(\lambda E, M\lambda)$ is a strict factorization system $S_\lambda$ for $E_\lambda M$.
     We leave this correspondence just right there; i. e., we won't show that $S_{(-)}$ and $\lambda_{(-)}$ are biequivalences inverse of each other, because this is not our objetive right now.
     The way a distributive law is induced by the Zappa-Szép product in the group case makes us wonder whether a distributive law in $\matcon$ participates in a correspondence of that kind...

References

[1] Beck, J. [1969]: Distributive laws, Seminar on Triples and Categorical Homological Theory, ETH 1966/67, 80, 119-140 (1969). ↩
[2] Brin, M. G. [2005]: On the Zappa-Szép Product, Communications in Algebra, 33, 393-424 (2005). ↩
[3] Rosebrugh, R., Wood, R. J. [2002]: Distributive laws and factorization, Journal of Pure and Applied Algebra, 175(1-3), 327-353 (2002). ↩
[4] Takeuchi, M. [1981]: Matched pairs of groups and bismash products of Hopf algebras, Communications in Algebra, 9(8), 841-882 (1981). ↩

Coálgebras, coinducción y computación, una brevísima introducción

Ya hace varias décadas que las estructuras de datos trataron de describirse de manera algebraica, y con éxito varias de ellas. Sin embargo, hay otras estructuras de datos que no pueden describirse algebraicamente de manera apropiada. Con el tiempo, comenzó a entenderse que tales estructuras quedaban mejor modeladas coalgebraicamente, como las estructuras que implican una noción de estado que puede cambiar; por ejemplo, los sistemas de transición, los autómatas, la semántica de programación orientada a objetos, los automorfismos parciales, los números reales, las listas infinitas, las series de potencias formales, etc.
     Volviendo a las álgebras, desde el punto de vista del álgebra universal, se tiene que las signaturas de operaciones inducen ciertos funtores polinomiales y que las álgebras de estos funtores corresponden a las álgebras o modelos de las signaturas. Si generalizamos, dado un funtor $F:\mathbf{Con}\rightarrow\mathbf{Con}$, un álgebra de $F:\mathbf{Con}\rightarrow\mathbf{Con}$ (o una $F$-álgebra) es un par $(B,\beta:FB\rightarrow B)$, donde $B\in\mathbf{Con}$ y $\beta$ es una función. Dualmente, una coálgebra de $F$ (o una $F$-coálgebra) es un par $(A,\alpha:A\rightarrow FA)$, con $A\in\mathbf{Con}$ y $\alpha$ una función.
     Ahora, la inducción, como principio para definir o demostrar, se utiliza para las estructuras algebraicas que son generadas por una colección de constructores (u operaciones constructoras) —como los números naturales, que son generados por $0:1\rightarrow\mathbb{N}$ y $s:\mathbb{N}\rightarrow\mathbb{N}$, o como las listas y los árboles finitos—. Estas estructuras algebraicas son las álgebras iniciales en la categoría de álgebras de algún funtor pertinente; más precisamente, el principio de inducción en una estructura, como en el conjunto de los números naturales $\mathbb{N}$ o en el conjunto de las listas finitas $A^\ast$ sobre $A$, puede reformularse como la inicialidad de esa estructura en la categoría de álgebras de algún funtor. Dualmente, la terminalidad en la categoría de coálgebras de un funtor nos da un principio de coinducción para la cóalgebra terminal (o final) de esa categoría. La coálgebra terminal viene equipada con destructores u operaciones destructoras (también llamadas observadores, accesores, mapeos de transición o mutadores), las cuales la cogeneran. Volviendo a la inducción y siguiendo con la correspondencia entre inducción y la inicialidad, esta implica existencia única: la existencia corresponde a definir por inducción y la unicidad a demostrar por inducción. Tal correspondencia también se tiene para la coinducción.
     La coinducción puede formularse de manera alternativa mediante el concepto de bisimulación, que es una relación sobre una coálgebra que es cerrada de manera apropiada bajo las operaciones coalgebraicas de la coálgebra; tales relaciones se pueden entender como el concepto dual de congruencia, que es una relación cerrada bajo operaciones algebraicas.
     Volviendo a las álgebras, expliquemos de manera más precisa la correspondencia entre álgebras de una signatura y las álgebras de funtores polinomiales. Sea $\Sigma$ una signatura (monoespécica), así que, dada una $\Sigma$-álgebra $X$ y $\sigma\in\Sigma$, se tiene una operación $$\sigma_X:\underbrace{X\times\cdots\times X}_{\mathrm{ar}(\sigma)\text{ veces}}\rightarrow X,$$ donde $\mathrm{ar}(\sigma)$ es la aridad de $\sigma$. Así que si $\Sigma=\{\sigma_1,\ldots,\sigma_n\}$, podemos asociarle a $\Sigma$ el funtor $T_\Sigma:\mathbf{Con}\rightarrow\mathbf{Con}$ dado como $$T_\Sigma X:=X^{\mathrm{ar}(\sigma_1)}+\cdots +X^{\mathrm{ar}(\sigma_n)}.$$ Ahora, la estructura algebraica $\beta:T_\Sigma X\rightarrow X$ de un álgebra $X$ del funtor $T_\Sigma$ puede identificarse con una $n$-cotupla $$\beta=[\beta_1,\ldots,\beta_n]:X^{\mathrm{ar}(\sigma_1)}+\cdots +X^{\mathrm{ar}(\sigma_n)}\rightarrow X$$ de funciones $\beta_i:X^{\mathrm{ar}(\sigma_i)}\rightarrow X$. De aquí, las álgebras de $T_\Sigma$ corresponden a los modelos de $\Sigma$, las $\Sigma$-álgebras. Es decir, los funtores polinomiales construidos a partir del funtor identidad, productos y coproductos tienen como álgebras las álgebras que son modelos de signaturas. Un ejemplo sencillo de tales funtores es el funtor $1+(-):\mathbf{Con}\rightarrow\mathbf{Con}$, una de cuyas álgebras es $(\mathbb{N},[0,s]:1+\mathbb{N}\rightarrow\mathbb{N})$, donde $0:1\rightarrow\mathbb{N}$ es el cero y $s:\mathbb{N}\rightarrow\mathbb{N}$ la función sucesor.
     Otros funtores polinomiales importantes son aquellos en los que aparecen conjuntos constantes, como el funtor $1+A\times (-):\mathbf{Con}\rightarrow\mathbf{Con}$, una de cuyas álgebras es el álgebra de listas finitas sobre el conjunto $A$; o sea, $(A^\ast,[\mathrm{\textbf{nil}},\mathrm{\textbf{cons}}]:1+A\times A^\ast\rightarrow A^\ast)$, con $\mathrm{\textbf{nil}}:1\rightarrow A^\ast$ la lista vacía y $\mathrm{\textbf{cons}}:A\times A^\ast\rightarrow A$ la prefijación de un elemento de tipo $A$ a una lista; o como el funtor $1+X\times A\times X$, una de cuyas álgebras es el álgebra de árboles finitos binarios enraizados con nodos en $A$; o sea, $(\mathrm{\textbf{Árbol}}(A),[\mathrm{\textbf{nil}},\mathrm{\textbf{nodo}}]:1+\mathrm{\textbf{Árbol}}(A)\times A\times\mathrm{\textbf{Árbol}}(A)\rightarrow\mathrm{\textbf{Árbol}}(A))$, con $\mathrm{\textbf{nil}}:1\rightarrow\mathrm{\textbf{Árbol}}(A)$ el árbol binario enraizado vacío y $\mathrm{\textbf{nodo}}:\mathrm{\textbf{Árbol}}(A)\times A\times\mathrm{\textbf{Árbol}}(A)\rightarrow\mathrm{\textbf{Árbol}}(A)$ la construcción de un árbol binario enraizado a partir de dos (sub)árboles y una raíz en $A$.
     Pasemos a las coálgebras y veamos algunos ejemplos. Consideremos una máquina que es una caja negra y que tiene dos botones, $\mathrm{\textbf{val}}$ y $\mathrm{\textbf{sig}}$. Presionar el botón $\mathrm{\textbf{val}}$ resulta en alguna indicación visible del estado interno de la máquina, indicación cuyos valores están en el conjunto de datos $A$; tal operación no afecta el estado interno de la máquina, así que presionar dos veces $\mathrm{\textbf{val}}$ da el mismo resultado. Si uno presiona el botón $\mathrm{\textbf{sig}}$, la máquina cambia de estado, cuyo valor puede inspeccionarse al presionar nuevamente $\mathrm{\textbf{val}}$. Esta máquina puede describirse de manera abstracta como una coálgebra con mapeo de estructura $$(\mathrm{\textbf{val}},\mathrm{\textbf{sig}}):X\rightarrow A\times X,$$ donde $X$ es el espacio de estados (internos) de la máquina. Un coálgebra del funtor $A\times(-)$ es la coálgebra de listas infinitas sobre $A$; a saber, $(A^\mathbb{N},(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}}):A^\mathbb{N}\rightarrow A\times A^\mathbb{N})$, donde $\mathrm{\textbf{cab}}:A^\mathbb{N}\rightarrow A$ nos da el primer elemento de una lista infinita y $\mathrm{\textbf{cola}}:A^\mathbb{N}\rightarrow A^\mathbb{N}$ nos da la lista que resulta de quitar el primer elemento de la lista. Otra máquina caja negra podría ser una con un botón y una luz. La máquina realiza una acción sólo si el botón es presionado y la luz se enciende sólo si la máquina se detiene por completo; así que lo único que podríamos observar es su comportamiento tras presionar el botón y si se enciende la luz. Esta máquina puede describirse como una coálgebra con mapeo de estructura $$\mathrm{\textbf{botón}}:X\rightarrow 1+X,$$ donde $\mathrm{\textbf{botón}}\, s=\ast$ si la máquina deja de operar tras presionar el botón y se enciende la luz, y $\mathrm{\textbf{botón}}\,s\in X$ si la máquina no deja de operar y ha cambiado de estado. Una coálgebra del funtor $1+(-):\mathbf{Con}\rightarrow\mathbf{Con}$ es $(\overline{\mathbb{N}},\mathrm{\textbf{pred}}:\overline{\mathbb{N}}\rightarrow 1+\overline{\mathbb{N}})$, donde $\overline{\mathbb{N}}:=\mathbb{N}+\{\infty\}$ y $\mathrm{\textbf{pred}}(0):=\ast$, $\mathrm{\textbf{pred}}(n+1):=n$ y $\mathrm{\textbf{pred}}(\infty):=\infty$.
     Volvamos a las álgebras y expliquemos mediante el ejemplo de los números naturales la correspondencia entre inducción e inicialidad. La $1+(-)$-álgebra $(\mathbb{N},[0,s])$ es álgebra inicial en la categoría de álgebras del funtor $1+(-):\mathbf{Con}\rightarrow\mathbf{Con}$. En efecto, sean $A\in \mathbf{Con}$, $\varphi : \mathbb{N} \rightarrow A$ una función y $[d,r] : 1+A \rightarrow A$ una $1+(-)$-álgebra. Entonces, considérense los siguientes diagramas: $$\begin{xy} \xymatrix{ 1 \ar[d]_1 \ar[r] & 1+\mathbb{N} \ar[d]^{1+\varphi} & \mathbb{N} \ar[l] \ar[d]^{\varphi} & 1 \ar[r] \ar[rd]_0 & 1+\mathbb{N} \ar[d]^{[0,s]} & \mathbb{N} \ar[l] \ar[ld]^s \\ 1 \ar[r] \ar[rd]_d & 1+A \ar[d]^{[d,r]} & A \ar[l] \ar[ld]^r & & \mathbb{N} \ar[d]^{\varphi} & \\ & A & & & A & . }\end{xy}$$ De aquí, $$\begin{xy} \xymatrix{ 1+\mathbb{N} \ar[r]^{1+\varphi} \ar[d]_{[0,s]} \ar@{}[rd]|{=} & 1+A \ar[d]^{[d,r]} \ar@{}[rd]^(.6){\Leftrightarrow} & 1 \ar[r]^0 \ar@<-.5ex>[rd]_d \ar@<.5ex>@{}[rd]^{=} & \mathbb{N} \ar[r]^s \ar[d]^{\varphi} \ar@{}[rd]|{=} & \mathbb{N} \ar[d]^{\varphi} \\ \mathbb{N} \ar[r]_{\varphi} & A & & A \ar[r]_r & A; }\end{xy}$$ entonces, si $\varphi$ es un homomorfismo de álgebras, $\varphi$ tiene que cumplir que para todo $n\in \mathbb{N}$ $$\begin{xy} \xymatrix{ & 1 \ar[d]^0 \ar[ld]_d \\ A \ar[d]_{r^n} & \mathbb{N} \ar[l]_{\varphi} \ar[d]^{s^n} \\ A & \mathbb{N} \ar[l]^{\varphi} }\end{xy}$$ conmuta; por lo tanto, $\varphi n = r^n d$ para todo $n\in \mathbb{N}$.
     Luego, $(\mathbb{N},[0,s] : 1+\mathbb{N} \rightarrow \mathbb{N})$ es inicial.
     Observemos que pudimos haber obtenido el conjunto portador del álgebra inicial del funtor $1+(-)$ como el conjunto de los términos cerrados (los términos básicos —ground terms en inglés—, los que no tienen variables), es decir, de aquellos términos que son generados al aplicar iteradamente los constructores $\mathbf{0}:1\rightarrow X$ y $\mathbf{S}:X\rightarrow X$ de un álgebra cualquiera $(X,[\mathbf{0},\mathbf{S}]:1+X\rightarrow X)$ de $1+(-)$: $$\{\mathbf{0},\mathbf{S}\mathbf{0},\mathbf{S}\mathbf{S}\mathbf{0},\mathbf{S}\mathbf{S}\mathbf{S}\mathbf{0},\ldots\}.$$ En general, el conjunto portador del álgebra inicial de un funtor $T$ se puede obtener a partir de los términos cerrados, es decir, a partir de aquellos que son generados al aplicar iteradamente los constructores de un álgebra de $T$.
     Ahora el principio de inducción en los naturales usado como principio de demostración normalmente se formula de la siguiente manera: un subcojunto $P$ de $\mathbb{N}$ es igual a $\mathbb{N}$ si $0\in P$ y $n\in P\Rightarrow n+1\in P$. Reformulándolo, las suposiciones inductivas sobre $P$ esencialmente dicen que $P$ tiene una estructura de álgebra $0' : 1 \rightarrow P$, $s' : P \rightarrow P$ tal que la función inclusión $i : P \rightarrow \mathbb{N}$ es un homomorfismo de álgebras: $$\begin{xy} \xymatrix{ 1+P \ar[r]^{1+i} \ar[d]_{[0',s']} & 1+\mathbb{N} \ar[d]^{[0,s]} \\ P \ar[r]_i & \mathbb{N}. }\end{xy}$$ Es decir, $P$ es una subálgebra de $\mathbb{N}$. Ahora, de la inicialidad de $(\mathbb{N},[0,s])$, existe un homomorfismo $j : \mathbb{N} \rightarrow P$; nuevamente, por la inicialidad de $(\mathbb{N},[0,s])$, $i\circ j = 1_{\mathbb{N}}$: $$\begin{xy} \xymatrix{ 1+\mathbb{N} \ar[r]^{1+j} \ar[d]_{[0,s]} \ar@/^2pc/[rr]^{1+1_{\mathbb{N}}} & 1+P \ar[r]^{1+i} \ar[d]^{[0',s']} & 1+\mathbb{N} \ar[d]^{[0,s]} \\ \mathbb{N} \ar[r]_j \ar@/_2pc/[rr]_{1_{\mathbb{N}}} & P \ar[r]_i & \mathbb{N}; }\end{xy}$$ de aquí, $P = \mathbb{N}$.
     Veamos un ejemplo de cómo usar la inicialidad para las definiciones por inducción. Supongamos que queremos definir por inicialidad la función $fn=2^{-n}$ de los números naturales $\mathbb{N}$ a los racionales $\mathbb{Q}$. Las ecuaciones inductivas que la definen son $$f0:=1\qquad\text{y}\qquad f(n+1):=\frac{1}{2}fn.$$ Para definir esta función $f:\mathbb{N}\rightarrow\mathbb{Q}$ por inicialidad, hay que dotar a $\mathbb{Q}$ de una estructura de álgebra $1+\mathbb{Q}\rightarrow\mathbb{Q}$. Esta álgebra sobre $\mathbb{Q}$ corresponde al lado derecho de las dos ecuaciones inductivas que definen a $f$: $$\begin{xy} \xymatrix{ 1\ar[r]^1 & \mathbb{Q} & & \mathbb{Q}\ar[r]^{\frac{1}{2}(-)} & \mathbb{Q} }\end{xy}$$ $$\begin{xy} \xymatrix{ \ast\ar@{|->}[r] & 1 & & \ x\ar@{|->}[r] & \frac{1}{2}x. }\end{xy}$$ Entonces, $fn=2^{-n}$ está determinada por inicialidad como la única función que hace conmutar el siguiente diagrama: $$\begin{xy} \xymatrix{ 1+\mathbb{N}\ar[rr]^{1+f}\ar[d]_{[0,s]} & & 1+\mathbb{Q}\ar[d]^{[1,\frac{1}{2}(-)]}\\ \mathbb{N}\ar[rr]_f & & \mathbb{Q} }\end{xy}$$ La conmutatividad del diagrama nos da de vuelta las ecuaciones inductivas que definen a $f$. Notemos que los constructores $0$ y $s$ aparecen “dentro” de la función $f$, que estamos definiendo: $f0=1$ y $fsn=fn$.
     Esto muestra cómo se puede usar la inicialidad para definir funciones por inducción: hay que dotar al codominio de la función en cuestión de un estructura algebraica apropiada que corresponda a las cláusulas inductivas que determinan a dicha función. Además, en las definiciones inductivas, los constructores aparecen “dentro” de la función que se desea definir. Resumiendo: definir por inicialidad a una función es dotar a su codominio de una estructura algebraica apropiada que nos da la existencia de la función a definir, el diagrama conmutativo nos da las ecuaciones inductivas que determinan a la función; recíprocamente, las ecuaciones inductivas que definen a una función nos dan la estructura algebraica apropiada del codominio de la función para obtener su existencia mediante la inicialidad.
     Volvamos a las coálgebras y veamos la correspondencia entre terminalidad y coinducción. La coálgebra terminal (o final) del funtor $A\times(-):\mathbf{Con}\rightarrow\mathbf{Con}$ es $(A^\mathbb{N},(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}}))$, donde $\mathrm{\textbf{cab}}\,\sigma=\sigma\,0$ y $\mathrm{\textbf{cola}}\,\sigma=\lambda x.\sigma(x+1)$. En efecto, considérense los siguientes diagramas: $$\begin{xy} \xymatrix{ & X\ar[d]^{(\mathrm{\textbf{val}},\mathrm{\textbf{sig}})}\ar[dl]_{\mathrm{\textbf{val}}}\ar@/^0.9pc/[dr]^{\mathrm{\textbf{sig}}} & & & X\ar[d]^\varphi &\\ A\ar[d]_1 & A\times X\ar[r]\ar[l]\ar[d]^{A\times\varphi} & X\ar[d]^\varphi & & A^\mathbb{N}\ar[d]^{(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}})}\ar@/^1.3pc/[dr]^{\mathrm{\textbf{cola}}}\ar[dl]_{\mathrm{\textbf{cab}}} &\\ A & A\times A^\mathbb{N}\ar[r]\ar[l] & A^\mathbb{N} & A & A\times A^\mathbb{N}\ar[r]\ar[l] & A^\mathbb{N}. }\end{xy}$$ De aquí, $$\begin{xy} \xymatrix{ X \ar[r]^\varphi \ar[d]_{(\mathrm{\textbf{val}},\mathrm{\textbf{sig}})} \ar@{}[rd]|{=} & A^\mathbb{N} \ar[d]^{(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}})} \ar@{}[drr]^(.65){\Leftrightarrow} & & & X\ar@<-.5ex>[dl]_{\mathrm{\textbf{val}}}\ar@<.5ex>@{}[dl]^{=} \ar[d]^\varphi \ar@{}[rd]|{=} & X \ar[l]_{\mathrm{\textbf{sig}}}\ar[d]^\varphi \\ A\times X \ar[r]_{A\times\varphi} & A\times A^\mathbb{N} & & A & A^\mathbb{N}\ar[l]^{\mathrm{\textbf{cab}}} & A^\mathbb{N}\ar[l]^{\mathrm{\textbf{cola}}} }\end{xy}$$ entonces, si $\varphi$ es un homomorfismo de coálgebras, $\varphi$ tiene que cumplir que para todo $n\in \mathbb{N}$ $$\begin{xy} \xymatrix{ X \ar[r]^\varphi \ar[d]_{\mathrm{\textbf{sig}}^n} & A^\mathbb{N} \ar[d]^{\mathrm{\textbf{cola}}^n} \\ X \ar[r]_\varphi \ar[rd]_{\mathrm{\textbf{val}}} & A^\mathbb{N} \ar[d]^{\mathrm{\textbf{cab}}} \\ & A }\end{xy}$$ conmuta; por lo tanto, $\varphi(x)(n)=\mathrm{\textbf{val}}(\mathrm{\textbf{sig}}^nx)$ para todo $n\in\mathbb{N}$, ya que $\varphi(x)(n)=\mathrm{\textbf{cab}}(\mathrm{\textbf{cola}}^n\varphi x)$ para todo $n\in\mathbb{N}$.
     Luego, $(A^\mathbb{N},(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}}):A^\mathbb{N}\rightarrow A\times A^\mathbb{N})$ es terminal.
     Observemos que pudimos haber obtenido el conjunto portador de la coálgebra terminal del funtor $A\times(-)$ como el conjunto de todos los posibles comportamientos de un elemento $x\in X$, el conjunto de los comportamientos que se podría observar de $x$; es decir, podemos obtener el portador de la coálgebra del funtor $A\times(-)$ al aplicar iteradamente los observadores $\mathrm{\textbf{cab}}:X\rightarrow A$ y $\mathrm{\textbf{sig}}:X\rightarrow X$ a cualquier elemento $x$ de una coálgebra cualquiera $(X,(\mathrm{\textbf{val}},\mathrm{\textbf{sig}}):X\rightarrow A\times X)$ de $A\times(-)$: todas las posibles listas infinitas $$(\mathrm{\textbf{val}}\,x,\mathrm{\textbf{val}}(\mathrm{\textbf{sig}}\,x),\mathrm{\textbf{val}}(\mathrm{\textbf{sig}}^2\,x),\ldots).$$ En general, el conjunto portador de la coálgebra terminal de un funtor $T$ se puede obtener a partir de los comportamientos observables.
     La técnica para definir una función $f:X\rightarrow A$ por terminalidad es la siguiente: se describen las observaciones directas junto con las pasos siguientes solos de $f$ como una estructura coalgebraica sobre $X$. La función $f$ entonces surge por repetición. De aquí, una definición coinductiva de $f$ no determina a $f$ en una sola vez, sino pasa a paso. Veamos esto con unos ejemplos.
     Para nuestro funtor $A\times(-)$ sea $A=\mathbb{N}$. Definamos por coinducción la función $\mathrm{\textbf{desde}}:\mathbb{N}\rightarrow\mathbb{N}^\mathbb{N}$, la cual manda un número natural $n\in\mathbb{N}$ a la sucesión $(n,n+1,n+2,n+3,\ldots)\in\mathbb{N}^\mathbb{N}$. Esto implica definir una estructura coalgebraica $\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$ sobre $\mathbb{N}$. La observación directa que podemos hacer acerca del “estado” $n\in\mathbb{N}$ es $n$ mismo y el estado siguiente es $n+1$ (acerca del cual podemos observar directamente $n+1$). La repetición entonces nos lleva a $\mathrm{\textbf{desde}}\, n$. Definimos entonces por terminalidad a $\mathrm{\textbf{desde}}$ en el siguiente diagrama: $$\begin{xy} \xymatrix{ \mathbb{N}\ar[rr]^{\mathrm{\textbf{desde}}}\ar[d]_{\lambda n.(n,n+1)} & & \mathbb{N}^\mathbb{N}\ar[d]^{(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}})}\\ \mathbb{N}\times\mathbb{N}\ar[rr]_{1\times\mathrm{\textbf{desde}}} & & \mathbb{N}\times\mathbb{N}^\mathbb{N}. }\end{xy}$$ Así que $\mathrm{\textbf{desde}}$ queda determinada por las ecuaciones coinductivas $$\mathrm{\textbf{cab}}(\mathrm{\textbf{desde}}\, n)=n\quad\text{y}\quad\mathrm{\textbf{cola}}(\mathrm{\textbf{desde}}\, n)=\mathrm{\textbf{desde}}(n+1).$$      Definamos otras tres funciones, dos por coinducción. Nuevamente, consideremos el funtor $A\times(-)$. Definamos por terminalidad y, en consecuencia, por coinducción la función $\mathrm{\textbf{non}}:A^\mathbb{N}\rightarrow A^\mathbb{N}$ que, dada una lista infinita, devuelve la lista que resulta de tomar sólo los elementos en las entradas impares de la lista original; dotemos entonces a $A^\mathbb{N}$ de una estructura coalgebraica que nos dé las observaciones que queremos: $$\begin{xy} \xymatrix{ A^\mathbb{N}\ar[rr]^{\mathrm{\textbf{non}}}\ar[d]_{\lambda\sigma.(\mathrm{\textbf{cab}}\,\sigma,\mathrm{\textbf{cola}}(\mathrm{\textbf{cola}}\,\sigma))} & & A^\mathbb{N}\ar[d]^{(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}})}\\ A\times A^\mathbb{N}\ar[rr]_{1\times\mathrm{\textbf{non}}} & & A\times A^\mathbb{N} }\end{xy}$$ La estructura coalgebraica sobre $A^\mathbb{N}$ a la izquierda da lugar, por terminalidad, a un único homomorfismo de coálgebras. Por conmutatividad, $\mathrm{\textbf{non}}$ queda determinada por las ecuaciones coinductivas $$\mathrm{\textbf{cab}}(\mathrm{\textbf{non}}\,\sigma)=\mathrm{\textbf{cab}}\,\sigma\quad\text{y}\quad\mathrm{\textbf{cola}}(\mathrm{\textbf{non}}\,\sigma)=\mathrm{\textbf{non}}(\mathrm{\textbf{cola}}(\mathrm{\textbf{cola}}\,\sigma)).$$ Ahora, definimos $\mathrm{\textbf{par}}:=\mathrm{\textbf{non}}\circ\mathrm{\textbf{cola}}$, que es la función que, dada una lista infinita, nos devuelve una lista que resulta de tomar sólo los elementos en las entradas pares de la lista original.
     Finalmente, definamos por terminalidad y, en consecuencia, por coinducción la función $\mathrm{\textbf{fus}}:A^\mathbb{N}\times A^\mathbb{N}\rightarrow A^\mathbb{N}$ que, dada dos listas infinitas $\sigma$ y $\tau$, nos devuelve una lista que resulta de tomar elementos de $\sigma$ y $\tau$ alternadamente, empezando por $\sigma$; dotemos entonces a $A^\mathbb{N}\times A^\mathbb{N}$ de una estructura coalgebraica que nos dé las observaciones que queremos: $$\begin{xy} \xymatrix{ A^\mathbb{N}\times A^\mathbb{N}\ar[rr]^{\mathrm{\textbf{fus}}}\ar[d]_{\lambda(\sigma,\tau).(\mathrm{\textbf{cab}}\,\sigma,(\tau,\mathrm{\textbf{cola}}\,\sigma))} & & A^\mathbb{N}\ar[d]^{(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}})}\\ A\times(A^\mathbb{N}\times A^\mathbb{N})\ar[rr]_{1\times\mathrm{\textbf{fus}}} & & A\times A^\mathbb{N}. }\end{xy}$$ El homomorfismo $\mathrm{\textbf{fus}}:A^\mathbb{N}\times A^\mathbb{N}\rightarrow A^\mathbb{N}$ queda entonces determinado por las ecuaciones coinductivas $$\mathrm{\textbf{cab}}(\mathrm{\textbf{fus}}(\sigma,\tau))=\mathrm{\textbf{cab}}\,\sigma\quad\text{y}\quad\mathrm{\textbf{cola}}(\mathrm{\textbf{fus}}(\sigma,\tau))=\mathrm{\textbf{fus}}(\tau,\mathrm{\textbf{cola}}\,\sigma).$$      Lo que podemos ver de nuestras tres definiciones por coinducción es (1) que definir por terminalidad a una función es dotar a su dominio de una estructura coalgebraica apropiada que nos da la existencia de la función a definir, el diagrama conmutativo nos da las ecuaciones coinductivas que determinan a la función; recíprocamente, las ecuaciones coninductivas que definen a una función nos dan la estructura coalgebraica apropiada del dominio de la función para obtener su existencia mediante la terminalidad, y (2) que la función que queremos definir ocurre “dentro” de los observadores (o destructores) de la coálgebra terminal.
     En resumen, en una definición inductiva de una función $f$, uno define los valores de $f$ al hacerlo en todos los constructores de un álgebra inicial y en una definición coinducitva de $f$ uno define los valores de todos los observadores en cada resultado $fx$.
     Retomando la cóalgebra final del funtor $A\times(-)$ y los homomorfismos de coálgebras $\mathrm{\textbf{fus}},\mathrm{\textbf{non}}$ y $\mathrm{\textbf{par}}$, demostremos por coinducción que $$\mathrm{\textbf{fus}}(\mathrm{\textbf{non}}\,\sigma,\mathrm{\textbf{par}}\,\sigma)=\sigma;$$ es decir, hagamos uso de la unicidad dada por la terminalidad. Basta mostrar entonces que $\mathrm{\textbf{fus}}\circ(\mathrm{\textbf{non}},\mathrm{\textbf{par}}):A^\mathbb{N}\rightarrow A^\mathbb{N}$ es un homomorfismo de coálgebras $(A^\mathbb{N},(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}}))\rightarrow(A^\mathbb{N},(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}}))$; para esto, basta mostrar que $(\mathrm{\textbf{non}},\mathrm{\textbf{par}})$ es un homomorfismo de coálgebras. Notemos que la estructura coalgebraica sobre $A^\mathbb{N}\times A^\mathbb{N}$ la podemos reescribir como $(\mathrm{\textbf{cab}}\circ p_1,\mathrm{\textbf{int}})$, donde $p_1$ es la proyección izquierda de $A^\mathbb{N}\times A^\mathbb{N}$ e $\mathrm{\textbf{int}}(\sigma,\tau):=(\tau,\mathrm{\textbf{cola}}\,\sigma)$. El siguiente diagrama conmuta: $$\begin{xy} \xymatrix{ A^\mathbb{N}\ar[rr]^{(\mathrm{\textbf{non}},\mathrm{\textbf{par}})}\ar[d]_{(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}})} & & A^\mathbb{N}\times A^\mathbb{N}\ar[d]^{(\mathrm{\textbf{cab}}\circ p_1,\mathrm{\textbf{int}})}\\ A\times A^\mathbb{N}\ar[rr]_(.42){1\times(\mathrm{\textbf{non}},\mathrm{\textbf{par}})} & & A\times(A^\mathbb{N}\times A^\mathbb{N}), }\end{xy}$$ pues $\mathrm{\textbf{non}}\circ\mathrm{\textbf{cola}}=\mathrm{\textbf{par}}$ y $\mathrm{\textbf{cola}}\circ\mathrm{\textbf{non}}=\mathrm{\textbf{non}}\circ\mathrm{\textbf{cola}}\circ\mathrm{\textbf{cola}}$.
     El principio de coinducción como principio de demostración puede formularse de otra manera, mediante el concepto de bisimulación.
     Retomemos la coálgebra final del funtor $A\times(-)$. Una bisimulación sobre $A^\mathbb{N}$ es una relación $R$ sobre $A^\mathbb{N}$ tal que $$R(\sigma,\tau)\Rightarrow \begin{cases} \mathrm{\textbf{cab}}\,\sigma=\mathrm{\textbf{cab}}\,\tau\,\text{ y}\\ R(\mathrm{\textbf{cola}}\,\sigma,\mathrm{\textbf{cola}}\,\tau). \end{cases} $$ Ahora, $A^\mathbb{N}$ cumple el principio coinductivo de demostración: para todo $\sigma,\tau\in A^\mathbb{N}$, $$\text{si }R(\sigma,\tau)\text{ para alguna bisimulación }R\text{ sobre }A^\mathbb{N},\text{ entonces }\sigma=\tau.$$ Demostremos, otra vez, que $\mathrm{\textbf{fus}}(\mathrm{\textbf{non}}\,\sigma,\mathrm{\textbf{par}}\,\sigma)=\sigma$. Definamos la relación $$R:=\{(\mathrm{\textbf{fus}}(\mathrm{\textbf{non}}(\sigma),\mathrm{\textbf{par}}(\sigma)),\sigma)\mid\sigma\in A^\mathbb{N}\}$$ sobre $A^\mathbb{N}$. Se tiene que $R$ es una bisimulación, pues $$\mathrm{\textbf{cab}}(\mathrm{\textbf{fus}}(\mathrm{\textbf{non}}\,\sigma,\mathrm{\textbf{par}}\,\sigma))=\mathrm{\textbf{cab}}\,\sigma$$ y $$\mathrm{\textbf{cola}}(\mathrm{\textbf{fus}}(\mathrm{\textbf{non}}\,\sigma,\mathrm{\textbf{par}}\,\sigma))=\mathrm{\textbf{fus}}(\mathrm{\textbf{non}}(\mathrm{\textbf{cola}}\,\sigma),\mathrm{\textbf{par}}(\mathrm{\textbf{cola}}\,\sigma)),$$ y esto último nos dice que $R(\mathrm{\textbf{cola}}(\mathrm{\textbf{fus}}(\mathrm{\textbf{non}}\,\sigma,\mathrm{\textbf{par}}\,\sigma)),\mathrm{\textbf{cola}}\,\sigma)$, así que, por el principio coinductivo de demostración basado en una bisimulación, se obtiene la igualdad.
     El principio funciona por lo siguiente. Dado un funtor $T:\mathbf{Con}\rightarrow\mathbf{Con}$, una bisimulación sobre la $T$-coálgebra $(X,\chi)$ es una relación $R$ sobre $X$ para la que existe una estructura $T$-coalgebraica $\gamma:R\rightarrow TR$ tal que las proyecciones $\pi_1:R\rightarrow X$, $\pi_2:R\rightarrow X$ son homomorfismos de $T$-coálgebras. Si $(X,\chi)$ es la coálgebra final de la categoría de $T$-coálgebras, entonces $\pi_1=\pi_2$.
     En el caso anterior, una relación $R$ es una bisimulación si y sólo si el siguiente diagrama conmuta: $$\begin{xy} \xymatrix{ A^\mathbb{N}\ar[d]_{(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}})} & R\ar[r]^{\pi_2}\ar[l]_(.45){\pi_1}\ar[d]^{(\mathrm{\textbf{val}},\mathrm{\textbf{sig}})} & A^\mathbb{N}\ar[d]^{(\mathrm{\textbf{cab}},\mathrm{\textbf{cola}})}\\ A\times A^\mathbb{N} & A\times R\ar[r]_{1\times\pi_2}\ar[l]^(.45){1\times\pi_1} & A\times A^\mathbb{N} }\end{xy}$$ si y sólo si $\mathrm{\textbf{cab}}\,\sigma=\mathrm{\textbf{val}}(\sigma,\tau)=\mathrm{\textbf{cab}}\,\tau$ con $\mathrm{\textbf{cola}}\,\sigma=\pi_1\,\mathrm{\textbf{sig}}(\sigma,\tau)$ y $\mathrm{\textbf{cola}}\,\tau=\pi_2\,\mathrm{\textbf{sig}}(\sigma,\tau)$, es decir, $R(\mathrm{\textbf{cola}}\,\sigma,\mathrm{\textbf{cola}}\,\tau)$.

Forma normal conjuntiva y demostración automática de teoremas

En los pocos libros de lógica que he hojeado o leído, los autores no llegan a explicar la importancia de las formas normales clausales (la normal conjuntiva y la normal disyuntiva), a pesar de que sí les dedican unas líneas a describirlas. Supongo que ha sido así porque son libros poco inclinados a la demostración automática de teoremas; por lo menos, la importancia de la forma normal conjuntiva radica ahí. Así que las siguientes líneas las dedico a establecer la conexión entre la forma normal conjuntiva y la demostración automática de teoremas.
     Para mostrar la relación entre la forma normal conjuntiva y la demostración automática de teoremas, haré lo siguiente: (1) calcular, salvo equivalencia lógica, el número total de proposiciones formadas a partir de otras; (2) describir la forma normal conjuntiva; (3) dar, salvo equivalencia lógica, formas explícitas de todas las proposiciones a partir de otras mediante una forma normal conjuntiva distinguida, y (4) dar expresiones explícitas de todas las proposiciones que son deducciones de un conjunto finito de axiomas.
     Calculemos, salvo equivalencia lógica, el número total de proposiciones a partir de otras. La totalidad de proposiciones que se pueden formar por combinación mediante los conectivos lógicos a partir de un número finito de proposiciones elementales $P_1,\ldots,P_n$ es, salvo equivalencia lógica, $2^{2^n}$. En efecto, para la verdad o falsedad de las proposiciones elementales hay $2^n$ posibilidades, puesto que cada $P_1,\ldots,P_n$ puede ser verdadera o falsa. La verdad o falsedad de una proposición compuesta por $P_1,\ldots,P_n$ está determinada por la verdad o falsedad de cada uno de los $2^n$ casos.
     Definamos y describamos las formas normales conjuntivas. Toda combinación de proposiciones formada mediante los conectivos lógicos (es decir, toda fórmula) se puede llevar a cierta forma normal a través de equivalencias lógicas. Esta forma normal consiste en una conjunción de disyunciones en las que cada componente es o una proposición elemental o la negación de una. Esto se puede hacer mediante las siguientes reglas.

• Aplicar las leyes asociativas, conmutativas y distributivas para los conectivos $\wedge$ y $\vee$
• Sustituir $\neg\neg P$ con $P$
• Sustituir $\neg(P\wedge Q)$ con $\neg P\vee\neg Q$ y $\neg(P\vee Q)$ con $\neg P\wedge\neg Q$.
• Sustituir $P\Rightarrow Q$ con $\neg P\vee Q$ y $P\Leftrightarrow Q$ con $(\neg P\vee Q)\wedge(\neg Q\vee P)$.

Por ejemplo, la expresión $$\neg((PQ\wedge\neg Q)\vee(R\wedge Q))$$ es equivalente a $$\neg P Q\wedge\neg Q Q\wedge\neg R\neg Q,$$ y la expresión $$(P\Rightarrow Q)\equiv(\neg Q\Rightarrow\neg P)$$ a $$PQ\neg P\wedge\neg QQ\neg P\wedge\neg Q\neg PQ\wedge P\neg PQ.$$ (Para simplicar las expresiones, se está omitiendo a $\vee$ y adoptando la convención de que hay prioridad de $\wedge$ sobre $\vee$ para los paréntesis).
     Demos, salvo equivalencia lógica, expresiones explícitas de todas las proposiciones a partir de otras. Salvo las expresiones tautológicas, toda expresión construida a partir de las proposiciones $P_1,\ldots,P_n$ es equivalente a una conjunción que es parte de la conjunción obtenida al desarrollar, de acuerdo a la ley distributiva $P(Q\wedge R)\equiv PQ\wedge PR$, la expresión $(P_1\wedge \neg P_1)(P_2\wedge\neg P_2)\cdots(P_n\wedge\neg P_n)$. En efecto, llevemos la expresión construida a partir de $P_1,\ldots,P_n$ a una forma normal conjuntiva. Como el valor de verdad de la expresión no cambia si se omite un conyunto verdadero, omitimos los conyuntos que contengan a $P$ y a $\neg P$. También cambiamos los $P\vee P$ por $P$. Así que cada uno de los conyuntos restantes es simplemente una disyunción cuyos disyuntos son elementos, con subíndice distinto, del conjunto $\{P_1,\ldots,P_n\}$. Si una disyunción no tiene ni a $P_i$ ni a $\neg P_i$, insertamos el término $(P_i\wedge\neg P_i)$ y aplicamos $P(Q\wedge R)\equiv PQ\wedge PR$. Luego, cada conyunto contiene o a $P_i$ o a $\neg P_i$ para todo $i$. Es decir, hay $2^n$ conyuntos posibles y un total de $\sum_{k=0}^{k=2^n}\binom{2^n}{k}=\mathcal{P}(2^n)=2^{2^n}$ conjunciones posibles con estos conyuntos. La conjunción impropia que surge de omitir todos los conyuntos es considerada una tautología.
     Por ejemplo, las cuatro diferentes proposiciones construidas a partir de $P$ son $$P\wedge\neg P\,,P\,,\neg P\,,P\vee\neg P.$$ Notemos que $P\vee\neg P$ corresponde a la conjunción impropia. Las dieciséis diferentes proposiciones construidas a partir de $P$ y $Q$ son \begin{align} &PQ\wedge\neg PQ\wedge P\neg Q\wedge\neg P\neg Q\,,PQ\wedge\neg PQ\wedge P\neg Q,\notag\\ &PQ\wedge P\neg Q\wedge\neg P\neg Q\,,PQ\wedge\neg PQ\wedge\neg P\neg Q\,,\neg PQ\wedge P\neg Q\wedge\neg P\neg Q,\notag\\ &PQ\wedge\neg PQ\,,PQ\wedge P\neg Q\,,PQ\wedge\neg P\neg Q\,,\neg PQ\wedge P\neg Q\,,\neg PQ\wedge\neg P\neg Q,\notag\\ &P\neg Q\wedge\neg P\neg Q\,,PQ\,,\neg PQ\,,P\neg Q\,,\neg P\neg Q,\notag\\ &(P\vee\neg P)\wedge (Q\vee\neg Q).\notag \end{align} Notemos que $(P\vee\neg P)\wedge (Q\vee\neg Q)$ corresponde a la conjunción impropia.
     Dadas las proposiciones $P_1,\ldots,P_n$, a los conyuntos individuales de la expresión $(P_1\wedge \neg P_1)(P_2\wedge\neg P_2)\cdots(P_n\wedge\neg P_n)$ desarrollada mediante la ley distributiva $P(Q\wedge R)\equiv PQ\wedge PR$ se los llama los constituyentes de $P_1,\ldots,P_n$, y diremos que las conjunciones obtenidas, como se mostró anteriormente, de las combinaciones de los conyuntos de esa expresión son las formas normales distinguidas de las proposiciones construidas a partir de $P_1,\ldots,P_n$.
     Calculemos, salvo equivalencia lógica, todas las deducciones a partir de los axiomas $A_1,\ldots, A_n$. Se tiene que la proposición $B$ es consecuencia lógica de estos si y sólo si $(A_1\wedge\cdots\wedge A_n)\Rightarrow B$ es una tautología. Sean $P_1,\ldots,P_m$ todas las proposiciones elementales que aparecen en $A_1,\ldots, A_n$ y conectemos todos nuestros axiomas $A_1,\ldots,A_n$ con $\wedge$, y supongamos que la combinación de proposiciones así obtenida está desarrollada en su forma normal distinguida en términos de $P_1,\ldots,P_m$. Tomemos entonces cualquier constituyente de $P_1,\ldots,P_m$ que no aparezca como conyunto en esta forma normal distinguida. Estos constituyentes se pueden transformar en una proposición falsa mediante una sustitució apropidada: un $P_i$ sustituido por una proposición verdadera si este $P_i$ está negado y un $P_i$ por una proposición falsa si este $P_i$ no lo está. Por otro lado, por medio de esta sustitución, nuestra forma normal distinguida queda transformada en una proposición verdadera, pues cada uno de sus conyuntos difieren de los constituyentes que no aparecen en ella en tener en al menos un lugar un disyunto que es la negación del del constituyente. Luego, los constituyentes que no aparecen en nuestra forma normal distinguida no son consecuencia lógica de los axiomas $A_1,\ldots,A_n$. Así que, obtenemos, salvo equivalencia lógica, a partir de nuestros axiomas, todas las consecuencias lógicas en las que aparecen las proposiciones elementales de nuestros axiomas como sigue: conectamos todos los axiomas mediante $\wedge$ y formamos la forma normal conjuntiva distinguida para la expresión resultante; finalmente, elegimos cualesquiera de los conyuntos de la forma normal distinguida de la conjunción de nuestros axiomas y hacemos su conjunción.

---

Estas notas están basadas en el libro Principles of mathematical logic de Hilbert y Ackermann. Interesante, aunque no extraño, que la conexión entre la forma normal conjuntiva y la demostración automática de teoremas la encontrara en un libro de Hilbert.

A fixing in a fence

— You know, a fence in lattice theory, more precisely an $n$-element fence in lattice theory, is an ordered set $\{x_1,\ldots,x_n\}$ in which $x_1$ is greater than $x_2$, $x_2$ less than $x_3$, $x_3$ greater than the next one, etc., and $x_n$ greater or less than $x_{n-1}$ depending whether $n$ is odd or even, or $x_1$ less than $x_2$, $x_2$ greater than $x_3$, etc., and its Hasse diagram looks like a zigzag.
— I see. So a defense is quite the opposite, and its Hasse diagram looks like a zagzig.
— No offense, but no!
— Exactly! (You're so emphatic, I like that.)

Don't be irrational

— This is Math.
— Hi, Math. So, what's your phone number?
— RATIONAL... You wouldn't like to dial forever, right?
— But...
— I know, I know, I know,...

Mónadas adjuntas en una 2-categoría

Samuel Eilenberg y John C. Moore, en su artículo Adjoint functors and triples, muestran la correspondencia biyectiva que existe entre las mónadas con adjunto derecho y las comónadas con adjunto izquierdo. Sus resultados se pueden generalizar a una 2-categoría $K$ tal que $K$ y $K^{co}$ admitan la construcción de álgebras. Aquí los detalles de tal generalización.

El mundo de $n^m$ espacios

Reempezando a leer la novela El mundo de ocho espacios de Jaime Romero Robledo, me vino a la mente la entrada El problema que me planteó la novela El mundo de ocho espacios (nunca terminé de leer la novela, por cierto), y se me ocurrió generalizar el problema a un 4-cubo (o un hipercubo de dimensión 4): calcular el número de caras interiores en un 4-cubo si dividimos sus aristas en $n$ partes iguales. Sin embargo, el problema se puede generalizar aún más: calcular el número de $k$-caras interiores y exteriores de un $m$-cubo si dividimos sus aristas en $n$ partes iguales.
     Obtuve lo siguiente. Si tenemos un $m$-cubo y dividimos cada arista (cada 1-cara) en $n$ partes iguales, obtenemos $$\binom{m}{k}(n-1)^{m-k}n^k\text{ $k$-caras interiores},$$ donde $k < m$ y $1\leq n$.
     Todavía no tengo muy claro cómo calcular el número de $k$-caras exteriores.

No hay álgebras booleanas completas libres sobre conjuntos infinitos

Mac Lane en su Categories for the working mathematician da dos ejemplos de funtores continuos con dominio pequeño-completo que no satisfacen la condición conjunto solución del Teorema de Freyd del Funtor Adjunto. Tal teorema dice lo siquiente.

Teorema de Freyd del Funtor Adjunto. Si $A$ es una categoría pequeño-completa con homoconjuntos pequeños, entonces un funtor $G:A\rightarrow X$ tiene adjunto izquierdo si y sólo si preserva todo límite pequeño y satisface lo siguiente.
     Condición conjunto solución. Para todo objeto $x\in X$, existe un conjunto pequeño $I$ y una familia de flechas $f_i:x\rightarrow Ga_i$ indexada por $I$ tal que toda flecha $h:x\rightarrow Ga$ se puede escribir como la composición $h=Gt\circ f_i$ para algún índice $i$ y alguna $t:a_i\rightarrow a$.

El ejemplo que me sorprendió e intrigó fue el segundo. Este empieza diciendo: “Dado un conjunto numerable $D$, uno puede construir un álgebra booleana completa arbitrariamente grande generada por $D$”. Tal afirmación la demostraron primero Gaifman y Hales de manera independiente utilizando argumentos de la lógica infinitaria y luego la demostró Solovay haciendo uso del álgebra abierta regular. La demostración de Solovay es mucho más simple. Hago un recuento detallado de esta demostración.

Sea $\kappa$ un cardinal infinito y dótese a $\kappa$ de la topología discreta. Considérese ahora a $\kappa^\omega$ con la topología producto. Sea $X:=\mathbf{AR}(\kappa^\omega)$, el álgebra abierta regular del espacio $\kappa^\omega$. Notemos que todo cerrabierto es regular; de donde, los $$A_{n,\eta}:=\{f\in \kappa^\omega\mid fn=\eta\},$$ con $\eta<\kappa$, son elementos de $X$: el conjunto $\{\eta\}$ es cerrabierto de $\kappa$; más aún, los $A_{n,\eta}$ son subbásicos de $\kappa^\omega$. Tenemos que la familia $\{A_{n,\eta}\mid n<\omega,\eta<\kappa\}$ genera a $X$; en efecto, sea $V\in X$; entonces, $V$ es unión de intersecciones finitas de $A_{n,\eta}$ s, digamos, $V=\bigcup V_i$; de donde, como $V$ es abierto regular y $\bigvee V_i=\mathrm{IntCl}(\bigcup V_i)$ es el abierto regular más pequeño que contiene a $\bigcup V_i$, tenemos que $V=\bigvee V_i$.
     Ahora, la cardinalidad de $X$ es al menos $\kappa$, pues si $\eta<\eta'<\kappa$, entonces $A_{0,\eta}$ y $A_{0,\eta'}$ son distintos.
     Antes de seguir, notemos que si $B\subseteq\kappa^\omega$ y $B$ depende de un número finito de coordenadas, entonces $B$ es cerrabierto. En efecto, que $B$ dependa de un número finito de coordenadas significa que $\exists\,n_1,\ldots,n_m\in\mathbb{N}$ $$B=\{f\in\kappa^\omega\mid R(fn_1,\ldots,fn_m)\},$$ donde $R\subseteq\kappa^m$ y $m\in\mathbb{N}$. Tenemos que $R$ es cerrabierto de $\kappa^m$ y $B=p^{-1}R$ con $p:\kappa^\omega\rightarrow\kappa^m$ definida como $pf:=(fn_1,\ldots,fn_m)$; $p$ es continua.
     Prosigamos. Dados $n,m<\omega$, defínase $$B_{n,m}:=\{f\in\kappa^\omega\mid fm\leq fn\}.$$ Entonces, por la observación anterior, $B_{n,m}$ es cerrabierto luego abierto regular. Afirmamos que los $B_{n,m}$ generan a $X$. En efecto, sea $Y$ la subálgebra completa más pequeña de $X$ que contiene a $\{B_{n,m}\mid n,m<\omega\}$. Bastará demostrar que $A_{n,\eta}\in Y$ para todo $n<\omega$ y para todo $\eta<\kappa$; hagámoslo por inducción sobre $\eta$; supongamos entonces que para $m<\omega$ y $\xi<\eta$ se tiene que $A_{m,\xi}\in Y$. Ahora, sean $$D_{n,\eta}:=\{f\in\kappa^\omega\mid fn<\eta\}\quad\text{y}\quad E_{n,\eta}:=\{f\in\kappa^\omega\mid fn\leq\eta\}$$ para $n<\omega$ y $\eta<\kappa$. Lo que queremos hacer es ver que $D_{n,\eta},E_{n,\eta}\in Y$, ya que $$A_{n,\eta}=D_{n,\eta}\cap E_{n,\eta}=D_{n,\eta}\wedge E_{n,\eta}.$$ Como $D_{n,\eta}$ y $E_{n,\eta}$ dependen sólo de una coordeanada, son cerrabiertos; luego, son elementos de $X$. Por inducción, estamos suponiendo que $A_{n,\xi}\in Y$, así que como $D_{n,\eta}$ es abierto regular y $$D_{n,\eta}=\bigcup_{\xi<\eta} A_{n,\xi},$$ entonces $D_{n,\eta}=\bigvee_{\xi<\eta} A_{n,\xi}\in Y$.
     Por otro lado, dados $n,m<\omega$, $$C_{m,n}:=\{f\in\kappa^\omega\mid fn\leq fm\text{ o }fm<\eta\}$$ es cerrabierto, ya que su definición depende sólo de $m$ y $n$; luego, $C_{m,n}\in X$. Notemos que $$C_{m,n}=B_{m,n}\cup\bigvee_{\xi<\eta} A_{m,\xi}.$$ Nuevamente, como $C_{m,n}\in X$, se tiene que $C_{m,n}=B_{m,n}\vee\bigvee_{\xi<\eta} A_{m,\xi}$. De donde, $C_{m,n}\in Y$. Demostremos que $E_{n,\eta}=\bigwedge_{m<\omega} C_{m,n}$; es decir, que $E_{n,\eta}=\mathrm{Int}(\bigcap_{m<\omega} C_{m,n})$.
     Ahora, dados $n<\omega$ y $f\in\kappa^\omega$, los $$U(n,f):=\{h\in\kappa^\omega\mid\forall\,m\leq n\; hm=fm\}$$ forman una base para $\kappa^\omega$ (es claro que $U(n,f)\in\tau(\kappa^\omega)$). En efecto, sea $\langle U_{i_1},\ldots,U_{i_m}\rangle$ un básico de $\kappa^\omega$ y sea $f\in\langle U_{i_1},\ldots,U_{i_m}\rangle$. Sin pérdida de generalidad, supóngase que $i_1<\cdots < i_m$. Entonces, $U(i_m,f)\subseteq\langle U_{i_1},\ldots,U_{i_m}\rangle$.
     Demostremos que $E_{n,\eta}=\mathrm{Int}(\bigcap_{m<\omega} C_{m,n})$. Sea $g\in E_{n,\eta}$; es decir, $gn\leq\eta$. Entonces, $U(n,g)\subseteq\bigcap_{m<\omega} C_{m,n}$, pues si $h\in U(n,g)$, entonces dado $m<\omega$, si $hn\leq hm$ entonces $h\in C_{m,n}$ y si $hm< hn=gn$ entonces $hm<\eta$ y $h\in C_{m,n}$; luego, $h\in\bigcap_{m<\omega} C_{m,n}$.
     Recíprocamente, sea $g\in\mathrm{Int}(\bigcap_{m<\omega} C_{m,n})$ y supóngase que $gn>\eta$. Como $g\in\mathrm{Int}(\bigcap_{m<\omega} C_{m,n})$, existe $N\in\omega$ tal que $U(N,g)\subseteq\bigcap_{m<\omega} C_{m,n}$. Como $U(k,g)\subseteq U(N,g)$ para todo $k\geq N$, podemos suponer que $N\geq n$. Ahora defínase $h:\omega\rightarrow\kappa$ como $$hm:=\begin{cases} gm &\text{si $m\leq N$,}\\ \eta &\text{si $m > N$}. \end{cases}$$ Entonces, $h\in U(N,g)\subseteq\bigcap_{m<\omega} C_{m,n}$; de donde, $h\in C_{N+1}$; es decir, $hn< h(N+1)$ o $h(N+1)<\eta$. Sin embargo, $h(N+1)=\eta< gn=hn$ y $h(N+1)\geq\eta$ !! Luego, $g\in E_{n,\eta}$. Así que $E_{n,\eta}\in Y$.
     Por lo tanto, $X$, que tiene cardinalidad por lo menos $\kappa$, es generado por $\{B_{n,m}\mid n,m<\omega\}$, que es numerable.
     Así que tenemos el siguiente teorema.

Teorema (Solovay). Sea $\kappa$ un cardinal infinito. Si $\kappa$ tiene la topología discreta y $\kappa^\omega$ la topología producto, entonces $\mathbf{AR}(\kappa^\omega)$ es un álgebra boolena completa numerablemente generada con cardinalidad por lo menos $\kappa$.

Y tenemos el siguiente corolario.

Corolario. No hay álgebras booleanas completas libres sobre conjuntos infinitos.

Demostración. Sean $X$ un conjunto infinito, $FX$ el álgebra completa libre generada por $X$ y $\eta_X:X\rightarrow FX$ la función con la propiedad universal de álgebra libre. Sea $\kappa$ un cardinal mayor que $|FX|$. Entonces, por el teorema anterior, $\mathbf{AR}(\kappa^\omega)$ tiene un conjunto numerable $Y$ de generadores. Sea $f:X\rightarrow Y$ una función suprayectiva. Entonces, si $g:FX\rightarrow\mathbf{AR}(\kappa^\omega)$ es homomorfismo de álgebras booleanas completas y $g\circ\eta_X=f$, entonces $gFX$ es una subálgebra completa de $\mathbf{AR}(\kappa^\omega)$ que incluye a $Y$; de donde, $g$ sería suprayectiva y $\kappa\leq|\mathbf{AR}(\kappa^\omega)|\leq|FX|<\kappa$ !!

El álgebra abierta regular de un espacio topológico

Leyendo sobre el Teorema de Freyd del Funtor Adjunto, me topé con un álgebra booleana completa que no conocía y que resultó ser un ejemplo estándar en teoría de álgebras booleanas: el álgebra abierta regular de un espacio topológico.
     Tal álgebra booleana se construye como sigue. Sea $X$ un espacio topológico. Definimos $$\mathbf{AR}(X):=\{V\subseteq X\mid V=\mathrm{IntCl}V\},$$ donde $\mathrm{Int}$ es el operador interior y $\mathrm{Cl}$ el operador cerradura. Es decir, $\mathbf{AR}(X)$ es el conjunto de los abiertos regulares de $X$ (un subconjunto $U\subseteq X$ se dice que es abierto regular si $U=\mathrm{IntCl}U$; dado $A\subseteq X$, a $\mathrm{IntCl}A$ se la llama la regularización de $A$). Se tiene que $\mathbf{AR}(X)$ es un álgebra booleana completa con el orden dado por la inclusión y bajo las siguientes operaciones $\bigvee$, $\bigwedge$ y $'$: $$\begin{align} \bigvee\mathcal{U} &:=\mathrm{IntCl}(\bigcup\mathcal{U})&(\mathcal{U}\subseteq\mathbf{AR}(X))\notag\\ \bigwedge\mathcal{U} &:=\mathrm{Int}(\bigcap\mathcal{U})&\notag\\ V' &:=\mathrm{Int}(X-V)&(V\in\mathbf{AR}(X)).\notag \end{align}$$      En general se tiene que \begin{equation} \text{si $A$ es un cerrado de un espacio $Y$, entonces $\mathrm{Int}A$ es abierto regular.} \end{equation} En efecto, sea $A$ cerrado de un espacio $Y$; entonces, $$\mathrm{Int}A\subseteq\mathrm{IntClInt}A.$$ Recíprocamente, se tiene que $\mathrm{Int}A\subseteq A$; de aquí, $\mathrm{ClInt}A\subseteq A$; luego, $$\mathrm{IntClInt}A\subseteq\mathrm{Int}A.$$      Ahora, tenemos entonces que $\bigvee\mathcal{U}\in\mathbf{AR}(X)$, pues $\mathrm{Cl}(\bigcup\mathcal{U})$ es cerrado de $X$, y $V'\in\mathbf{AR}(X)$ porque $X-V$ también es cerrado de $X$.      En general se tiene si $\{A_i\}$ es una familia de subconjuntos de un espacio topológico $Y$, entonces \begin{align} &\mathrm{Cl}(\bigcap A_i)\subseteq \bigcap\mathrm{Cl}A_i \\ &\mathrm{Int}(\bigcap A_i)\subseteq \bigcap\mathrm{Int}A_i. \end{align} En efecto, (2) se sigue de que $\bigcap A_i\subseteq\bigcap\mathrm{Cl}A_i$ y (3) de que $\mathrm{Int}(\bigcap A_i)\subseteq\mathrm{Int}A_i$.
     Veamos entonces que $\bigwedge\mathcal{U}\in\mathbf{AR}(X)$. Sea $\{V_i\}$ una familia de elementos de $\mathbf{AR}(X)$. Ya se tiene que $\mathrm{Int}(\bigcap V_i)\subseteq\mathrm{IntClInt}(\bigcap V_i)$, así que basta ver la contención recíproca. Notemos que como cada $V_i\in\mathbf{AR}(X)$, $$V_i=\mathrm{IntCl}V_i.$$ Entonces, \begin{align} \mathrm{IntClInt}(\bigcap V_i)&\subseteq\mathrm{IntClInCl}(\bigcap V_i)\notag\\ &=\mathrm{IntCl}(\bigcap V_i)&\text{(por (1)}\notag\\ &\subseteq\bigcap\mathrm{IntCl}V_i &\text{(por (2) y (3))}\notag\\ &=\bigcap V_i\notag; \end{align} de donde, $\mathrm{IntClInt}(\bigcap V_i)\subseteq\mathrm{Int}(\bigcap V_i)$.
     Se tiene que $\emptyset,X\in\mathbf{AR}(X)$, y es fácil ver que $$V\wedge V'=\emptyset\qquad\text{y}\qquad V\vee V'=X.$$      Sea $\mathcal{U}\subseteq\mathbf{AR}(X)$. Veamos que $\bigvee\mathcal{U}$ es la mínima cota superior de $\mathcal{U}$ en $\mathbf{AR}(X)$ y que $\bigwedge\mathcal{U}$ es la máxima cota inferior de $\mathcal{U}$ en $\mathbf{AR}(X)$. Se tiene que $\bigcup\mathcal{U}$ es abierto y es el conjunto más pequeño que incluye a cada $V\in\mathcal{U}$; de donde, $\bigvee\mathcal{U}$ es la mínima cota superior de $\mathcal{U}$ en $\mathbf{AR}(X)$. Ahora, tenemos que $\bigwedge\mathcal{U}\subseteq V$ para todo $V\in\mathcal{U}$ y $\bigwedge\mathcal{U}\in\mathbf{AR}(X)$. Sea $B$ otra cosa inferior de $\mathcal{U}$; entonces, $B\subseteq\bigcap\mathcal{U}$; de donde, $B\subseteq\bigwedge\mathcal{U}$, pues $B$ es abierto de $X$.
     Finalmente, veamos que $$V\wedge(\bigvee V_i)=\bigvee(V\wedge V_i).$$      En general, se tiene que \begin{equation} \text{si $U$ es abierto de un espacio $Y$, entonces $\mathrm{Cl}(U\cap A)=\mathrm{Cl}(U\cap\mathrm{Cl}A)$ para todo subconjunto $A$ de $Y$} \end{equation} (véase el punto 1 de la entrada anterior). De aquí, \begin{equation} \text{si $U$ es abierto de $Y$, $U\cap\mathrm{Cl}A\subseteq\mathrm{Cl}(U\cap A)$ para todo $A\subseteq Y$.} \end{equation}      Ahora, sea $\{V_i\}$ una familia de elementos de $\mathbf{AR}(X)$ y sea $V\in\mathbf{AR}(X)$. Entonces, \begin{align} V\wedge\bigvee V_i &=V\cap\mathrm{IntCl}(\bigcup V_i)\notag\\ &=\mathrm{Int}V\cap\mathrm{IntCl}(\bigcup V_i)\notag\\ &=\mathrm{Int}(V\cap\mathrm{Cl}(\bigcup V_i)) &\text{(propiedad de $\mathrm{Int}$)}\notag\\ &\subseteq\mathrm{IntCl}(V\cap\bigcup V_i) &\text{(por (5))}\notag\\ &=\bigvee(V\wedge V_i)\notag. \end{align} Recíprocamente, \begin{align} \bigvee(V\wedge V_i) &=\mathrm{IntCl}(\bigcup V\cap V_i)\notag\\ &=\mathrm{IntCl}(V\cap\bigcup V_i)\notag\\ &\subseteq\mathrm{IntCl}V\cap\mathrm{IntCl}(\bigcup V_i)&\text{(por (2) y (3))}\notag\\ &=V\wedge\bigvee V_i\notag. \end{align}      Por lo tanto, $(\mathbf{AR}(X),\vee,\wedge,',\emptyset,X)$ es un álgebra booleana completa. A dicha álgebra se la llama el álgebra abierta regular de $X$.

Topología general julio 2015

1. Sea $(X,\tau)\in\mathbf{Top}$ y sea $U\subseteq X$. Entonces, $U\in\tau$ si y sólo si $\forall\,A\subseteq X\;\mathrm{Cl}(U\cap A)=\mathrm{Cl}(U\cap\mathrm{Cl}A)$.
   
   Supóngase que $U\in\tau$ y sea $A\subseteq X$. Como $U\cap A\subseteq U\cap\mathrm{Cl}A$, $\mathrm{Cl}(U\cap A)\subseteq\mathrm{Cl}(U\cap\mathrm{Cl}A)$. Veamos entonces que $\mathrm{Cl}(U\cap\mathrm{Cl}A)\subseteq\mathrm{Cl}(U\cap A)$. Sea $x\in\mathrm{Cl}(U\cap\mathrm{Cl}A)$ y $V\in\tau(x,X)$ (un abierto de $X$ que contiene a $x$). Entonces, $V\cap U\cap\mathrm{Cl}A\neq\emptyset$; sea entonces $y\in V\cap U\cap\mathrm{Cl}A$; de aquí, $y\in V\cap U$ y $y\in\mathrm{Cl}A$; de donde, $V\cap U\cap A\neq\emptyset$. Por lo tanto, $x\in\mathrm{Cl}(U\cap A)$.
        Recíprocamente, supóngase que $\forall\,A\subseteq X\;\mathrm{Cl}(U\cap A)=\mathrm{Cl}(U\cap\mathrm{Cl}A)$. Entonces, $$\emptyset=\mathrm{Cl}(U\cap(X-U))=\mathrm{Cl}(U\cap\mathrm{Cl}(X-U));$$ de donde, $U\cap\mathrm{Cl}(X-U)=\emptyset$; de aquí, $U\cap\mathrm{Fr}U=\emptyset$; luego, $U\in\tau$.
2. Sea $\{(X_\alpha,\tau_\alpha)\}$ una familia infinita de espacios topológicos tal que $\mathcal{B}:=\{\alpha\mid X_\alpha\text{ es compacto}\}$ es finito. Sea $B\subseteq\prod X_\alpha$. Si $B$ es compacto, entonces $\mathrm{Int}B=\emptyset$.
   
   Supóngase que $B$ es compacto y que $\mathrm{Int}B\neq\emptyset$. Entonces, dado $(x_\alpha)\in\mathrm{Int}B$, existe $\langle U_{\alpha_1},\ldots,U_{\alpha_n}\rangle$ básico de $\tau$ (la topología producto) tal que $$(x_\alpha)\in\langle U_{\alpha_1},\ldots,U_{\alpha_n}\rangle\subseteq\mathrm{Int}B\subseteq B.$$ Sea $\beta\notin\mathcal{B}$ tal que $\beta\neq\alpha_i$; así que $X_\beta$ no es compacto. Por otro lado, $$X_\beta=p_\beta\langle U_{\alpha_1},\ldots,U_{\alpha_n}\rangle\subseteq p_\beta B\subseteq X_\beta,$$ donde $p_\beta:\prod X_\alpha\rightarrow X_\beta$ es la proyección en $X_\beta$. Entonces, $p_\beta B=X_\beta$; es decir, $X_\beta$ es compacto !!
        Otra manera. Supóngase que $B$ es compacto y que $\mathrm{Int}B\neq\emptyset$. Entonces, dado $(x_\alpha)\in\mathrm{Int}B$, existe $\langle U_{\alpha_1},\ldots,U_{\alpha_n}\rangle$ básico de $\tau$ (la topología producto) tal que $$(x_\alpha)\in\langle U_{\alpha_1},\ldots,U_{\alpha_n}\rangle\subseteq\mathrm{Int}B\subseteq B.$$ Sea $\beta\notin\mathcal{B}$ tal que $\beta\neq\alpha_i$; así que $X_\beta$ no es compacto. Luego, existe una cubierta abierta $\{V_i\}$ de $X_\beta$ que no tiene subcubierta finita. Sea $Y_\beta:=\prod_{\alpha\neq\beta} X_\alpha$. Entonces, $\{V_i\times Y_\beta\}$ es cubierta abierta de $B$, pero $B$ es compacto; luego, existen $V_{i_1},\ldots,V_{i_m}$ de $\{V_i\}$ tal que $$B\subseteq(V_{i_1}\times Y_\beta)\cup\cdots\cup(V_{i_m}\times Y_\beta),$$ pero $\langle U_{\alpha_1},\ldots,U_{\alpha_n}\rangle\not\subseteq (\cup V_{i_j})\times Y_\beta$ !!
3. Sea $(X,\tau)\in\mathbf{Top}$ $T_2$ y $f:[0,1]\rightarrow(X,\tau)$ continua y suprayectiva, donde $[0,1]$ tiene la topología usual. Entonces, $X$ es localmente conexo.
   
   Esta afirmación se puede generalizar. Sean $(Y,\tau'),(X,\tau)\in\mathbf{Top}$ con $(Y,\tau')$ compacto y $T_2$ y $(X,\tau)$ $T_2$. Sea $f:(Y,\tau')\rightarrow(X,\tau)$ continua y suprayectiva. Si $Y$ es localmente conexo, entonces $X$ también.
   
   Veamos primero que $f:Y\rightarrow X$ es cerrada. Sea $B\subseteq Y$ cerrado; entonces, como $Y$ es compacto, $B$ es compacto; de aquí, $fB$ es compacto en $X$, que es $T_2$; luego, $fB$ es cerrado.
        Por otro lado, toda función continua cerrada (o abierta) y suprayectiva es una identificación, un mapeo cociente. En efecto, sea $g:(Z,\sigma)\rightarrow(Z',\sigma')$ una tal función y sea $V\subseteq Z'$ tal que $g^{-1}V\in\sigma$. Entonces, $Z-g^{-1}V=g^{-1}(Z'-V)$ es cerrado de $Z$. Como $g$ es cerrada y suprayectiva, $Z'-V=gg^{-1}(Z'-V)$ es cerrado de $Z'$; de donde $V\in\sigma'$.
        Ahora, veamos que toda identificación preserva conexidad local. Sea $h:(Z,\sigma)\rightarrow(Z',\sigma')$ una identificación y supóngase que $Z$ es localmente conexo. Demostremos que las componentes de todo subespacio abierto $A$ de $Z'$ son abiertos de $Z'$. Sea $A\subseteq Z'$ tal que $A\in\sigma'$. Sea $C$ componente de $A$. Veamos que $C\in\sigma'$. Sea $B$ componente de $h^{-1}C\subseteq h^{-1}A$. Afirmamos que $B$ es componente de $h^{-1}A$; en efecto, sea $B'$ componente de $h^{-1}A$ tal que $B\subseteq B'$. Entonces, tenemos que $hB\subseteq hB',C\subseteq A$, pero $hB$ y $hB'$ son conexos así que, como $C$ es componente de $A$ y $hB\subseteq hB',C$, se tiene que $hB'\subseteq C$; de donde, $B'\subseteq h^{-1}C$ con $B'$ conexo y $B\subset B'$, pero $B$ es componente de $h^{-1}C$; luego, $B=B'$.
        Por otro lado, como $h^{-1}A\in\sigma$ y $Z$ es localmente conexo, toda componente de $h^{-1}A$ es abierta, así que $B\in\sigma$. Entonces, como $h^{-1}C$ es la unión de sus componentes, que son abiertas, $h^{-1}C\in\sigma$; de donde, como $h$ es identificación, $C\in\sigma'$. Luego, $Z'$ es localmente conexo.
4. Considérese la recta de Sorgenfrey. Un espacio topológico $(X,\tau)$ se dice que es homogéneo si $\forall\,x,y\in X\,\exists\, f:X\rightarrow X\;$ homeomorfismo tal que $fx=y$.
   1. La recta de Sorgenfrey es homogénea.
   2. El producto de espacios homogéneos es homogéneo.
   
   4(a). Sean $x,y\in\mathbb{R}$. Defínase $f:\mathbb{R}\rightarrow\mathbb{R}$ como $$fz:=z+y-x.$$ Claramente, $fx=y$, y dado un intervalo $[a,b)$, $$f^{-1}[a,b)=[a-x+y,b-x+y);$$ de donde, $f$ es continua. Es claro que su inversa $f^{-1}z=z-x+y$ también es continua.
   
   4(b). Sea $\{X_\alpha\}$ una familia de espacios homogéneos. Sean $(x_\alpha),(y_\alpha)\in\prod X_\alpha$. Entonces, $\forall\,\alpha\;\exists\,f_\alpha:X_\alpha\rightarrow X_\alpha\;$ homeomorfismo tal que $f_\alpha x_\alpha=y_\alpha$. Considérese el siguiente diagrama conmutativo: $$\require{AMScd} \begin{CD} \prod X_\alpha @>p_\beta>> X_\beta\\ @V\prod f_\alpha VV & @VVf_\beta V\\ \prod X_\alpha @>>p_\beta> X_\beta\\ @V\prod f^{-1}_\alpha VV @VVf^{-1}_\beta V\\ \prod X_\alpha @>>p_\beta> X_\beta \end{CD}$$ Entonces, por la propiedad universal del producto y porque $f^{-1}_\beta f_\beta=1$ para todo $\beta$, $\prod f^{-1}_\alpha\prod f_\alpha=1$; similarmente, $\prod f_\alpha\prod f^{-1}_\alpha=1$. Luego, $\prod f_\alpha$ es homeomorfismo, y $\prod f_\alpha(x_\alpha)=(y_\alpha)$.
5. 1. No existe un espacio conexo completamente regular y numerable con al menos dos puntos.
   2. No existe un espacio conexo regular y numerable con al menos dos puntos.
   
   5(b). Si $(X,\tau)$ es un espacio con un solo punto, es regular conexo y numerable.
        Supóngase que $X$ tiene al menos dos puntos, que es regular conexo y numerable. Entonces, como $X$ es numerable, $X$ es Lindelöf. Como todo Lindelöf $T_3$ es $T_4$, se tiene que, dados $x,y\in X$, $x\neq y$, existe una función continua $f:X\rightarrow[0,1]$ tal que $fx=0$ y $fy=1$ (notemos que como $X$ es regular, $X$ también es $T_2$, así que $\{x\}$ y $\{y\}$ son cerrados). Sin embargo, como $f$ es continua y $X$ es conexo, $fX$ es conexo. Por otro lado, $fX$ es numerable; de donde, $fX$ es disconexo !!
        Otra manera. Supóngase que $X$ tiene al menos dos puntos, que es regular conexo y numerable. Entonces, como $X$ es numerable, $X$ es Lindelöf. Como todo Lindelöf $T_3$ es $T_4$, se tiene que, dados $x,y\in X$, $x\neq y$, existe una función continua $f:X\rightarrow[0,1]$ tal que $fx=0$ y $fy=1$. Ahora, como $f$ es continua y $X$ es conexo, $fX$ es conexo con $0,1\in fX$. Luego, $[0,1]=fX$; de donde, $$|X|\geq |[0,1]|;$$ de aquí, $X$ es no numerable !!
   
   5(a). Todo espacio $T_{3\frac{1}{2}}$ es $T_3$.
6. Si $(X,\tau)$ es un espacio compacto $T_2$ entonces $\forall\,f:X\rightarrow X$ continua $\exists\,A\subseteq X$ cerrado no vacío tal que $fA=A$.
   
   Antes de demostrar el resultado, demostremos la siguiente afirmación. Si $f:X\rightarrow Y$ es una función continua con $X$ compacto y $Y$ $T_2$ y $\{F_n\}$ es una sucesión decreciente de subconjuntos cerrados de $X$, entonces $f(\cap F_n)=\cap fF_n$. En efecto, si existe $n$ tal que $F_n=\emptyset$, entonces se tiene la igualdad deseada. Supóngase entonces que $F_n\neq\emptyset$ para todo $n$. Ahora, como ya se tiene que $f(\cap F_n)\subseteq\cap fF_n$, basta ver que $\cap fF_n\subseteq f(\cap F_n)$.
        Como $f$ es continua, $fF_1$ es compacto, y como $\{fF_n\}$ es decreciente, $\cap fF_n\neq\emptyset$. Sea $y\in\cap fF_n$; entonces, $\forall\,n\;\exists\; b_n\in F_n\; y=fb_n$. De donde, $\forall\,n\; F_n\cap f^{-1}y\neq\emptyset$. Como $Y$ es $T_2$, $\{y\}$ es cerrado de $Y$, así que $f^{-1}y$ es cerrado de $X$. Luego, tenemos una sucesión decreciente $\{F_n\cap f^{-1}y\}$ de subconjuntos cerrados no vacíos de $X$, que es compacto. Por lo tanto, $\cap F_n\cap f^{-1}y\neq\emptyset$, y $$y\in f(\cap F_n\cap f^{-1}y)\subseteq f(\cap F_n).$$ Luego, $\cap fF_n\subseteq f(\cap F_n)$.
        Ahora, volviendo al resultado que queríamos demostrar, sea $g:X\rightarrow X$ una función continua con $X$ compacto y $T_2$. Tenemos entonces la siguiente sucesión decreciente de subconjuntos cerrados no vacíos de $X$: $\{g^nX\}$, donde $g^n$ es simplemente la composición $g\circ\cdots\circ g$ con $g$ apareciendo n veces. De la afirmación anterior, $g(\cap g^nX)=\cap g^{n+1}X=\cap g^nX$ y $\cap g^nX\neq\emptyset$. Sea $A:=\cap g^nX$.
7. Sea $(X,\tau)$ un espacio topológico y $R$ una relación de equivalencia sobre $X$. Supóngase que la proyección canónica $p:X\rightarrow X/R$ es abierta. Sea $B\subseteq X/R$. Entonces, $B$ es homeomorfo a $p^{-1}B/R_0$, donde $R_0$ es la relación inducida por $R$ sobre $p^{-1}B$.
   
   Otra vez, antes de demostrar la afirmación que nos concierne, demostremos el siguiente resultado. Si $f:X\rightarrow Y$ es una identificación abierta y $B\subseteq Y$, entonces $\tau(B)=\tau(f,B)$, donde $\tau(B)$ es la topología de subespacio inducida sobre $B$ por la topología $\tau(Y)$ de $Y$ y donde $\tau(f,B)$ es la topología de identificación inducida sobre $B$ por la suprayección $f\mid_{f^{-1}B}:f^{-1}B\rightarrow B$. En efecto, supóngase que $f:X\rightarrow Y$ es una identificación abierta. Como $\tau(f,B)$ es la topología más grande que hace a $f\mid_{f^{-1}B}:f^{-1}B\rightarrow B$ continua y como $f\mid_{f^{-1}B}:f^{-1}B\rightarrow B$ es continua si $B$ tiene la topología $\tau(B)$, entonces $\tau(B)\subseteq\tau(f,B)$. Veamos que se tiene la otra contención. Sea $V\in\tau(f,B)$; entonces, $f^{-1}V\in\tau(f^{-1}B)$; de donde, existe $W\in\tau(X)$ tal que $f^{-1}V=f^{-1}B\cap W$; de aquí, $$V=ff^{-1}V=B\cap fW;$$ luego, como $f$ es abierta, $V\in\tau(B)$.
        Volvamos a la afirmación que queríamos demostrar. Del resultado anterior, tenemos entonces que $p\mid_{p^{-1}B}:p^{-1}B\rightarrow B$ es una identificación; es decir, $p\mid_{p^{-1}B}:p^{-1}B\rightarrow B$ es continua suprayectiva y $\tau(B)=\tau(p,B)$. Por otro lado, notemos que $R_0=(p^{-1}B\times p^{-1}B)\cap R$. Sea $q:p^{-1}B\rightarrow p^{-1}B/R_0$ la proyección canónica. Veamos que $\mathrm{ker\,}p\mid_{p^{-1}B}=\mathrm{ker\,}q$. Sean $x,y\in p^{-1}B\times p^{-1}B$. Entonces, $$(x,y)\in\mathrm{ker\,}p\mid_{p^{-1}B}\;\Leftrightarrow\; px=py\;\Leftrightarrow\;x R_0 y\;\Leftrightarrow\;qx=qy\;\Leftrightarrow\;(x,y)\in\mathrm{ker\,}q.$$ De aquí y por la propiedad universal de una identificación, existen únicas $s:B\rightarrow p^{-1}B/R_0$ y $t:p^{-1}B/R_0\rightarrow B$ funciones inyectivas continuas tales que el siguiente diagrama conmuta: $$\require{AMScd} \begin{CD} p^{-1}B @> p\mid_{p^{-1}B} >> B\\ @| & @VsVV\\ p^{-1}B @> q >> p^{-1}B/R_0\\ @| & @VtVV\\ p^{-1}B @>> p\mid_{p^{-1}B} > B; \end{CD}$$ de aquí, por la propiedad universal de $p\mid_{p^{-1}B}$, $ts=1_B$. Luego, $t$ es suprayectiva; por lo tanto, $t$ es un homeomorfismo con inversa $s$.
8. Considérese a $\mathbb{R}$ con la topología $\sigma$ cuyos básicos son los intervalos $[a,b)$; en otras palabras, $(\mathbb{R},\sigma)$ es la recta de Sorgenfrey. Sea $\tau$ la topología sobre $\mathbb{R}$ dada por los básicos $[q,b)$ con $q\in\mathbb{Q}$.
   1. $(\mathbb{R},\sigma)\times(\mathbb{R},\sigma)$ no es metrizable.
   2. $(\mathbb{R},\sigma)\times(\mathbb{R},\tau)$ no es metrizable.
   3. $(\mathbb{R},\tau)\times(\mathbb{R},\tau)$ es metrizable.
   
   8(a). $(\mathbb{R},\sigma)\times(\mathbb{R},\sigma)$ es el cuadrado de Sorgenfrey, el cual no es $T_4$, y todo espacio métrico es $T_4$; luego, $(\mathbb{R},\sigma)\times(\mathbb{R},\sigma)$ no es metrizable.
   
   8(b). Afirmamos que la recta de Sorgenfrey no es segundo numerable. En efecto, si lo fuera, entonces el cuadrado de Sorgenfrey lo sería; luego, el cuadrado de Sorgenfrey sería Lindelöf. Por otro lado, la recta de Sorgenfrey es $T_3$, pues los intervalos $[a,b)$ son abiertos y cerrados; así que el cuadrado de Sorgenfrey es $T_3$. Todo espacio Lindelöf y $T_3$ es $T_4$; por lo tanto, el cuadrado de Sorgenfrey es $T_4$ !! Así que la recta de Sorgenfrey no es segundo numerable.
        Ahora veamos que $(\mathbb{R},\sigma)\times(\mathbb{R},\tau)$ no es metrizable. Es claro que la recta de Sorgenfrey es separable y regular y que $(\mathbb{R},\tau)$ también. De donde, $(\mathbb{R},\sigma)\times(\mathbb{R},\tau)$ es separable y regular; sin embargo, como la recta de Sorgenfrey no es segundo numberable, $(\mathbb{R},\sigma)\times(\mathbb{R},\tau)$ tampoco lo es; de donde, $(\mathbb{R},\sigma)\times(\mathbb{R},\tau)$ no es metrizable.
   
   8(c). Afirmamos que $(\mathbb{R},\tau)$ es segundo numerable. Se tiene que $$S:=\{[q,r)\mid q,r\in\mathbb{Q}\}$$ es una base para $\tau$. En efecto, dado $[q,b)$ básico de $\tau$, $[q,b)$ se puede escribir como unión de elementos de $S$.
        Ahora, $(\mathbb{R},\tau)$ es regular, así que como $(\mathbb{R},\tau)$ es regular y segundo numerable, es metrizable; de donde, $(\mathbb{R},\tau)\times(\mathbb{R},\tau)$ también.

Extender endofuntores en $\mathbf{Con}$ a endofuntores oplaxos en $\mathbf{Rel}$

Leyendo sobre redes, de manera inesperada llegué al artículo Relational algebras, el cual me pareció muy interesante, pues en él se demuestran varios resultados con tal atributo. El primero que me gustó es el siguiente.
     Hay un funtor $L:\mathrm{Fun}(\mathbf{Con},\mathbf{Con})\rightarrow\mathrm{OpLFun}(\mathbf{Rel},\mathbf{Rel})$, el cual extiende los endofuntores en $\mathbf{Con}$ a endofuntores oplaxos en $\mathbf{Rel}$, donde $\mathrm{OpLFun}(\mathbf{Rel},\mathbf{Rel})$ es la categoría cuyos objetos son los funtores oplaxos $F:\mathbf{Rel}\rightarrow\mathbf{Rel}$ y cuyas flechas son las transformaciones laxas entre estos. Enseguida hago un recuento detallado del asunto.

Observación 1. Toda relación $r:X\rightarrow Y$ se puede factorizar como $$\require{AMScd} \begin{CD} X @>dr^\circ >> G_r @>cr >> Y, \end{CD}$$ donde $G_r$ es la gráfica de $r$, $dr:=p_X\mid_{G_r}$ y $cr:=p_Y\mid_{G_r}$, con $p_X$ y $p_Y$ las proyecciones del producto $X\times Y$. Lo que hace $(-)^\circ$ es darnos la relación recíproca.

Definición. Decimos que una relación $r:X\rightarrow Y$ es epi, mono, está definida en todas partes o es una función parcial si $cr$ es epi, $cr$ es mono, $dr$ es epi o $dr$ es mono, respectivamente.

Observación 2. El siguiente diagrama de funciones conmuta $$\begin{equation} \require{AMScd} \begin{CD} X @>v>> Y\\ @VuVV @VVgV\\ Z @>>f> A, \end{CD} \end{equation}$$ si y sólo si $u\cdot v^\circ\subseteq f^\circ\cdot g$; en efecto, se tiene que $$u\cdot v^\circ=\{(vx,ux)\in Y\times Z\mid x\in X\}$$ y $$f^\circ\cdot g=\{(y,z)\in Y\times Z\mid gy=fz\}.$$ Nótese que $g^\circ\cdot f$ es la retrotracción (pullback) en $\mathbf{Con}$ de $f$ y $g$.
     Tenemos que (1) es una retrotracción débil si y sólo si $u\cdot v^\circ=f^\circ\cdot g$. En efecto, supóngase que (1) es retrotracción débil; entonces, $\exists\, s:g^\circ\cdot f\rightarrow X$ $$\require{AMScd} \begin{CD} Z @< p_Z << g^\circ\cdot f @>p_Y>> Y\\ @| @VVsV @|\\ Z @<< u < X @>>v> Y \end{CD}$$ conmuta, donde $p_Z:g^\circ\cdot f\rightarrow Z$ y $p_Y:g^\circ\cdot f\rightarrow Y$ son las proyecciones de la retrotracción $\mathrm{Rt}(f,g)=g^\circ\cdot f$ de $f$ y $g$: $$\require{AMScd} \begin{CD} g^\circ\cdot f @>p_Y>> Y\\ @Vp_ZVV @VVgV\\ Z @>>f> A. \end{CD}$$ Por otro lado, $\exists!\,t:X\rightarrow g^\circ\cdot f$ $$\require{AMScd} \begin{CD} Z @< u << X @>v>> Y\\ @| @VVtV @|\\ Z @<< p_Z < g^\circ\cdot f @>>p_Y> Y \end{CD}$$ conmuta. Por la propiedad universal de $g^\circ\cdot f$, se tiene que $ts=1$; de donde, $t$ es epi. De aquí, $u\cdot v^\circ=f^\circ\cdot g$.
     Recíprocamente, supóngase que $u\cdot v^\circ=f^\circ\cdot g$. Sea $$\require{AMScd} \begin{CD} B @>s>> Y\\ @VrVV @VVgV\\ Z @>>f> A \end{CD}$$ un diagrama conmutativo en $\mathbf{Con}$ y sea $b\in B$; entonces, como $r\cdot s^\circ\subseteq f^\circ\cdot g=u\cdot v^\circ\;$, $\exists\,x_b\in X\;\;(sb,rb)=(vx_b,ux_b)$. Defínase entonces $t:B\rightarrow X$ como $tb:=x_b$ para todo $b\in B$. Claramente, $t$ hace conmutar el diagrama $$\require{AMScd} \begin{CD} Z @< r << B @>s>> Y\\ @| @VVtV @|\\ Z @<< u < X @>>v> Y. \end{CD}$$ Proposición 1. Para toda relación $r:X\rightarrow Y$

1. $r$ es epi $\Leftrightarrow\; r\cdot r^\circ\supseteq \Delta_Y,$
2. $r$ es mono $\Leftrightarrow\; r^\circ\cdot r\subseteq \Delta_X,$
3. $r$ está definida en todas partes $\Leftrightarrow\; r^\circ\cdot r\supseteq \Delta_X,$
4. $r$ es función parcial $\Leftrightarrow\; r\cdot r^\circ\subseteq \Delta_Y,$
5. $r$ es función $\Leftrightarrow\; r^\circ\cdot r\supseteq \Delta_X\;$ y $\; r\cdot r^\circ\subseteq \Delta_Y$.

Observación 3. $\mathbf{Rel}$ es una categoría 2: sus homoconjuntos $\mathbf{Rel}(X,Y)$ están parcialmente ordenados, y la composición es compatible con el orden; es decir, si $$\require{AMScd} \begin{CD} Z @= Z\\ @Ar'AA{\leq} @AAs'A\\ Y @= Y\\ @ArAA{\leq} @AAsA\\ X @= X \end{CD}$$ entonces $$\require{AMScd} \begin{CD} Z @= Z\\ @Ar'\cdot rAA{\leq} @AAs'\cdot sA\\ X @= X \end{CD}$$ (aquí estoy escribiendo verticalmente la composición horizontal de celdas 2). Tal compatibilidad nos dice cómo definir la composición horizontal de celdas 2. Es claro que tal composición es asociativa y funtorial.

Observación 4. Si se tiene el diagrama de funciones $$\begin{equation} \require{AMScd} \begin{CD} A @>u>> Y\\ @VvVV @AAgA\\ X @<< f < Z \end{CD} \end{equation}$$ entonces $g\cdot f^\circ\subseteq u\cdot v^\circ\;\Leftrightarrow\;\exists\,h:Z\rightarrow A\;\;$ el diagrama (2) conmuta. Simplemente notemos que $$g\cdot f^\circ=\{(fz,gz)\in X\times Y\mid z\in Z\}$$ y que $$u\cdot v^\circ=\{(va,ua)\in X\times Y\mid a\in A\}.$$ Es claro que $g\cdot f^\circ=u\cdot v^\circ\;\Leftrightarrow\;$ $h$ es epi.

Proposición 2. Dados $X\in\mathbf{Con}$, $T:\mathbf{Con}\rightarrow\mathbf{Con}$ funtor y $\alpha:T\Rightarrow S:\mathbf{Con}\rightarrow\mathbf{Con}$ transformación natural, defínase $LTX:=TX$, $LT:\mathbf{Rel}\rightarrow\mathbf{Rel}$ como $LTr:=Tg\cdot Tf^\circ$, donde $r=g\cdot f^\circ$ es una factorización en funciones de $r$, y $L\alpha:=\alpha$. Entonces $LT$ es un funtor oplaxo y $L$ es un funtor $\mathrm{Fun}(\mathbf{Con},\mathbf{Con})\rightarrow\mathrm{OpLFun}(\mathbf{Rel},\mathbf{Rel})$.

Demostración. Notemos que $LT(r^\circ)=(LTr)^\circ$, así que denotemos a cualquiera de estos dos como $LTr^\circ$.
     Demostremos primero que $LT$ está bien definido. Sea $r:X\rightarrow Y$ una relación y $u\cdot v^\circ=r$ otra factorización en funciones de $r$; entonces, $u\cdot v^\circ=cr\cdot dr^\circ$; de la Observación 4 y del hecho de que $T$ preserva epis (pues todo epi en $\mathbf{Con}$ es epi escindido), $Tu\cdot Tv^\circ=Tcr\cdot Tdr^\circ$.
     Ahora, que $LT$ sea oplaxo significa que dados $X\in\mathbf{Con}$ y $r,s$ relaciones, $LT\Delta_X\subseteq\Delta_{LTX}$, $r\subseteq s\Rightarrow LTr\subseteq LTs$ y $LT(s\cdot r)\subseteq LTs\cdot LTr$.
     Sea $X\in\mathbf{Con}$; entonces $\Delta_X=1_X\cdot 1_X^\circ$, así que, por la Observación 4, $$LT\Delta_X=1_{TX}\cdot 1_{TX}^\circ=\Delta_{TX}=\Delta_{LTX}.$$      Sean $r,s:X\rightarrow Y$ relaciones y supóngase que $r\subseteq s$. Entonces, tenemos el siguiente diagrama conmutativo: $$\require{AMScd} \begin{CD} X @< ds << G_s @>cs>> Y\\ @| @AAiA @|\\ X @<< dr < G_r @>>cr> Y, \end{CD}$$ donde $i$ es la inclusión. Si aplicamos $T$, obtenemos un diagrama conmutativo igual al anterior, salvo que aparece una $T$ delante de cada cosa; luego, por la Observación 4, $$LTr=Tcr\cdot Tdr^\circ\subseteq Tcs\cdot Tds^\circ=LTs.$$      Sean $r,s$ relaciones tales que $$\require{AMScd} \begin{CD} X @>r>> Y @>s>> Z; \end{CD}$$ entonces, $s\cdot r=cs\cdot ds^\circ\cdot cr\cdot dr^\circ$. Por la Observación 1, la relación $ds^\circ\cdot cr:G_r\rightarrow G_s$ se puede factorizar en funciones como $ds^\circ\cdot cr=p\cdot q^\circ$. De la observación 2, tenemos que el siguiente diagrama es una retrotracción débil: $$\require{AMScd} \begin{CD} \bullet @>q>> G_r\\ @VpVV @VVcrV\\ G_s @>>ds> Y; \end{CD}$$ así que al aplicar $T$ al diagrama anterior, funtor que quizá no preserva retrotracciones débiles, obtenemos, por lo menos, un diagrama conmutativo; luego, por la Observación 2, $Tp\cdot Tq^\circ\subseteq Tds^\circ\cdot Tcr$. Por otro lado, como $\mathbf{Rel}$ es una categoría 2, $$Tcs\cdot Tp\cdot Tq^\circ\cdot Tdr^\circ\subseteq Tcs\cdot Tds^\circ\cdot Tcr\cdot Tdr^\circ.$$ El lado izquierdo en la inclusión es $LT(s\cdot r)$ y el lado derecho es $LTs\cdot LTr$. (Que $Tcs\cdot Tp=T(cs\cdot p)$ considerando a $Tcs, Tp$ y $T(cs\cdot p)$ como relaciones, se sigue del hecho de que si $h=g\cdot f$ como funciones entonces $h=g\cdot f$ como relaciones).
     Finalmente veamos que $L\alpha$ es una transformación laxa $LT\Rightarrow LS$. Sea $r:X\rightarrow Y$ una relación. Entonces, de la naturalidad de $\alpha$, el diagrama $$\require{AMScd} \begin{CD} TG_r @>Tdr>> TX\\ @V\alpha G_rVV @VV\alpha XV\\ SG_r @>>Sdr> SX \end{CD}$$ conmuta. Por la Observación 2, $\alpha G_r\cdot Tdr^\circ\subseteq Sdr^\circ\cdot\alpha X$; de aquí, como $\mathbf{Rel}$ es categoría 2, $$Scr\cdot\alpha G_r\cdot Tdr^\circ\subseteq Scr\cdot Sdr^\circ\cdot\alpha X.$$ Como $\alpha Y\cdot Tcr=Scr\cdot\alpha G_r$ (por la naturalidad de $\alpha$), $$\alpha Y\cdot Tcr\cdot Tdr^\circ\subseteq Scr\cdot Sdr^\circ\cdot\alpha X;$$ es decir, $$\require{AMScd} \begin{CD} LTX @>L\alpha X>> LSX\\ @V LTr VV{\leq} @VV LSr V\\ LTY @>>L\alpha Y> LSY. \end{CD}$$      La funtorialidad de $L$ se sigue del hecho de que si $\beta:S\Rightarrow R:\mathbf{Con}\rightarrow\mathbf{Con}$ entonces $\beta\cdot\alpha(X)=\beta X\cdot\alpha X$ y de que $\mathbf{Rel}$ es categoría 2.

Observación 5. Sean $u,v,f,g$ funciones como en la Observación 2. Supóngase que el diagrama (1) conmuta y que $f$ es iso. Entonces, (1) es retrotracción débil si y sólo s $v$ es epi. En efecto, supóngase que $u\cdot v^\circ=f^\circ\cdot g$. Veamos que $v$ es epi. Sea $y\in Y$; entonces, $gy\in A$; luego, como $f$ es iso, $\exists !\, z\in Z\;\; gy=fz$; de aquí, $(y,z)\in f^\circ\cdot g$; por lo tanto, como $f^\circ\cdot g=u\cdot v^\circ,\,$ $\exists\,x\in X\;\; vx=y,\,ux=z$. Luego, $v$ es epi.
     Recíprocamente, supóngase que $v$ es epi. Veamos que $u\cdot v^\circ=f^\circ\cdot g$. Basta mostrar que $f^\circ\cdot g\subseteq u\cdot v^\circ$. Sea $(y,z)\in f^\circ\cdot g$; luego, $gy=fz$. Por otro lado, como $v$ es sobre, $\exists\,x\in X\;\;y=vx$. Finalmente, veamos que $ux=z$. Ya se tiene que $u\cdot v^\circ\subseteq f^\circ\cdot g$, así que $(vx,ux)\in f^\circ\cdot g$; de donde, $$fux=gvx=gy=fz,$$ pero $f$ es mono; luego, $z=ux$.

Corolario. Sean $T\in\mathrm{Fun}(\mathbf{Con},\mathbf{Con})$ y $X\overset{r}{\rightarrow}Y\overset{s}{\rightarrow}Z$ realciones. Si $s$ es función o $r$ es bimorfismo (epi y mono), entonces $LT(s\cdot r)=LTs\cdot LTr$.

Demostración. Si $s$ es función, entonces, por la Proposición 1, $ds$ es iso, y si $ds^\circ\cdot cr=p\cdot q^\circ$ como en la proposición anterior, entonces $q$ es epi, por la observación anterior. Como $T$ preserva epis e isos, $Tds$ es iso y $Tq$ es epi. Por otro lado, $$\require{AMScd} \begin{CD} \bullet @>Tq>> \bullet\\ @VTpVV @VVTcrV\\ \bullet @>>Tds> \bullet \end{CD}$$ conmuta; luego, por la observación anterior, $Tds^\circ\cdot Tcr=Tp\cdot Tq^\circ$, así que $LT(s\cdot r)=LTs\cdot LTr$.
     Si $r$ es bimorfismo, $cr$ es iso.

Un problema, una pregunta sin respuesta y rarezas de las redes

En el libro Elementary topology de Michael C. Gemignani, aparece un problema que me dejó pensando si hay algo que no estoy entendiendo o si Gemignani tergiversó algún resultado. El problema dice lo siguiente.

Suppose $X, D$ is a metric space and $\{s_i\},i\in I$, is a net in $X$.

1. Suppose $s_i\rightarrow x$. Prove that a subsequence of $\{s_i\}, i\in I$, converges to $x$.
2. Prove that if every subsequence of $\{s_i\}$ converges to $x$, then $s_i\rightarrow x$.
3. Prove a and b when it is merely assumed that $X,\tau$ is a first countable space.

El problema me desconcierta porque, dado un espacio topológico $(X,\sigma)$, siempre podemos encontrar una red¹ en $X$ sin subsucesiones; más aún, en $\mathbb{R}$ con su topología usual, podemos encontrar una red $\{r_i\}$ sin subsucesiones no convergente; de donde, podemos encontrar, en un métrico, una red no convergente de la cual toda subsucesión converge a un punto $m\in M$, por vacuidad.
     Demuestro mi primera afirmación. Sea $(Y,\tau)$ el espacio topológico con $Y:=\mathbb{R}^{\mathbb{R}}$ y $\tau$ la topología cuyos básicos son los $$U(f,F,p):=\{h\in Y\mid \forall\,x\in F\, |hx-fx|< p\},$$ donde $f\in Y$, $F$ es subconjunto finito de $\mathbb{R}$ y $p\in\mathbb{R}^+$. Dado $f\in Y$, $$T(Y,f):=\{V\in\tau\mid f\in V\}$$ es un conjunto dirigido con el orden $\leq$ dado por $U\leq V$ si y sólo si $V\subseteq U$. Tenemos que toda red $s:T(Y,\mathrm{const}\,0)\rightarrow X$ no tiene subsucesiones. En efecto, supóngase que $s\circ k$ es subsucesión de $s$; es decir, supongamos que $\forall\, U\in T(Y,\mathrm{const}\,0)\,\exists\,n\in\mathbb{N}\;\; k_n\subseteq U$. Sea $p\in\mathbb{R}^+$; entonces, $\forall\,x\in\mathbb{R}\,\exists\,m_x\in\mathbb{N}\;\;k_{m_x}\subseteq U(\mathrm{const}\,0,\{x\},p)$. Esto nos da una función $\alpha:\mathbb{R}\rightarrow\mathbb{N}$ dada por $\alpha x:=m_x$. Tenemos que $$\mathbb{R}=\bigcup_{n\in\mathbb{N}}\alpha^{-1}n;$$ de aquí, $\exists\,r\in\mathbb{N}\;\;|\alpha^{-1}r|=|\mathbb{R}|$; es decir, $\exists\,r\in\mathbb{N}\;\;k_r\subseteq U(\mathrm{const}\,0,\{x\},p)$ para todo $x\in\alpha^{-1}r=:S$, con $|S|=|\mathbb{R}|$. Luego, $k_r\subseteq\cap_{x\in S}U(\mathrm{const}\,0,\{x\},p)$. Por otro lado, como $k_r\in T(Y,\mathrm{const}\,0)\subseteq\tau\;$ y $\forall\,n\in\mathbb{N}\;\;k_n\neq\{\mathrm{conts}\,0\}$ (porque $\{\mathrm{conts}\,0\}$ no es abierto), dado $f\in k_r\setminus\{\mathrm{const}\,0\}$, $\exists\,F\subseteq\mathbb{R}$ finito y $\exists\,q\in\mathbb{R}^+\;\;U(f,F,q)\subseteq k_r$. Defínase $h:\mathbb{R}\rightarrow\mathbb{R}$ como $$hx:=\begin{cases} fx+\frac{q}{2}&\text{ si $x\in F$},\\ p+1&\text{ si $x\notin F$}. \end{cases}$$ Entonces, $h\in U(f,F,q)$ pero $h\notin\cap_{x\in S}U(\mathrm{const}\,0,\{x\},p)\;$!! Luego, $s$ no tiene subsucesiones.
     Así que toda subsucesión de $s$ satisface cualquier propiedad, puesto que un condicional es falso si y sólo si su antecedente es verdadero y su consecuente falso; en otras palabras, $\forall\,r\;\;(r\text{ es subsucesión de }s\Rightarrow Pr)$ es siempre verdadera, pues el predicado “subsucesión de $s$” corresponde a un conjunto vacío. Como cuando uno considera un espacio con más de un punto que tiene la topología trivial; dicho espacio es $\mathrm{T}_4$ porque no tiene subconjuntos cerrados no vacíos distintos de él mismo.
     Demuestro mi segunda afirmación. Definamos $s'':L\rightarrow\mathbb{R}$, donde $$L:=\{U(\mathrm{const}\,0,\{0,\ldots,n\},1)\mid n\in\mathbb{N}\},$$ como $s''U(\mathrm{const}\,0,\{0,\ldots,n\},1):=(-1)^n\,$ y $s':T(Y,\mathrm{const}\,0)\rightarrow L$ como $$s'V:=\begin{cases} U(\mathrm{const}\,0,\{0,\ldots,n\},1)&\text{si $V=U(\mathrm{const}\,0,\{0,\ldots,n\},1)$},\\ U(\mathrm{const}\,0,\{0\},1)&\text{si $V\notin L$}. \end{cases}$$ Entonces, $s:=s''\circ s':T(Y,\mathrm{const}\,0)\rightarrow\mathbb{R}$ no converge y tiene como punto límite a 1 pero no a -1; sin embargo, toda subsucesión de $s$ converge a 1 (o a cualquier otro real).
     Tratando de encontrar un resultado en el cual podría estar pensando Gemignani, hallé lo siguiente (en el Introduction to General Topology de K. D. Joshi): un espacio con una sucesión con un punto límite cuyas subsucesiones no convergen, y que si $X$ es un espacio primero numerable y $\{x_n\}$ es una sucesión en $X$ con punto límite $x$ entonces existe una subsucesión de $\{x_n\}$ que converge a $x$.
     El espacio de la sucesión con un punto límite cuyas subsucesiones no convergen es el siguiente. Consideremos a $\mathbb{N}\times\mathbb{N}$; dado $k\in\mathbb{N}$, al conjunto $\mathbb{N}\times\{k\}$ lo llamaremos el $k$-ésimo renglón de $\mathbb{N}\times\mathbb{N}$. Sea $\infty$ un símbolo que no está en $\mathbb{N}\times\mathbb{N}$ (por alguna razón poco misteriosa me estoy acordando de lo poco que leí sobre la teoría de conjuntos de Zermelo-Fraenkel con átomos; ZFA le llaman). Sean $Z:=(\mathbb{N}\times\mathbb{N})\cup\{\infty\}$, $S_1:=\mathcal{P}(\mathbb{N}\times\mathbb{N})$ y $S_2$ el conjunto de los $A\subseteq Z$ tales que $\infty\in A$ y $A$ contiene casi todos los puntos en casi todos los renglones; es decir, $\forall^\infty\,k\in\mathbb{N}\,\forall^\infty\,n\in\mathbb{N}\;\;(n,k)\in A$, (donde ‘$\forall^\infty$’ simboliza “para casi todo” significando “ para todo salvo un número finito”); dicho de otra manera, dado $A\in S_2$, existe un número finito de renglones $\mathbb{N}\times\{k\}$ de los cuales hay un número infinito de puntos de cada renglón $\mathbb{N}\times\{k\}$ que no contiene $A$, y para el resto de los renglones hay a lo más un número finito de puntos de cada uno de estos renglones que no contiene $A$ (no sé cómo podría poner esto con cuantificadores; por cierto, el dual de ‘$\forall^\infty$’ es ‘$\exists^\infty$’ “existe una cantidad infinita tal que”). Sea $\sigma:=S_1\cup S_2$; $\sigma$ es una topología sobre $Z$.
     Veamos que ninguna sucesión en $\mathbb{N}\times\mathbb{N}$ puede converger a $\infty$. Sea $\{x_n\}$ una sucesión en $\mathbb{N}\times\mathbb{N}$ tal que $x_n\rightarrow\infty$, así que $\forall\,A\in T(Z,\infty)\exists\,n\in\mathbb{N}\,\forall\,m\in\mathbb{N}\;\;(n\leq m\Rightarrow x_m\in A)$. De aquí, no puede ser que haya un renglón de $\mathbb{N}\times\mathbb{N}$ que contenga una cantidad infinita de términos de $\{x_n\}$, pues si así fuera, podríamos obtener un $A\in T(Z,\infty)$ tal que $x_n\notin A$ para una infinidad de términos de $\{x_n\}$. Así que todo renglón de $\mathbb{N}\times\mathbb{N}$ tiene a lo más un número finito de términos de $\{x_n\}$. Si quitamos de cada renglón esos términos de $\{x_n\}$, obtenemos un abierto $B\in T(Z,\infty)$ que no contiene a ningún término de $\{x_n\}$ !! Así que una sucesión converge a un punto en $(Z,\sigma)$ si y sólo si es eventualmente constante.
     Ahora, sea $z:\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$ una biyección. Entonces, $\infty$ es punto límite de $\{z_n\}$; es decir, $\forall\, A\in T(Z,\infty)\,\forall\,n\in\mathbb{N}\,\exists\,m\in\mathbb{N}\;\;m\geq n\;\text{y}\;x_m\in A$. En efecto, dado $n\in\mathbb{N}$ y dado $A\in T(Z,\infty)$, no puede ser que $\forall\,m\geq n\;\;x_m\notin A$, puesto que $z(\mathbb{N})=\mathbb{N}\times\mathbb{N}$, así que debe existir un $m\geq n$ tal que $x_m\in A$. Ninguna subsucesión de $\{z_n\}$ converge a $\infty$.
     Quizá Gemignani estaba pensando en el segundo resultado que encontré (el cual es fácil de demostrar): ocurre en los métricos, pues son primero numebrales. No lo sé.

---

1. Una red $\{s_i\}_{i\in I}$ en un espacio $(X,\sigma)$ es una función $s:I\rightarrow X$ cuyo dominio $I$ es un conjunto dirigido.
     Sea $J$ un conjunto dirigido y $k:J\rightarrow I$ una función tal que

1. $k$ es monótona,
2. $\forall\,i\in I\,\exists\,j\in J\;\;i\leq k(j)$.

Se dice que la composición $s\circ k:J\rightarrow X$ es una subred de $s$. En particular, si $J=\mathbb{N}$, se dice que $s\circ k$ es una subsucesión de $s$.↩