Apéndice C. Ejercicios y soluciones
Este banco propone un recorrido progresivo por las cinco partes del tratado. Cada ejercicio declara procedencia, nivel, fuente, prerrequisitos, pista y solución. Los rótulos C.1–C.31 identifican ejercicios de este apéndice; no son nuevos nodos matemáticos.
Procedencia. “Ejercicio existente” retoma una pregunta ya formulada en el manuscrito, con redacción autosuficiente y solución. “Adaptación” reformula una pregunta, lectura guiada o prueba de estrés identificada en la fuente, y declara cuando restringe el marco. “Propuesta nueva” es una formulación didáctica de esta entrega basada en resultados existentes; no reivindica un teorema nuevo. El banco es una selección organizada, no una reproducción exhaustiva de todas las preguntas dispersas en los capítulos.
Modo de uso. Lea el enunciado y escriba primero los tipos, dominios e hipótesis. Intente resolverlo antes de consultar la pista y la solución. En una demostración, justifique el paso que permite cancelar, seleccionar, evaluar o concluir igualdad; una respuesta numérica correcta no sustituye ese argumento.
| Nivel | Trabajo esperado |
|---|---|
| Inicial | Identificar datos, calcular casos y distinguir conceptos |
| Demostración | Reconstruir un argumento con las hipótesis explícitas |
| Lectura crítica | Localizar una hipótesis, un cambio de contrato o una inferencia inválida |
| Integración | Combinar dominio, igualdad, composición y efectividad en un mismo problema |
Mapa del banco
| Parte | Ejercicios | Propósito |
|---|---|---|
| I. Reconstrucción estructural | C.1–C.7 | Gráficas, proyecciones, elementos, relaciones y elección única |
| II. Parcialidad y lógica | C.8–C.13 | Dominios, composición, complementos, etiquetas y extremos vacíos |
| III. Efectividad y autorreferencia | C.14–C.20 | Enumeración, contratos de terminación, diagonalización y punto fijo |
| IV. Comparación y reconstrucción | C.21–C.26 | Tipos, testigos, representaciones, naturalidad, Yoneda y densidad |
| V. Síntesis | C.27–C.31 | Recuperación exacta, extensión, composición y límites de comprobación |
El banco contiene 5 ejercicios existentes, 15 adaptaciones y 11 propuestas didácticas nuevas. Todos incluyen solución.
Parte I. Reconstrucción estructural
C.1. La gráfica no contiene el codominio
Procedencia: Adaptación. Nivel: Inicial. Fuente: capítulo 1, §1.3, prueba de estrés. Prerrequisitos: TF-THM-00005.
Enunciado. Sean \(f:\{0\}\to\{0\}\) y \(g:\{0\}\to\{0,1\}\), ambas con valor cero. Compare sus gráficas como conjuntos de pares y su sobreyectividad. Explique qué dato falta para reconstruir la flecha desde esos pares.
Pista. Separe los pares ordenados de los extremos declarados.
Solución. Ambas gráficas desnudas son \(\{(0,0)\}\). La función \(f\) es sobreyectiva y \(g\) no alcanza \(1\). Para reconstruir la flecha deben fijarse dominio y codominio, o el ambiente del subobjeto gráfico. El criterio de TF-THM-00005 no identifica flechas de codominios distintos.
C.2. Reconstrucción por proyecciones
Procedencia: Propuesta nueva. Nivel: Demostración. Fuente: capítulo 1, §1.3. Prerrequisitos: TF-THM-00005, TF-AX-00004.
Enunciado. En una categoría con el producto \(A\times B\), sea \(m:R\rightarrowtail A\times B\). Escriba \(p=\pi_A m\) y \(q=\pi_B m\). Si \(p\) es iso, pruebe que \(m\) representa la gráfica de \(f=q p^{-1}\) y que esa flecha es única.
Pista. Compare ambas proyecciones de dos mapas hacia el producto.
Solución. Para \(\gamma_f=\langle1_A,f\rangle\), las proyecciones de \(\gamma_f p\) son \(p\) y \(fp=q\). La universalidad da \(\gamma_f p=m\); como \(p\) es iso, representan el mismo subobjeto. Si \(m=\gamma_g j\) con \(j:R\to A\) iso, la primera proyección obliga \(j=p\) y la segunda da \(q=gp\), luego \(g=qp^{-1}=f\). No se escoge un valor en cada fibra.
C.3. Dónde se usa que el terminal genere
Procedencia: Adaptación. Nivel: Inicial. Fuente: capítulo 2, §2.1, pregunta de lectura. Prerrequisitos: TF-THM-00007, TF-CEX-00001.
Enunciado. Para \(f,g:A\to B\), distinga las hipótesis usadas en cada dirección de “\(f=g\) si y sólo si \(fa=ga\) para todo \(a:1\to A\)”. Explique el fallo en la órbita libre de \(C_2\).
Pista. La composición respeta igualdad, pero el terminal puede no separar.
Solución. De \(f=g\) se obtiene \(fa=ga\) por sustitución; no se usa que \(1\) genere. La vuelta exige que los puntos globales separen flechas, es decir, la propiedad generadora del terminal. En el objeto de dos elementos intercambiados por \(C_2\) no hay puntos globales; identidad y transposición son distintas, pero satisfacen vacíamente la condición. No se concluye igualdad.
C.4. Un mono biyectivo que no es iso
Procedencia: Propuesta nueva. Nivel: Demostración. Fuente: capítulo 3, §3.3.5. Prerrequisitos: TF-CEX-00002.
Enunciado. En Pos, considere la identidad subyacente del orden discreto \(D=\{p,q\}\) a la cadena \(C=\{p<q\}\). Pruebe que es mono y no iso. ¿Por qué un clasificador de todos los monos produciría una contradicción?
Pista. Una característica de ese mono tendría que ser constantemente verdadera.
Solución. El mapa es monótono e inyectivo, por lo que se cancela a la izquierda punto a punto. Su inversa conjuntista no es monótona: \(p<q\) en \(C\) pero no en \(D\). Si fuera pullback de verdad por \(\chi:C\to\Omega\), la sobreyectividad subyacente forzaría \(\chi(p)=\chi(q)=\mathsf{true}\). El pullback de verdad por la constante verdadera es \(1_C\); unicidad del pullback haría iso al mono, contradicción. No se confunden monos con inclusiones que reflejan orden.
C.5. Composición de relaciones mediante testigos
Procedencia: Propuesta nueva. Nivel: Inicial. Fuente: capítulo 4, §4.3. Prerrequisitos: TF-DEF-00015, TF-THM-00028.
Enunciado. En Set, sean \(A=\{a,b\}\), \(B=\{0,1\}\), \(C=\{x,y\}\), \(R=\{(a,0),(a,1),(b,1)\}\) y \(S=\{(0,x),(1,x),(1,y)\}\). Enumere el objeto de testigos de la composición y su imagen en \(A\times C\). ¿Qué pierde esa imagen?
Pista. Conserve primero la coordenada intermedia.
Solución. Los testigos son \((a,0,x)\), \((a,1,x)\), \((a,1,y)\), \((b,1,x)\) y \((b,1,y)\). La imagen es \(\{(a,x),(a,y),(b,x),(b,y)\}\). Dos testigos diferentes producen \((a,x)\), pero la relación compuesta registra pertenencia, no multiplicidad ni elección del testigo. Este cálculo usa la composición en Set; no demuestra la asociatividad regular general.
C.6. Selector, sección y cambio de grupo
Procedencia: Adaptación. Nivel: Demostración. Fuente: capítulo 5, §5.5, preguntas 1–2. Prerrequisitos: TF-THM-00034, TF-CEX-00003.
Enunciado. Para una relación \(m:R\rightarrowtail A\times B\) con proyecciones \(p,q\), escriba la correspondencia entre sección \(t\) de \(p\) y selector \(s\). Después explique por qué no puede reemplazarse \(\mathbb Z\) por \(\mathbb Z/3\mathbb Z\) en el cociente hacia \(\mathbb Z/2\mathbb Z\) del contraejemplo.
Pista. Una factorización de la gráfica debe recuperar su primera proyección.
Solución. Si \(pt=1_A\), el selector es \(s=qt\) y \(mt=\langle1_A,s\rangle\). Recíprocamente, una factorización \(mt=\langle1_A,s\rangle\) da \(pt=1_A\); el mediador es único por monicidad de \(m\). Ser epi no suministra tal \(t\). Un homomorfismo \(h:\mathbb Z/3\mathbb Z\to\mathbb Z/2\mathbb Z\) cumple \(3h([1])=0\), que en el destino implica \(h([1])=0\). Sólo existe el homomorfismo cero; no una sobreyección. La sustitución no preserva el ejemplo.
C.7. Separación y existencia única
Procedencia: Adaptación. Nivel: Demostración. Fuente: capítulo 5, §5.5, pregunta 3. Prerrequisitos: TF-THM-00039.
Enunciado. Dados conjuntos \(A,B\) y una fórmula de ZF \(\varphi(a,b)\) con un único \(b\in B\) para cada \(a\in A\), indique qué hace separación y qué hace unicidad. ¿Dónde sería necesario AC?
Pista. Forme primero un subconjunto del producto.
Solución. Separación forma \(F=\{(a,b)\in A\times B:\varphi(a,b)\}\). La existencia asegura totalidad y la unicidad asegura univaluación, así que \(F\) es una gráfica. La extensionalidad asegura que otra gráfica con esos mismos pares sea igual. AC no interviene: no hay alternativas entre las que seleccionar. Si se elimina unicidad, pedir un selector general es otro problema.
Parte II. Parcialidad y lógica
C.8. Dos asociaciones de tres aplicaciones parciales
Procedencia: Adaptación. Nivel: Demostración. Fuente: capítulo 6, §6.7, pregunta 1, restringida a Set. Prerrequisitos: TF-THM-00043.
Enunciado. Sean parciales \(f:A\rightharpoonup B\), \(g:B\rightharpoonup C\) y \(h:C\rightharpoonup E\), con dominios \(D_f,D_g,D_h\). Compare los testigos parentizados \(((a,b),c)\) y \((a,(b,c))\) sujetos a \(a\in D_f\), \(b=f(a)\in D_g\) y \(c=g(b)\in D_h\). Construya la correspondencia y compare dominio y valor.
Pista. Cambie los paréntesis, conservando todas las condiciones.
Solución. La biyección \(((a,b),c)\mapsto(a,(b,c))\) tiene inversa evidente y conserva las tres ecuaciones. Ambas proyecciones sobre \(A\) tienen imagen \(\{a\in D_f:f(a)\in D_g,\ g(f(a))\in D_h\}\) y ambas salidas son \(h(g(f(a)))\). Por tanto ambas asociaciones tienen dominio y valor iguales. En categorías generales el cambio de paréntesis se reemplaza por el isomorfismo universal de los pullbacks; aquí se ha pedido sólo su instancia en Set.
C.9. El dominio se restringe antes de componer
Procedencia: Propuesta nueva. Nivel: Inicial. Fuente: capítulo 7, §7.2. Prerrequisitos: TF-THM-00054.
Enunciado. Sean \(f:\mathbb N\rightharpoonup\mathbb N\) con \(f(2k)=k\) y \(g:\mathbb N\rightharpoonup\mathbb N\) con \(g(n)=n-1\) para \(n>0\). Determine dominio y valor de \(g\circ f\) y de \(f\circ g\).
Pista. Exija pertenencia al segundo dominio después de aplicar el primer mapa.
Solución. Para \(g\circ f\), la entrada es \(2k\) con \(k>0\); el dominio son los pares positivos y el valor es \(k-1\). Para \(f\circ g\), debe ser \(n>0\) y \(n-1\) par; el dominio son los impares positivos y el valor es \((n-1)/2\). En cero ninguna composición está definida. No basta intersectar los dominios originales, porque se comprueba también el valor intermedio.
C.10. Mismo dominio, valores diferentes
Procedencia: Adaptación. Nivel: Inicial. Fuente: capítulo 7, §7.5, pregunta 2. Prerrequisitos: TF-THM-00056.
Enunciado. Exhiba dos aplicaciones parciales con igual predicado de dominio y distintos valores. Precise qué falta para deducir su igualdad.
Pista. Use un dominio común no vacío y un codominio con dos elementos.
Solución. Sobre \(A=\{0,1\}\) y con codominio \(\{a,b\}\), tome dominio \(D=\{0\}\) para ambas, una con valor \(a\) y otra con valor \(b\). Sus características de dominio coinciden, pero sus gráficas son \(\{(0,a)\}\) y \(\{(0,b)\}\). TF-THM-00056 exige igual dominio y valores coincidentes tras identificar sus representantes; la primera condición sola no basta.
C.11. Un dominio sin complemento
Procedencia: Adaptación. Nivel: Demostración. Fuente: capítulo 7, §7.5, pregunta 4. Prerrequisitos: TF-CEX-00006.
Enunciado. Enumere los subobjetos del terminal \(T=(1\to1)\) en la categoría de flechas de conjuntos. Compruebe que \(U=(\varnothing\to1)\) no tiene complemento.
Pista. La pareja \((1,\varnothing)\) no define una subflecha.
Solución. Las únicas posibilidades compatibles con la flecha son \(\bot=(\varnothing\to\varnothing)\), \(U=(\varnothing\to1)\) y \(\top=T\). Forman una cadena. Para que \(V\cap U=\bot\), necesariamente \(V=\bot\); entonces \(V\cup U=U\ne T\). No hay complemento. Una fórmula global por los casos “dentro” y “fuera” que exija dominios complementarios no se obtiene automáticamente.
C.12. Tres parciales y sólo dos etiquetas
Procedencia: Adaptación. Nivel: Demostración. Fuente: capítulo 8, §8.6, pregunta 3. Prerrequisitos: TF-CEX-00007, TF-THM-00063.
Enunciado. En el modelo anterior calcule \(\operatorname{Par}(T,T)\) y \(\operatorname{Hom}(T,T\sqcup T)\). Deduzca por qué \(L(T)\) no puede ser isomorfo a \(T\sqcup T\).
Pista. Hacia el terminal hay un único mapa por cada dominio.
Solución. Cada subobjeto de \(T\) da una parcial única hacia \(T\), así que hay tres parciales. Una flecha natural \(T\to T\sqcup T\) escoge el mismo elemento de \(\{0,1\}\) en ambos componentes, por lo que hay dos. Si \(L(T)\cong T\sqcup T\), sus conjuntos de flechas desde \(T\) serían biyectivos; pero el primero clasifica las tres parciales. La contradicción impide el isomorfismo, no la existencia de \(L(T)\).
C.13. El codominio vacío en una prolongación
Procedencia: Adaptación. Nivel: Inicial. Fuente: capítulo 6, §6.7, pregunta 5, con control de extensión. Prerrequisitos: TF-EXA-00010, TF-THM-00048.
Enunciado. En Set, represente la parcial totalmente indefinida \(A\rightharpoonup\varnothing\) por un span. ¿Cuándo admite extensión total \(A\to\varnothing\)? Relacione el caso con una prolongación por valor por defecto.
Pista. Un valor por defecto exige que el codominio esté habitado.
Solución. El span es \(A\leftarrow\varnothing\to\varnothing\), con la inclusión vacía como mono. La única parcial de ese tipo tiene dominio vacío. Una extensión total existe exactamente cuando \(A=\varnothing\); si \(A\) tiene un elemento, no puede asignarle un valor en el vacío. Por eso una construcción por valor fijo en el codominio exige tal valor o un dominio ya total. No se aplica sin revisar las hipótesis de TF-THM-00048.
Parte III. Efectividad y autorreferencia
C.14. Buscar un valor en una gráfica enumerable
Procedencia: Adaptación. Nivel: Demostración. Fuente: capítulo 9, §9.5, pregunta 1. Prerrequisitos: TF-THM-00070.
Enunciado. Sea \(R\subseteq\mathbb N^2\) una relación c.e. y univaluada. Construya un programa de parada exacta para la función parcial cuya gráfica es \(R\). Indique dónde se usa univaluación.
Pista. Espere a que aparezca un par con la entrada requerida.
Solución. Dada \(n\), ejecute la enumeración de \(R\) hasta ver \((n,m)\) y devuelva \(m\). Si hay un par con primera coordenada \(n\), aparecerá en tiempo finito; si no lo hay, el programa no termina. La univaluación garantiza que cualquier par encontrado tenga el mismo segundo componente, por lo que el resultado no depende del orden de enumeración. Sin ella habría una selección inducida por el procedimiento, pero \(R\) no sería la gráfica de una función.
C.15. Extensión y totalización etiquetada
Procedencia: Adaptación. Nivel: Demostración. Fuente: capítulo 9, §9.5, preguntas 2–3. Prerrequisitos: TF-CEX-00009, TF-THM-00073.
Enunciado. Explique por qué una extensión computable de una parcial no decide siempre su dominio. Después pruebe el criterio de totalización etiquetada para \(f:\mathbb N\rightharpoonup\mathbb N\) de parada exacta, con etiquetas decidibles.
Pista. Una extensión puede devolver el mismo número dentro y fuera del dominio.
Solución. La parcial constante cero sobre \(K\) tiene extensión total constante cero, aunque \(K\) sea indecidible. Si, en cambio, un algoritmo total devuelve Some(f(n)) en el dominio y None fuera, inspeccionar la etiqueta decide pertenencia. Recíprocamente, si el dominio es decidible, fuera devolvemos None y dentro ejecutamos el programa parcial, que termina por la pertenencia ya decidida. Ambas ramas terminan; se ha construido la totalización requerida.
C.16. El realizador constante no reconoce el dominio
Procedencia: Adaptación. Nivel: Lectura crítica. Fuente: capítulo 9, §9.5, pregunta 5. Prerrequisitos: TF-CEX-00010, TF-THM-00069.
Enunciado. Para \(D=\mathbb N\setminus K\), una parcial vale cero en \(D\) y no está definida fuera. Explique cómo la realiza bajo promesa un operador total constante y por qué no se deduce que \(D\) sea c.e.
Pista. El contrato puede no imponer nada fuera de los nombres admisibles.
Solución. Con la representación de naturales del capítulo, el operador emite siempre un nombre de cero y es correcto sobre los nombres de elementos de \(D\). Fuera de \(D\) el contrato bajo promesa guarda silencio. Su propia terminación no coincide con el dominio de la parcial representada. TF-THM-00069 exige esa coincidencia en el contrato de parada exacta; no se aplica aquí. Como \(D\) no es c.e., tampoco puede existir un programa de parada exacta con ese dominio.
C.17. Para qué sirve la promesa de totalidad
Procedencia: Adaptación. Nivel: Demostración. Fuente: capítulo 10, §10.6, pregunta 2. Prerrequisitos: TF-THM-00082.
Enunciado. Dados índices de dos funciones que se promete son totales, describa un semidecisor de desigualdad y explique dónde usa la promesa. ¿Por qué buscar salidas distintas no basta para parciales arbitrarias?
Pista. Una diferencia puede estar en la terminación, no en los valores.
Solución. Simule en paralelo ambos programas sobre todas las entradas y acepte al encontrar dos salidas diferentes para la misma entrada. Si las funciones totales difieren, existe esa entrada y ambas ejecuciones acabarán. Si coinciden, no se acepta. Para parciales, una puede terminar y la otra divergir en una entrada; son distintas pero no habrá dos valores que comparar. Este algoritmo no semidecide toda desigualdad parcial ni decide igualdad bajo promesa.
C.18. La diagonal y el tipo de su familia
Procedencia: Propuesta nueva. Nivel: Demostración. Fuente: capítulo 11, §11.1. Prerrequisitos: TF-THM-00088.
Enunciado. Sean \(A\) un conjunto, \(B=\{0,1\}\) y \(U:A\times A\to B\) total. Defina \(d(a)=1-U(a,a)\) y pruebe que ninguna sección \(U_p(a)=U(p,a)\) es \(d\). Trate \(A=\varnothing\) y explique por qué no se obtiene una contradicción con un evaluador parcial.
Pista. Para excluir la sección de índice p, evalúe en p.
Solución. Si \(d=U_p\), en \(p\) se tendría \(U(p,p)=1-U(p,p)\), imposible en \(\{0,1\}\). Si \(A\) es vacío, hay una única función \(d:A\to B\), pero no hay índices \(p\) ni secciones de la familia; sigue sin estar representada. La evaluación diagonal requiere que \(U(a,a)\) esté definida. Un evaluador parcial puede divergir y no suministra el valor necesario para construir una diagonal total mediante esta fórmula.
C.19. Testigos locales y selección simultánea
Procedencia: Adaptación. Nivel: Lectura crítica. Fuente: capítulo 12, ejercicios de control, inciso a. Prerrequisitos: TF-THM-00098, TF-THM-00038.
Enunciado. Explique por qué la afirmación general “toda sobreyección de conjuntos tiene sección” equivale a AC, pero la prueba diagonal reindexada con \(q:A\twoheadrightarrow P\) puede excluir cada sección sin escoger una sección de \(q\).
Pista. Distinga fijar un p y usar un preimagen de construir una función de preimágenes.
Solución. AC aplicado a las fibras de una sobreyección da una sección. Recíprocamente, para una familia \((X_i)_{i\in I}\) no vacía en cada índice, la proyección de su unión disjunta a \(I\) es sobreyectiva; una sección suministra una elección en cada \(X_i\). Es una equivalencia de principios, no una adopción de AC. En la diagonal, fijado un \(p\), la sobreyectividad permite tomar localmente \(a\) con \(q(a)=p\) y obtener la contradicción en ese \(a\). Así se demuestra para todo \(p\) que la diagonal difiere de \(U_p\), sin definir simultáneamente un mapa \(P\to A\). No se pretende demostrar aquí independencia de AC respecto de ZF.
C.20. La totalidad del transformador de índices
Procedencia: Adaptación. Nivel: Lectura crítica. Fuente: capítulo 12, ejercicios de control, inciso c. Prerrequisitos: TF-THM-00100, TF-DEF-00052.
Enunciado. En la prueba del punto fijo extensional, \(H(x,y)\simeq\varphi_{F(S(x,x))}(y)\) y \(e=S(p,p)\), donde \(p\) indexa \(H\). Determine qué puede fallar si \(F\) es parcial computable. ¿Deja necesariamente de existir un índice para \(H\)?
Pista. No confunda que H sea parcial computable con que F(e) esté definido.
Solución. La composición sigue describiendo un algoritmo parcial computable: si el cálculo de \(F(S(x,x))\) diverge, también diverge \(H(x,y)\). Por tanto puede existir un índice \(p\) para \(H\). Lo que no queda garantizado es que \(F(e)\) termine y entregue un índice; entonces la conclusión \(\varphi_e\simeq\varphi_{F(e)}\) no está formulada con un índice numérico disponible. Si \(F\) diverge en todas las entradas, no hay ningún \(e\) con \(F(e)\) definido. La totalidad evita precisamente ese fallo; no asegura que las funciones indexadas sean totales.
Parte IV. Comparación y reconstrucción
C.21. Beta y eta como igualdades de funciones
Procedencia: Propuesta nueva. Nivel: Demostración. Fuente: capítulo 13, §13.2. Prerrequisitos: TF-THM-00103, TF-THM-00104.
Enunciado. En Set, para \(h:X\times A\to B\) defina \(\operatorname{curry}(h)(x)(a)=h(x,a)\) y para \(k:X\to B^A\) defina \(\operatorname{uncurry}(k)(x,a)=k(x)(a)\). Pruebe las dos recuperaciones. ¿Qué formalismo no queda identificado por ese cálculo?
Pista. Evalúe primero en un par y después en dos argumentos.
Solución. Se tiene \(\operatorname{uncurry}(\operatorname{curry}(h))(x,a)=h(x,a)\), luego igualdad por extensionalidad. También \(\operatorname{curry}(\operatorname{uncurry}(k))(x)(a)=k(x)(a)\); extensionalidad en \(a\) y después en \(x\) da igualdad de funciones. Es una interpretación concreta en Set. No identifica igualdad por reducción y proposicional en toda teoría de tipos ni prueba equivalencia entre fundamentos completos.
C.22. Extraer los testigos que ya se tienen
Procedencia: Propuesta nueva. Nivel: Demostración. Fuente: capítulo 13, §13.4. Prerrequisitos: TF-THM-00107.
Enunciado. En el sistema dependiente declarado en el capítulo, de \(w:\prod_{a:A}\sum_{b:B}R(a,b)\) construya una pareja formada por \(f:\prod_{a:A}B\) y una prueba de \(\prod_aR(a,f(a))\). Dé la operación inversa y explique el límite respecto de existencia truncada.
Pista. Use las dos proyecciones del par w(a).
Solución. Defina \(f(a)=\pi_1(w(a))\) y \(r(a)=\pi_2(w(a))\). La segunda componente tiene tipo \(R(a,f(a))\), así que \((f,r)\) cumple lo pedido. De \((f,r)\) se vuelve a \(a\mapsto(f(a),r(a))\). Las recuperaciones se entienden con las reglas de igualdad de funciones y pares del sistema elegido. No se ha eliminado una existencia truncada hacia un dato arbitrario: cada \(w(a)\) ya contiene un valor y su prueba.
C.23. Un cambio de nombres no computable
Procedencia: Propuesta nueva. Nivel: Demostración. Fuente: capítulo 14, §14.3.4. Prerrequisitos: TF-CEX-00019.
Enunciado. Sea \(p\) la permutación de naturales que intercambia \(2n\) y \(2n+1\) exactamente cuando \(n\in K\). Para las representaciones \(\delta_0(m)=m\) y \(\delta_p(m)=p(m)\), determine cualquier traductor de \(\delta_0\) a \(\delta_p\) y pruebe que no es computable.
Pista. La ecuación de representación determina el traductor de manera única.
Solución. Un traductor \(T\) debe cumplir \(p(T(m))=m\). Como \(p^{-1}=p\), se obtiene \(T(m)=p(m)\). Si fuese computable, calcular \(T(2n)\) y examinar su paridad decidiría \(K\): es impar exactamente cuando \(n\in K\). La contradicción no impide que \(p\) exista como biyección conjuntista. La computabilidad depende del contrato de nombres.
C.24. Biyecciones que no forman un mapa natural
Procedencia: Propuesta nueva. Nivel: Inicial. Fuente: capítulo 15, §15.1.5. Prerrequisitos: TF-CEX-00020, TF-THM-00116.
Enunciado. Sobre la categoría \(0\to1\), tome \(F=G\) constantes en \(B=\{a,b\}\) y componentes \(\alpha_0=1_B\), \(\alpha_1\) transposición. Compruebe qué cuadrado falla y por qué no basta invertir las componentes.
Pista. Escriba G(u)α₀ y α₁F(u).
Solución. Ambos funtores envían \(u\) a \(1_B\), así que \(G(u)\alpha_0=1_B\) y \(\alpha_1F(u)=\alpha_1\ne1_B\). Falta naturalidad. Aunque cada componente tenga inversa, la familia no es una transformación natural a la que aplicar el criterio de isomorfismo. Invertir componentes no corrige la ecuación que ya falla.
C.25. Recuperación de Yoneda para un prehaz
Procedencia: Propuesta nueva. Nivel: Demostración. Fuente: capítulo 15, §15.2.2. Prerrequisitos: TF-THM-00117.
Enunciado. Sea \(\mathcal C\) pequeña, \(F:\mathcal C^{op}\to\mathbf{Set}\) y \(A\in\mathcal C\). Para \(x\in F(A)\), defina \(\eta^x_X(g)=F(g)(x)\) para \(g:X\to A\). Pruebe naturalidad y que \(\eta\mapsto\eta_A(1_A)\) es inversa de \(x\mapsto\eta^x\).
Pista. Use contravarianza y después naturalidad respecto de g.
Solución. Si \(u:Y\to X\), entonces \(F(u)(\eta^x_X(g))=F(u)F(g)(x)=F(g\circ u)(x)=\eta^x_Y(g\circ u)\). Por tanto \(\eta^x\) es natural. Evaluar en \(1_A\) devuelve \(F(1_A)(x)=x\). Para una \(\eta:yA\Rightarrow F\) natural, su naturalidad respecto de \(g:X\to A\) da \(F(g)(\eta_A(1_A))=\eta_X(g)\). Así la construcción inversa recupera cada componente. Se declara pequeñez para mantener el control de conjuntos; no se obtiene un algoritmo de igualdad de transformaciones.
C.26. Densidad en la categoría terminal
Procedencia: Propuesta nueva. Nivel: Demostración. Fuente: capítulo 16, §16.5.1. Prerrequisitos: TF-CEX-00022, TF-THM-00127, TF-THM-00132.
Enunciado. Sobre la categoría terminal, considere el prehaz \(F(*)=\{0,1\}\). Describa su categoría de elementos, el diagrama de representables y su colímite. ¿Es F representable?
Pista. Cada representable tiene un elemento y hay un objeto de elementos por valor.
Solución. La categoría de elementos tiene dos objetos, \((*,0)\) y \((*,1)\), y sólo sus identidades. El diagrama contiene dos copias del representable unitario. Su colímite es el coproducto de esos dos singletons, isomorfo a \(\{0,1\}\). No hay un representable de dos elementos, luego \(F\) no es representable. La categoría de elementos tampoco tiene terminal. La densidad se cumple y no afirma representabilidad individual.
Parte V. Síntesis
C.27. Una relación univaluada que no es total
Procedencia: Ejercicio existente. Nivel: Integración. Fuente: capítulo 17, §17.5.1, ejercicio de control. Prerrequisitos: TF-THM-00005, TF-THM-00033.
Enunciado. Sean \(A=\{0,1\}\), \(B=\{b\}\) y \(R=\{(0,b)\}\). ¿Qué condición falla? ¿Puede la recuperación producir una función total \(A\to B\) sin cambiar el subobjeto?
Pista. Examine la primera proyección y la entrada 1.
Solución. La proyección \(R\to A\) es inyectiva y no sobreyectiva. La relación es univaluada, pero no total, y la proyección no es invertible. Añadir \((1,b)\) produce una función total, pero cambia el subobjeto. Se trata de una extensión, no de la recuperación exacta de la relación original.
C.28. Todas las sondas y una identidad
Procedencia: Ejercicio existente. Nivel: Integración. Fuente: capítulo 17, §17.5.2, ejercicio de control. Prerrequisitos: TF-THM-00009, TF-CEX-00001.
Enunciado. Para \(f,g:A\to B\), suponga \(fu=gu\) para toda \(u:X\to A\) y todo \(X\). ¿Se necesita elección para deducir \(f=g\)? ¿Puede reemplazarse “todo X” por \(X=1\) sin una hipótesis adicional?
Pista. Entre las sondas ya se encuentra 1_A.
Solución. Tome \(X=A\) y \(u=1_A\). Resulta \(f=f1_A=g1_A=g\), sin elección de una familia de testigos. Restringirse a \(X=1\) exige que el terminal separe flechas; TF-CEX-00001 muestra que puede fallar. La identidad del objeto proporciona una sonda disponible sin postular puntos globales.
C.29. La prolongación olvida el dominio
Procedencia: Ejercicio existente. Nivel: Integración. Fuente: capítulo 18, §18.5, ejercicio 1. Prerrequisitos: TF-THM-00056.
Enunciado. Sea \(D=\{k^2:k\in\mathbb N\}\) y \(\rho:\mathbb N\rightharpoonup\mathbb N\) la raíz exacta con dominio \(D\). Sea \(\tau\) igual a \(\rho\) en \(D\) y definida además en \(2\), con valor cero. Prolongue ambas por cero fuera de sus dominios. Compare las prolongaciones y las parciales.
Pista. Distingua el valor añadido en 2 de una etiqueta de indefinición.
Solución. Ambas prolongaciones valen la raíz exacta en \(D\) y cero fuera de \(D\), por lo que coinciden. Las parciales no coinciden: \(2\) pertenece al dominio de \(\tau\) y no al de \(\rho\), y sus gráficas difieren por \((2,0)\). El criterio de igualdad parcial incluye dominio, no sólo valores en la intersección.
C.30. Dos raíces y composición etiquetada
Procedencia: Ejercicio existente. Nivel: Integración. Fuente: capítulo 18, §18.5, ejercicio 2. Prerrequisitos: TF-THM-00054, TF-THM-00110.
Enunciado. Para la parcial \(\rho\) del ejercicio anterior, calcule \(\rho\circ\rho\) en \(0\), \(4\) y \(16\) y determine su dominio. Describa la composición de las codificaciones \(\widehat\rho:\mathbb N\to\mathbb N\sqcup\{\bot\}\).
Pista. El valor de la primera raíz debe volver a ser un cuadrado.
Solución. La composición está definida cuando \(n=k^2\) y \(k=\ell^2\), es decir, \(n=\ell^4\). Devuelve entonces \(\ell\). En cero devuelve cero, en cuatro queda indefinida y en dieciséis devuelve dos. La composición etiquetada propaga la etiqueta indefinida y aplica \(\widehat\rho\) al valor numérico de la otra rama. La composición ordinaria de las dos codificaciones no está tipada: la primera entrega un valor en una suma, no un natural sin etiqueta.
C.31. Pruebas finitas y demostración universal
Procedencia: Ejercicio existente. Nivel: Integración. Fuente: capítulo 18, §18.5, ejercicio 3. Prerrequisitos: TF-THM-00081.
Enunciado. Dos implementaciones pasan las entradas de \(0\) a \(1000\). ¿Queda probada su igualdad extensional sobre los naturales? Dé dos programas totales que muestren el límite de esa inferencia.
Pista. Cambie una salida fuera de la muestra.
Solución. No. Los programas \(f(n)=0\) y \(g(n)=1\) si \(n=1001\), cero en otro caso, son totales computables y coinciden en la muestra, pero difieren en \(1001\). Una prueba con invariante y terminación puede acreditar una afirmación universal específica; la batería finita por sí sola no lo hace.
Itinerarios sugeridos
- Primera lectura: C.1, C.3, C.5, C.9–C.13, C.24 y C.27–C.31. El objetivo es reconocer qué dato falta cuando una comparación falla.
- Reconstrucción de demostraciones: C.2, C.4, C.6–C.8, C.14–C.15, C.18, C.21–C.22 y C.25–C.26. Compare su argumento con la prueba fuente.
- Fronteras fundacionales y efectivas: C.16–C.20 y C.23, después de leer los capítulos pertinentes. Evite convertir una equivalencia de principios en adopción de un axioma o un punto fijo semántico en igualdad de códigos.
Estos itinerarios pueden solaparse y no sustituyen los prerrequisitos de cada ejercicio. Para encontrar las pruebas consulte el atlas de teoremas; para escoger un modelo que refute una inferencia, el catálogo de contraejemplos.
Criterios de revisión de una solución
Una solución suficiente declara el marco usado, conserva los extremos, distingue existencia de dato suministrado y justifica su noción de igualdad. Si se pide algoritmo, identifica representación, corrección y terminación; si se pide una imposibilidad, muestra la contradicción o reducción precisa. Debe separar el cálculo de una instancia del teorema general y explicar qué cambiaría al retirar una hipótesis.
En C.8 se pide expresamente una instancia en Set; no se presenta como prueba de la asociatividad en toda categoría. C.19 demuestra una equivalencia con AC, no su independencia. C.20 conserva la computabilidad parcial de la composición, pero detecta que el índice final puede no existir como valor. Estas diferencias forman parte de las respuestas, no son observaciones accesorias.