Conjuntos 1

Este curso está dividido en dos partes. Una parte clásica, donde se estudiara la teoría de conjuntos de Zermelo-Fraenkel. La otra parte será una introducción a la categoría de conjuntos abstractos de Lawvere (y de cierta forma, de Cantor).

En esta página se irán agregando notas acerca de las clases

La categoría de conjuntos abstractos

Semana 1

Clases 1 y 2

La definición más básica para poder dar la categoría de conjuntos abstractos es la de categoría.

Definición

Una categoría consta de:

• Una colección de objetos, denotados \(A\), \(B\), \(C\), \ldots
• Una colección de flechas, denotadas \(f\), \(g\), \(h\), \ldots
• Para cada flecha \(f\), un par de objetos \(\text{dom}(f)\) y \(\text{cod}(f)\). De esta forma, si \(\text{dom}(f)=A\) y \(\text{cod}(f)=B\), escribimos \(f\colon A\to B\).
• Para cada objeto \(A\), una flecha identidad \(\text{id}_A\colon A\to A\).
• Para cada par de flechas \(f\colon A\to B\) y \(g\colon B\to C\), una composición \(gf\colon A\to C\).

Esta información debe satisfacer los siguientes axiomas:

• La composición es asociativa, \(h(gf)=(hg)f\), y
• Las identidades son neutras, \(f\text{id}_A=f=\text{id}_Bf\).

Un tipo especial de objeto, que sirvió cómo motivación para la definición de categoría es el terminal.

Definición

Un objeto \(1\) en una categoría \(\mathbf{A}\) es terminal si para cada objeto \(A\) en \(\mathbf{A}\) existe una única flecha \(f\colon A\to 1\).

Recordemos que la notación para la única flecha hacia el terminal es \(!_A\).

Finalmente, notamos que los conjuntos abstractos podrían ser conjuntos variables y, para que se comporten como los conjunto usuales, agregamos algo para detener la variación.

Definición

Un objeto \(S\) en una categoría \(\mathbf{A}\) es un separador si para cualesquiera dos flechas \(f,g\colon A\to B\), si se satisface que para toda \(x\colon S\to A\) se tiene que \(fx=gx\), entonces \(f=g\).

Denotamos con \(\mathcal{S}\) a la colección de conjuntos abstractos y flechas entre ellos. Hasta este momento tenemos los siguientes axiomas para \(\mathcal{S}\):

1. \(\mathcal{S}\) es una categoría.
2. \(\mathcal{S}\) tiene un objeto terminal \(1\).
3. El objeto terminal \(1\) es un separador en \(\mathcal{S}\).

Semana 2

Clase 3

Empezamos con la definición de isomorfismo.

Definición

Sean \(A\) y \(B\) en \(\mathbf{A}\). Una flecha \(f\colon A\to B\) es un iso(morfismo) si existe una flecha \(g\colon B\to A\) tal que \(gf=\text{id}_A\) y \(fg=\text{id}_B\). En este caso, decimos que \(A\) y \(B\) son isomorfos y escribimos \(A\cong B\).

Un isomorfismo en \(\mathbf{Con}\) es una biyección. En una categoría generada por un orden parcial, un isomorfismo es una igualdad.

Proposición

En una categoría arbitraria, el objeto terminal es único salvo isomorfismo.

Demostración

Supongamos que \(1\) y \(1'\) son objetos terminales. Entonces, por definición, existen flechas \(!_1\colon 1\to 1'\) y \(!_{1'}\colon 1'\to 1\). Además, como \(1\) es terminal, existe una única flecha \(\text{id}_1\colon 1\to 1\). Así, \(!_{1'}\,!_1=\text{id}_1\). De forma análoga, \(!_1\,!_{1'}=\text{id}_{1'}\). Por lo tanto, \(1\cong 1'\).

De forma análoga a lo que hemos visto con el objeto terminal, podemos definir el objeto inicial. Este tendrá ejemplos y propiedades análogas a las del terminal.

Definición

Un objeto \(0\) en una categoría \(\mathbf{A}\) es inicial si para cada objeto \(A\) en \(\mathbf{A}\) existe una única flecha \(f\colon 0\to A\).

La notación para la única flecha desde el inicial es \(!_A\). No habrá confusión con la del objeto terminal ya que siempre se especificaran dominios y codominios.

Es fácil ver que \(\emptyset\) es un objeto inicial en \(\mathbf{Con}\). Si \(\mathbf{P}\) es la categoría generada por el orden parcial \(\langle P,\leq\rangle\), entonces \(\mathbf{P}\) tiene un objeto inicial si y sólo si \(P\) tiene mínimo.

Un ejemplo de categoría diferente a las que hemos estado usando es la categoría de espacios verctoriales sobre un campo \(k\). Los objetos de esta categoría son espacios vectoriales y las flechas son transformaciones lineales. En esta categoría el espacio vectorial trivial, \(\{0\}\), es un objeto tanto inicial como terminal.

Axioma 3

\(\mathcal{S}\) tiene un objeto inicial \(0\) y \(0\not\cong 1\).

Aunque tenemos pocos axiomas, ya podemos demostrar que el inicial en \(\mathcal{S}\) se parece al vacío.

Proposición

En \(\mathcal{S}\), el objeto inicial \(0\) no tiene elementos globales.

Demostración

Supongamos que \(0\) tiene un elemento global, digamos \(x\colon 1\to 0\). Como \(0\) es inicial, existe una única flecha \(!_1\colon 0\to 1\). Luego, si usamos que \(0\) es inicial y \(1\) es terminal, tenemos que \(x\,!_1=\text{id}_1\) y \(!_1\,x=\text{id}_0\). Así, \(1\cong 0\), lo cual es una contradicción.

Finalmente, vimos la definición de inyectividad y suprayectividad en una categoría con objeto terminal.

Definición

• Una flecha \(f\colon A\to B\) es inyectiva si para cualquier elemento global \(b\colon 1\to B\) existe a lo más un elemento global \(a\colon 1\to A\) tal que \(fa=b\).
• \(f\colon A\to B\) es suprayectiva si para todo \(b\colon 1\to B\) existe un \(a\colon 1\to A\) tal que \(fa=b\).
• \(f\colon A\to B\) es biyectiva si es inyectiva y suprayectiva.

Proposición

\(f\colon A\to B\) es inyectiva si y sólo si para cualesquiera dos elementos globales \(a_1,a_2\colon 1\to A\) se tiene que \(fa_1=fa_2\) implica \(a_1=a_2\).

Clase 4

En esta clase necesitamos la definición de mono(morfismo) y epi(morfismo).

Definición

Sea \(f\colon A\to B\) en \(\mathbf{A}\). Decimos que \(f\) es un

• monomorfismo si para cualesquiera dos flechas \(x,y\colon T\to A\) se tiene que \(fx=fy\) implica \(x=y\).
• epimorfismo si para cualesquiera dos flechas \(g,h\colon B\to C\) se tiene que \(gf=hf\) implica \(g=h\).

Luego, vimos cómo son este tipo de flechas en \(\mathbf{Con}\). De hecho, vimos que si aceptamos un principio más, entonces las demostraciones se pueden hacer en \(\mathcal{S}\).

Proposición

En \(\mathbf{Con}\), una flecha \(f\colon A\to B\) es un mono si y sólo si es inyectiva.

Luego, para enunciar el principio que nos falta necesitamos dos conceptos más.

Definición

Sean \(r\colon A\to B\) y \(s\colon B\to A\) en \(\mathbf{A}\). Si se satisface que \(rs=\text{id}_B\), entonces decimos que \(r\) es una retracción (de \(s\)) y que \(s\) es una sección (de \(r\)).

Ahora sí, el principio que nos falta.

Axioma 4 (axioma de elección)

En \(\mathcal{S}\), todo epi tiene una sección.

Proposición

En \(\mathbf{Con}\), una flecha \(f\colon A\to B\) es un epi si y sólo si es suprayectiva.

Semana 3

Clase 5

En esta clase definimos pertenencia y contensión en \(\mathcal{S}\). Algo importante que hay que notar es que estas nociones no son exactamente las mismas que en conjuntos usuales. Por ejemplo, ninguna de ellas es global y admiten propiedades que no satisfacen los conjunto usuales.

Antes de las definiciones importantes definimos un subobjeto de \(A\) como un mono de la forma \(m\colon S\to A\).

Definición

Sean \(x\colon X\to A\) y \(m\colon S\to A\). Decimos que \(x\) pertenece a \(m\) según \(A\), y lo denotamos \(x\in_A m\), si existe \(h\colon X\to S\) tal que \(mh=x\).

\[\begin{CD} X @>h>> S\\ @VxVV @VVmV\\ A @= A \end{CD}\]

Definición

Sean \(m\colon S\to A\) y \(n\colon T\to A\). Decimos que \(m\) está contenido en \(n\) según \(A\), y lo denotamos \(m\subseteq_A n\), si existe \(h\colon S\to T\) tal que \(nh=m\).

\[\begin{CD} S @>h>> T\\ @VmVV @VVnV\\ A @= A \end{CD}\]

Observamos que en ambas definiciones, de existir la flecha \(h\), esta es única. Además, en la definición de contensión, mostramos que \(h\) es mono.

Proposición

Sean \(m\colon S\to A\) y \(n\colon T\to A\).

1. \(m\in_A m\).
2. \(n\in_A m\) si y sólo si \(n\subseteq_A m\).
3. \(n\subseteq_A m\) si y sólo si para todo \(x\colon X\to A\) se tiene que \(x\in_A n\) implica \(x\in_A m\).

Clase 6

La definición principal de esta clase fue la de producto fibrado.

Definición

Sean \(f\colon A\to B\) y \(g\colon A\to C\) en \(\mathbf{A}\). Un producto fibrado de \(g\) a lo largo de \(f\) es un objeto \(P\) y dos flechas que hacen conmutar al siguiente diagrama:

\[\begin{CD} P @>p_B>> B\\ @Vp_AVV @VVgV\\ A @>>f> C \end{CD}\]

Además, si \(X\) es otro objeto con flechas \(x_B\colon X\to B\) y \(x_A\colon X\to A\) que hacen conmutar a

\[\begin{CD} X @>x_B>> B\\ @Vx_AVV @VVgV\\ A @>>f> C \end{CD}\]

entonces existe una única flecha \(h\colon X\to P\) tal que \(p_Bh=x_B\) y \(p_Ah=x_A\).

Vimos que, en \(\mathbf{Con}\), el producto fibrado de \(g\) a lo largo de \(f\) es el conjunto

junto con las proyecciones a cada entrada.

Como queremos que la categoría de conjuntos abstractos se parezca a la de conjuntos usuales, necesitamos pedir la existencia de productos fibrados.

Axioma 5

\(\mathcal{S}\) tiene productos fibrados.

Luego, queremos al producto fibrado para hacer algunas construcciones. Por ejemplo, podemos definir la imagen inversa como sigue.

Definición

Sean \(f\colon A\to B\) e \(n\colon T\rightarrowtail B\). La imagen inversa de \(n\) bajo \(f\) es el producto fibrado de \(n\) a lo largo de \(f\).

\[\begin{CD} f^{-1}n @>>> T\\ @VVV @VVnV\\ A @>>f> B \end{CD}\]

Clase 7

Lo primero que deberíamos revisar en la definición de imagen inversa es que esta nos da un subobjeto de \(A\).

Proposición

Con la notación de la definición de producto fibrado, si \(g\) es mono, entonces \(p_A\) es mono.

Ahora, podemos ver que nuestra definición satisface lo mismo que la imagen inversa en conjunto usuales.

Proposición

Sean \(f\colon A\to B\) e \(n\colon T\rightarrowtail B\). Para cualquier elemento generalizado \(x\colon X\to A\), se tiene que \(x\in_A p_A\) si y sólo si \(fx\in_B n\).

Así como la imagen inversa es un caso particular de un producto fibrado, la intersección es un caso particular de imagen inversa.

Definición

Sean \(m\colon S\rightarrowtail A\) y \(n\colon T\rightarrowtail A\). La intersección de \(m\) y \(n\) es el subobjeto de \(A\) dado por la imagen inversa de \(n\) bajo \(m\).

\[\begin{CD} S\cap T @>>> T\\ @VVV @VVnV\\ S @>>m> A \end{CD}\]

Como la composición de monos es un mono, entonces la intersección es un subobjeto de \(A\). Así, la intersección de los subobjetos \(m\) y \(n\) de arriba será denotada \(m\cap n\colon S\cap T\rightarrowtail A\).

De nuevo vimos que la intersección satisface lo que esperamos de ella.

Proposición

Sean \(m\colon S\rightarrowtail A\) y \(n\colon T\rightarrowtail A\). Para cualquier elemento generalizado \(x\colon X\to A\), se tiene que \(x\in_A m\cap n\) si y sólo si \(x\in_A m\) y \(x\in_A n\).

Finalmente vimos la definición de clasificador de subobjetos. Seguimos lo que pasa en conjuntos usuales con el conjunto \(2=\{0,1\}\). Este conjunto sirve como un conjunto de valores de verdad y puede ser usado para representar subconjuntos por medio de funciones características.

Semana 4

Clase 8

En esta clase vimos la definición de clasificador de subobjetos.

Definición

Un clasificador de subobjetos en \(\mathbf{A}\) es un objeto \(\Omega\) y una flecha \(v\colon 1\to\Omega\) tal que para cualquier subobjeto \(m\colon S\rightarrowtail A\) existe una única flecha \(\chi_m\colon A\to\Omega\) tal que el siguiente diagrama es un producto fibrado.

\[\begin{CD} S @>>> 1\\ @VmVV @VVvV\\ A @>>\chi_m> \Omega \end{CD}\]

Esta definición sigue lo que satisface el conjunto \(2\) en conjuntos usuales. Además, vimos que el clasificador de subobjetos es único salvo isomorfismo.

Proposición

Si \(v\colon 1\to\Omega\) y \(v'\colon 1\to\Omega'\) son clasificadores de subobjetos en \(\mathbf{A}\), entonces \(\Omega\cong\Omega'\).

Clase 9

Para demostrar que el clasificado de subobjetos es único salvo isomorfismo, es necesario usar un resultado acerca de productos fibrados.

Lema del producto fibrado

Consideremos el diagrama conmutativo \eqref{eq:lpf}. Si los dos cuadrados son productos fibrados, entonces el rectángulo también es un producto fibrado. Además, si el rectángulo y el cuadrado de la derecha son productos fibrados, entonces el cuadrado de la izquierda también es un producto fibrado. \(\begin{equation}\label{eq:lpf} \begin{CD} \bullet @>>> \bullet @>>> \bullet\\ @VVV @VVV @VVV\\ \bullet @>>> \bullet @>>> \bullet\\ \end{CD} \end{equation}\)

Semana 5

Clases 10 y 11

En estas clases vimos algunas construcciones y propiedades con el clasificador de subobjetos. La primera, y la razón por la cual necesitamos el lema del producto fibrado es la siguiente.

Proposición

El clasificador de subobjetos es único salvo iso.

Como habíamos comentado, una flecha de la forma \(A\to\Omega\) se puede interpretar como una propiedad de “elementos” de \(A\). Una de las propiedades que estaremos usando es la que es verdadera en todos los elementos de \(A\). Esta es una flecha \(v_A\colon A\to\Omega\) definida como la siguiente composición

Lo siguiente que necesitamos para hacer la construcción que queremos es la diagonal del producto \(A\times A\). En conjuntos sabemos como es,

Este conjunto se puede ver como la imagen de la función \(\Delta_A\colon A\to A\times A\) definida por \(a\mapsto(a,a)\). Finalmente, esta función satisface que al componerla con las proyecciones se obtiene la identidad en \(A\). Así, la diagonal se define mediante la propiedad universal del producto, como en el siguiente diagrama. (Escrito aquí usando cuadrados en lugar de triángulos ya que TiKzJax dejó de funcionar en esta página y amscd sólo soporta cuadrados.)

Una observación acerca de la flecha diagonal es que esta es mono.

Proposición

La diagonal \(\Delta_A\colon A\to A\times A\) es mono.

Ahora podemos usar al clasificador de subobjetos para obtener la característica de la diagonal. Esto es, consideramos el siguiente producto fibrado,

Finalmente, mostramos que \(=_A\) es de verdad el predicado de igualdad en \(A\). Un predicado con dos variables libres del mismo tipo.

Proposición

Sean \(x,y\colon X\to A\). Sucede que \(=A(x,y)=v_X\) si y sólo si \(x=y\).

Semana 6

Clases 12 y 13

En esta clase vimos definimos una relación entre subobjetos y vimos algunas equivalencias.

Proposición

Sean \(m\colon S\rightarrowtail A\) y \(n\colon T\rightarrowtail A\). Sean \(\chi_m\colon A\to\Omega\) y \(\chi_n\colon A\to\Omega\) las flechas características de \(m\) y \(n\), respectivamente. Los siguientes enunciados son equivalentes:

1. \(m\subseteq_A n\) y \(n\subseteq_A m\).
2. Existen \(h\colon S\to T\) y \(k\colon T\to S\) tales que \(nh=m\), \(mk=n\) y son inversas, es decir, \(hk=\text{id}_T\) y \(kh=\text{id}_S\).
3. \(\chi_m=\chi_n\).

Luego, escogimos una de las propiedades de la proposición anterior para definir cuando dos subobjetos son equivalentes.

Definición

Sean \(m\colon S\rightarrowtail A\) y \(n\colon T\rightarrowtail A\). Decimos que \(m\) y \(n\) son equivalentes si \(m\subseteq_A n\) y \(n\subseteq_A m\).

La notación que usamos para la equivalencia de subobjetos es \(m\sim_A n\). No es difícil ver que la relación \(\sim_A\) es de equivalencia.

Como dice en el punto 2 de la proposición anterior, cuando consideramos clases de equivalencia de subobjetos, estas pueden verse como subobjetos salvo iso.

Definición

$$\text{Sub}(A)={m\colon S\rightarrowtail A\mid S\text{ subobjeto de }A}/\sim_A.

Con esto podemos demostrar que, en efecto, el clasificador de subobjetos puede representar a los subobjetos de un objeto.

Proposición

\(\mathcal{S}(A,\Omega)\cong\text{Sub}(A)\).

Finalmente, vimos una forma de construir la conjunción \(\land\colon\Omega\times\Omega\to\Omega\). La idea para decir cómo se comporta esta flecha es como sigue. Sean \(\varphi,\psi\colon A\to\Omega\). Diremos cual es el resultado de hacer la composición \(\land(\varphi,\psi)\), que denotamos \(\varphi\land\psi\). Primero tomamos los subobjetos caracterizados por \(\varphi\) y \(\psi\), digamos \(m\) y \(n\). Luego, tomamos la intersección de estos subobjetos, \(m\cap n\). Finalmente, la flecha característica de la intersección será el resultado de la composición.

Semana 7

Para formalizar la construcción de la conjunción, necesitamos de algunos resultados técnicos. En esta semana haremos un paréntesis para ver estos resultados.

Clase 14

Empezamos este paréntesis con la definición de funtor.

Definición

Un funtor covariante \(F\colon\mathbf{A}\to\mathbf{B}\) entre dos categorías consta de dos asignaciones \(F_0\colon\text{Obj}(\mathbf{A})\to\text{Obj}(\mathbf{B})\) y \(F_1\colon\text{Fl}(\mathbf{A})\to\text{Fl}(\mathbf{B})\) que satisfacen las siguientes propiedades:

1. \(\text{dom}(F_1(f))=F_0(\text{dom}(f))\),
2. \(\text{cod}(F_1(f))=F_0(\text{cod}(f))\),
3. \(F_1(\text{id}_A)=\text{id}_{F_0(A)}\), y
4. \(F_1(gf)=F_1(g)F_1(f)\).

No es usual distinguir las dos asignaciones que conforman un funtor, así que seguiremos la notación usual y denotaremos a ambas con \(F\).

Además de los funtores covariantes también existen los funtores contravariantes. Para definir estos últimos necesitamos la noción de categoría opuesta.

Definición

La categoría opuesta de una categoría \(\mathbf{A}\), denotada \(\mathbf{A}^{\text{op}}\), consta de los mismos objetos que \(\mathbf{A}\) y las mismas flechas, pero con el sentido inverso. Esto es, hay una flecha \(A\to B\) en \(\mathbf{A}^{\text{op}}\) si y sólo si hay una flecha \(B\to A\) en \(\mathbf{A}\).

Definición

Un funtor contravariante \(F\colon\mathbf{A}\to\mathbf{B}\) es un funtor covariante \(F\colon\mathbf{A}^{\text{op}}\to\mathbf{B}\).

Es posible describir a un funtor contravariante en términos de la categoría \(\mathbf{A}\). Para esto simplemente se cambia el sentido de las flechas, es decir, una flecha \(f\colon A\to B\) en \(\mathbf{A}\) va a una flecha de la forma \(F(f)\colon F(B)\to F(A)\) en \(\mathbf{B}\). Hay que observar que la condición anterior nos obliga a cambiar el orden en las composiciones.

Luego, definimos transformación natural.

Definición

Sean \(F,G\colon\mathbf{A}\to\mathbf{B}\) funtores. Una transformación natural \(\tau\colon F\to G\) es una familia de flechas \(\tau_A\colon FA\to GA\), una para cada \(A\in\mathbf{A}\) que satisfacen que para cada flecha \(a\colon A\to A'\) en \(\mathbf{A}\), el siguiente diagrama conmuta.

\[\begin{CD} FA @>\tau_A>> GA\\ @V{Fa}VV @VV{Ga}V\\ FA' @>>\tau_{A'}> GA' \end{CD}\]

Observamos que la composición de transformaciones naturales es una transformación natural, que esta composición es asociativa y que tiene neutros. Así, es posible considerar a los funtores y transformaciones naturales como una categoría.

Definición

Sean \(\mathbf{A}\) y \(\mathbf{B}\) categorías. La categoría de funtores entre \(\mathbf{A}\) y \(\mathbf{B}\), denotada \(\mathbf{B}^{\mathbf{A}}\), tiene como objetos a los funtores entre \(\mathbf{A}\) y \(\mathbf{B}\) y como flechas a las transformaciones naturales entre estos funtores.

Finalmente, la razón por la que vimos funtor y transformación natural es que necesitamos una categoría de funtores especial.

Definición

Sea \(\mathbf{A}\) una categoría. La categoría de pregavillas de \(\mathbf{A}\) es la categoría de funtores \(\textbf{Con}^{\mathbf{A}^{\text{op}}}\).

Clase 15

En esta clase vimos un tipo especial de pregavilla, la representable.

Definición

Dado un objeto \(A\in\mathbf{A}\), la pregavilla representable, representada por \(A\), es el funtor \(\mathbf{A}(-,A)\colon\mathbf{A}^{\text{op}}\to\mathbf{Con}\).

Ahora podemos enunciar uno de los pendientes que quedó en la construcción de la conjunción de la siguiente forma:

Proposición

Sea \(A\), \(B\) y \(C\) objetos de \(\mathbf{A}\). Sucede que \(\mathbf{A}(A,B)\times\mathbf{A}(A,C)\cong\mathbf{A}(A,B\times C)\).

Clase 16

En esta clase demostramos el lema de Grothendieck-Yoneda y vimos un corolario de él.

Lema de Grothendieck-Yoneda

Sean \(\mathbf{A}\) una categoría pequeña, \(A\) un objeto de \(\mathbf{A}\) y \(P\) una pregavilla. Sucede que hay una biyección (natural)

\(\text{Nat}(\mathbf(-,A),P)\cong P(A)\).

El funtor de Grothendieck-Yoneda es de la forma \(\mathbf{A}\to\textbf{Con}^{\mathbf{A}^{\text{op}}}\). A cada objeto \(A\) le asigna el funtor representable \(\mathbf{A}(-,A)\) y a cada flecha \(f\colon A\to B\) le asigna la transformación natural \(\mathbf{A}(-,f)\colon\mathbf{A}(-,A)\to\mathbf{A}(-,B)\), que en cada componente es la función que compone con \(f\) por la derecha.

Corolario

El funtor de Grothendieck-Yoneda es fiel y pleno.

Semana 8

Clase 17

Después del largo paréntesis para demostrar el lema de Grothendieck-Yoneda y su corolario, volvimos a la construcción de la conjunción.

Consideramos el siguiente diagrama (la flecha de en medio no va, pero TikZJax sigue sin funcionar y an amscd no hay forma de dibujarlo sin ponerla).

Como todas la biyecciones son naturales, entonces la flecha de abajo es la componente en \(A\) de una transformación natural \(\tau\colon\mathbf{A}(-,\Omega\times\Omega)\to\mathbf{A}(-,\Omega)\). Por el corolario anterior, esta transformación natural está determinada por una flecha entre los objetos \(\Omega\times\Omega\) y \(\Omega\). Esta flecha es nuestra definición de conjunción \(\land\colon\Omega\times\Omega\to\Omega\).

Clase 18

En esta clase regresamos a las construcciones que nos faltan en la categoría de conjuntos abstractos. En concreto, vimos la definición de exponencial.

Definición

Sean \(\mathbf{A}\) una categoría con productos finitos y \(A\) y \(B\) objetos en \(\mathbf{A}\). El objeto exponencial \(B^A\) es un objeto junto con una flecha \(\text{ev}_{A,B}\colon A\times B^A\to B\) tal que para cualquier objeto \(C\) y flecha \(f\colon A\times C\to B\), existe una única flecha \(g\colon C\to B^A\) tal que el siguiente diagrama conmuta

\[\begin{CD} A\times B^A @>\text{ev}_{A,B}>> B\\ @A{\text{id}_A\times g}AA @AAfA\\ A\times C @= A\times C \end{CD}\]

De la definición se puede ver que hay una biyección

No es difícil mostrar que el conjunto de funciones \(B^A=\{f\colon A\to B\mid f\text{ es función}\}\) junto con la función \(\text{ev}_{A,B}\colon A\times B^A\to B\) dada por \(\text{ev}_{A,B}(a,f)=f(a)\) satisface la propiedad universal de la definición anterior. Así, el conjunto de funciones es el exponencial en \(\mathbf{Con}\).

Clase 19

En la categoría generada por la lógica de proposiciones, la exponencial de dos fórmulas es la implicación \(\beta^{\alpha}=\alpha\to\beta\). Además, la vealuación es modus ponens. Finalmente, la biyección \eqref{eq:exp} es el teorema de la deducción.

Semana 9

Clase 20

Ahora empezaremos a usar la exponencial en la categoría de conjuntos abstractos. Para lo cual primero necesitamos la existencia de exponenciales en dicha categoría.

Axioma 6

\(\mathcal{S}\) tiene exponenciales.

Cuando usamos la biyección \eqref{eq:exp} y el hecho \(A\times 1\cong A\) podemos ver que los elementos globales de \(B^A\) son flechas \(A\to B\). Esto es, cada flecha \(f\colon A\to B\) tiene un nombre en la exponencial, que denotamos \(\ulcorner f\urcorner\colon 1\to B^A\). Esta flecha es la que se obtiene mediante la propiedad universal de la exponencial:

Ahora, notemos que la exponencial define dos funciones. Una de ellas es \(X^{(\;)}\colon\mathcal{S}\to\mathcal{S}\), que a cada objeto \(A\) le asigna el exponencial \(X^A\). La otra función es \((\;)^{Y}\colon\mathcal{S}\to\mathcal{S}\), que a cada objeto \(A\) le asigna el exponencial \(A^Y\).

En esta clase vimos que ambas asignaciones se pueden completar a funtores. Para el resto de esta clase fijemos una flecha \(f\colon A\to B\) en \(\mathcal{S}\).

Definimos \(X^f\) usando la propiedad universal de la exponencial. Esto es, mediante el siguiente diagrama conmutativo:

No es difícil ver que esta asignación en flechas define un funtor contravariante.

Proposición

La flecha \(X^f\) es la única que satisface \(X^f\ulcorner g\urcorner=\ulcorner g\circ f\urcorner\).

La flecha \(f^Y\) se define de forma análoga, es decir, se considera:

Esta asignación define un funtor covariante.

Proposición

La flecha \(f^Y\) es la única que satisface \(f^Y\ulcorner g\urcorner=\ulcorner f\circ g\urcorner\).

Clase 21

En esta clase vimos el teorema de Lawvere y como el teorema de Cantor es un corolario del primero. Empezamos con algunos conceptos que aparecerán en el enunciado del teorema de Lawvere.

Definición

Sea \(f\colon A\to A\) en una categoría \(\mathbf{A}\). Decimos que \(f\) tiene un punto fijo si existe \(a\colon 1\to A\) tal que \(fa=a\). Además, \(A\) tiene la propiedad del punto fijo si toda \(f\colon A\to A\) tiene un punto fijo.

Para dar el ejemplo que necesitamos de un objeto que no tiene la propiedad del punto fijo, antes debemos dar un axioma más acerca de la categoría de conjuntos abstractos.

Axioma 7

\(\mathcal{S}\) es booleana, es decir, \(\Omega=1+1\).

Otra forma de escribir el axioma es \(\Omega=2\). En lo siguiente usaremos la notación de \(\Omega\) para recordar que daremos un nuevo conectivo lógico. Sin embargo en el teorema de Cantor usaremos \(2\) ya que esta es la notación estándar en ese lugar.

Ahora construyamos una flecha de la forma \(\Omega\to\Omega\) usando la propiedad universal del coproducto.

Gracias al axioma 7 podemos decir que la flecha definida en el diagrama es la negación.

Es fácil ver, de la definición, que \(\neg\colon\Omega\to\Omega\) no tiene puntos fijos. Así, \(\Omega\) no tiene la propiedad del punto fijo.

Teorema de Lawvere

Si existe \(f\colon A\times A\to B\) tal que para cualquier \(g\colon A\to B\) existe \(a\colon 1\to A\) tal que \(f(-,a)=g\), entonces \(B\) tiene la propiedad del punto fijo.

Este teorema está escrito en términos de productos en los dominios de las flechas. Si lo traducimos a exponenciales, tendremos una flecha \(\bar{f}\colon A\to B^A$ y diremos que para cualquier\)\ulcorner g\urcorner\colon 1\to B^A\(existe\)a\colon 1\to A\(. Finalmente la condición\)f(-,a)=g\(se traduce a\)\bar{f}a=\ulcorner g\urcorner\(. Esto último significa que\)\bar{f}$$ es suprayectiva.

Teorema de Lawvere versión exponencial

Si existe \(f\colon A\to B^A\) suprayectiva, entonces \(B\) tiene la propiedad del punto fijo.

Corolario (Teorema de Cantor)

No existe \(f\colon A\to 2^A\) suprayectiva.

Demostración

Si existe \(f\colon A\to 2^A\) suprayectiva, entonces, por el teorema de Lawvere, \(2\) tiene la propiedad del punto fijo. Sin embargo, ya vimos que \(\neg\colon 2\to 2\) no tiene puntos fijos. Lo cual es un absurdo.

Una observación sobre la lógica de la demostración es que no es una demostración por contradicción. Lo que está usando es la interpretación de la lógica intuisionista de Brower-Heyting-Kolmogorov. Una demostración por contradicción (que haga uso de lógica clásica) es cuando se intententa demostrar \(\varphi\), para ello se supone \(\neg\varphi\) y se llega a una contradicción. Si al terminar este procedimiento se concluye \(\varphi\) entonces sí se usó lógica clásica. De manera intuisionista se concluiría \(\neg\neg\varphi\), pero la afirmación \(\neg\neg\varphi\equiv\varphi\) es clásica.

Clase 22

En esta clase vimos más equivalencias del teorema de Lawvere.

Corolario (paradoja de Russell)

No existe \(R=\{x\mid x\notin x\}\).

Luego, vimos un par que tiene que ver con algo de lenguaje natural. Decimos que un adjetivo es heterológico si no satisface la propiedad que describe. Por ejemplo, monosilábica es heterológica ya que monosilábica no es una palabra monosilábica. En cambio, polisilábica no es heterológica por que sí es polisilábica.

Corolario (paradoja de Grelling)

No existe la colección de adjetivos heterológicos.

Finalmente, vimos otra paradoja conocida.

Corolario (paradoja del mentiroso)

No existe la colección de enunciados que afirman su propia falsedad.

Semana 10

Ahora empezamos un tema nuevo, el objeto de números naturales, que abreviaremos onn. Antes de decir qué es un onn, volveremos a revisar un poco acerca de categorías de pregavillas, es decir, veremos conjuntos variables.

Clase 23

Consideramos la categoría \(\mathbf{A}=(\bullet\to\bullet)\), es decir, sólo hay dos objetos y una flecha no identidad (la identidades no se dibujan). Primero notemos que la opuesta de \(\mathbf{A}\) se ve igual que la original, así que no pondremos opuesta para hacer las pregavillas con esta categoría.

Un objeto (funtor) \(X\in\mathbf{Con}^{\mathbf{A}}\) consta de dos conjuntos y una función entre ellos, \(f_X\colon X_0\to X_1\). Si tenemos dos objetos \(X\) y \(Y\), entonces una flecha (transformación natural) consta de dos funciones \(\tau_0\colon X_0\to Y_0\) y \(\tau_1\colon X_1\to Y_1\) tales que el siguiente diagrama conmuta

Podemos pensar que \(X\) es un sistema que empieza en un estado inicial, \(X_0\), pasa por un proceso, \(f_X\), y termina en un estado final \(X_1\). Esto es, \(X\) es un conjunto que “evolucionó” del “tiempo 0” al “tiempo 1” mediante una “regla de evolución”. En otras palabras es un conjunto que varía en el tiempo.

Una flecha \(\tau\colon X\to Y\) tranforma los estados iniciales y finales de los conjuntos de tal forma que se preserva la evolución, como indica el diagrama conmutativode arriba.

Todas las categorías de pregavillas son topos así que tienen casi todas las propiedades que hemos visto en \(\mathcal{S}\). En particular, tienen objeto terminal. Por cuestiones tipográficas denotaremos al terminal de pregavillas con \(T\). Es fácil ver que el terminal debe cumplir \(T_0=\{*\}=T_1\) y su regla de evolución es la función identidad, es un conjunto que permanece ivariante en el tiempo.

Podemos aprovechar que los subobjetos se pueden dar salvo isomorfismo, de tal forma que un subobjeto \(S\hookrightarrow X\) es un par de subconjuntos \(S_i\subseteq X_i\) con la restricción como regla de evolución, \(f_S=(f_X)|_S\). Con esto se puede saber cómo es el clasificador de subobjetos de esta categoría.

Un elemento \(x\in X_0\) tiene tres opciones. Una es \(x\in S_0\). Otra de ellas es \(x\notin S_0\) pero \(f_X(x)\in S_1\). La úlima es que no se de ninguna de las antariores, \(x\notin S_0\) y \(f_X(x)\notin S_1\). Así el clasificador en el tiempo \(0\) es \(\Omega_0=\{1,2,0\}\). Por otro lado, un elemento \(x\in X_1\) sólo tiene dos opciones \(x\in S_1\) y \(x\notin S_1\). Así, en el tiempo \(1\) el clasificador es \(\Omega_1=\{1,0\}\).

La transformación natural verdadero, \(v\colon T\to\Omega\) es la que en cada tiempo elige a \(1\). Esto es, \(1\) sigue representando a verdadero, \(0\) seguirá siendo falso y \(2\) es un nuevo valor que está entre los dos anteriores. (En un partido de fútbol se puede ganar, \(1\), perder, \(0\), o empatar, \(2\).)

No es difícil ver que \(f_{\Omega}\colon\Omega_0\to\Omega_1\) definida por \(f_{\Omega}(1)=f_{\Omega}(2)=1\) y \(f_{\Omega}(0)=0\) es la regla de evolución que hace que todo subobjeto tenga una única flecha característica.

La categoría de pregavillas que nos interesa es muy similar a la anterior. Ahora consideramos una categoría \(\mathbf{A}\) con sólo un objeto y una flecha no identidad del objeto en sí mismo. Ahora un objeto \(X\) consta es una función \(f_X\colon X\to X\) y las flechas \(\tau\colon X\to Y\) constan de sólo una función que hace conmutar al siguiente diagrama

Un conjunto \(X\) con una función \(f_X\colon X\to X\) es un sistema dinámico discreto. Así, la categoría \(\mathbf{Con}^{\mathbf{A}}\) es la categoría de sistemas dinámicos discretos.

Lo que queremos hacer notar en esta categoría es que los elementos globales no son suficientemente buenos para hablar de los elementos de un sistema dinámico discreto. Si seguimos denotando al terminal con \(T\), entonces un elemento global \(x\colon T\to X\) es un elemento del sistema \(X\) que se queda fijo bajo la dinámica \(f_X\).

Nos gustaría encontrar un objeto \(N\in\mathbf{Con}^{\mathbf{A}}\) tal que los elementos del sistema \(X\), fijos o no bajo la dinámica, estén en biyección con las flechas, transformaciones naturales, \(N\to X\). De esto se extrae la definición de onn.

Definición

Un objeto de números naturales (onn) es un objeto \(N\) con un par de flechas \(0\colon 1\to N\) y \(s\colon N\to N\) tal que para cualquier otro objeto \(A\) con flechas \(a\colon 1\to A\) y \(f\colon A\to A\) existe una única \(h\colon N\to A\) que hace conmutar al siguiente diagrama

\[\begin{CD} 1 @>0>> N @>s>> N\\ @V{id}VV @VhVV @VVhV\\ 1 @>>a> A @>>f> A \end{CD}\]

Paro

Vamos a escribir el material que falta respecto al objeto de números naturales, aunque no lo veamos en clases.

Onn es un sistema de Peano

Originalmente Peano dió un conjunto de axiomas para los números naturales. Estos axiomas son suficientes para poder hacer toda la artmética de números naturales. La lista de axiomas es:

1. \(0\in\mathbb{N}\),
2. si \(n\in\mathbb{N}\), entonces \(s(n)\in\mathbb{N}\),
3. si \(s(n)=s(m)\) entonces \(n=m\),
4. \(0\notin \text{im}(s)\) y
5. si \(A\subseteq\mathbb{N}\) cumple \(0\in A\) y \(n\in A\implies s(n)\in A\) entonces \(A=\mathbb{N}\).

En la teoría de conjuntos usual se demuestra, con estos 5 axiomas, que \(\mathbb{N}\) tiene un teorema de recursión. En esta versión categórica definimos al onn mediante una propiedad universal, que resulta ser recursión. Caundo veamos que nuestro onn satisface los 5 axiomas de Peano obtendremos que esa lista de 5 axiomas es equivalente a un solo axioma.

Los dos primeros axiomas son fáciles ya que \(0\in\mathbb{N}\) se traduce a que haya una flecha \(0\colon 1\to N\), lo cual es parte de la definición de onn. El segundo, traducido a lenguaje de flechas, dice que si \(n\colon 1\to N\) entonces \(sn\colon 1\to N\), el cual se obtiene componiendo.

Para demostrar el tercer axioma, antes debemos ver una variante de recursión.

Proposición

Sea \(A\) en \(\mathcal{S}\) con un elemento global \(a\colon 1\to A\) y una flecha \(f\colon N\times A \to A\). Sucede que existe una única \(h\colon N\to A\) tal que

1. \(h0=a\) y
2. \(h(sn)=f(n,hn)\).

Con esta versión de recursión podemos construir una flecha especial.

Corolario

Existe una única flecha \(p\colon N\to N\), llamada predecesor, tal que

1. \(p0=0\) y
2. \(p(sn)=n\).

Como el segundo punto de la proposición anterior se satisface para cualquier \(n\colon 1\to N\), entonces podemos usar que \(1\) es separador para concluir \(ps=\text{id}\). Esto es, \(s\) es una sección. Por lo tanto, \(s\) es mono. Con esto tenemos el tercer axioma de Peano.

El cuarto axioma se hace de manera directa.

Proposición

No existe \(n\colon 1\to N\) tal que \(sn=0\).

Finalmente, para mostrar el axioma de inducción usaremos más fuertemente que \(1\) es separador.

Proposición

Si \(A\) está en \(\mathcal{S}\), entonces

\[A\cong\sum_{a\colon 1\to A} 1.\]

Gracias a esta última proposición podemos concluir que para definir una flecha \(A\to B\) basta decir a dónde van a dar los elementos globales \(a\colon 1\to A\).

Corolario

Sean \(A\) y \(B\) en \(\mathcal{S}\). Si para cada \(a\colon 1\to A\) existe \(b_a\colon 1\to B\), entonces existe una única \(f\colon A\to B\) tal que \(fa=b_a\).

Con todo lo anterior estamos listos para demostrar inducción.

Proposición

Sea \(m\colon A\rightarrowtail N\). Si se satisface

1. \(0\in_N m\) y
2. \(n\in_N m \implies sn\in_N m\),
   entonces \(m\) es iso.

Aritmética

En lo que sigue veremos cómo definir las operaciones usuales con el objeto de números naturales, \(\cdot,+\colon N\times N\to N\).

Antes de poder definir las operaciones necesitamos algunos resultados y flechas especiales. Empezamos con todo ese preámbulo.

Proposición

Sea \(a\colon A\to A\) en \(\mathcal{S}\). Existe una única \(a^{(\,)}\colon N\to A^A\) tal que

1. \(a^0=\ulcorner\text{id}_A\urcorner\) y
2. \(a^{sn}=\ulcorner a\, a^n\urcorner\).

Notemos que, si usamos nombres en la exponencial, la proposición anterior dice que dado un elemento generalizado \(\ulcorner a\urcorner\colon 1\to A^A\) existe uno \(\ulcorner a^{(\,)}\urcorner\colon 1\to (A^A)^N\). Si usamos el corolario anterior en esta situación obtenemos el siguiente resultado:

Proposición

Existe una única \(\text{iter}\colon A^A\to (A^A)^N\) tal que \(\text{iter}\ulcorner a\urcorner=\ulcorner a^{(\,)}\urcorner\).

Lo siguiente es tomar \(A=N\), es decir, \(\text{iter}\colon N^N\to (N^N)^N\). En este contexto hay que notar que si \(k\colon N\to N^N\), entonces \(k\) representa una operación binaria

Así, si empezamos con \(f\colon N\to N\) podemos considerar \(f^{(\,)}\colon N\to N^N\). Con lo anterior, definimos \(\bar{f}\colon N\times N\to N\) como la composición \(\text{ev}(\text{id}\times f^{(\,)})\). Con esto tenemos las siguientes dos cosas:

1. \(\bar{f}(n,0)=\text{ev}(n,f^0)=\text{ev}(n,\ulcorner\text{id}\urcorner) = \text{id}n = n\) y
2. \(\bar{f}(n,sm)=\text{ev}(n,f^{sm})=\text{ev}(n,\ulcorner ff^m \urcorner)\)
   \(=f f^m n = f \text{ev}(n,\ulcorner f^m \urcorner) = f \text{ev}(n,f^m) = f\bar{f}(n,m)\).

Finalmente, aplicamos este proceso a la flecha sucesor \(s\colon N\to N\). Con esto obtenemos una flecha \(\bar{s}\colon N\times N\to N\) que satisface:

1. \(\bar{s}(n,0)=n\) y
2. \(\bar{s}(n,sm)=s\bar{s}(n,m)\).

Si denotamos con \(x+y\) a la composición \(\bar{s}(x,y)\), entonces los dos puntos anteriores se traducen a lo siguiente:

1. \(n+0=n\) y
2. \(n+sm=s(n+m)\).

Lo cual nos da la definición recursiva de la suma.