Guía 5, Ejercicios 3 y 7
La Guía 5 define subuniverso tres veces: una para la terna (L, s, i), una para el acotado (L, s, i, 0, 1) y una para el complementado (L, s, i, ᶜ, 0, 1). Las tres dicen la misma frase —un subconjunto que contiene las constantes y cierra bajo las operaciones— y por eso se leen como repetición. No lo son. Lo que cambia de una a otra es cuáles son esas constantes y esas operaciones.
Al lado hay otra palabra que se le parece tanto que la guía frena a aclararlo: entre los subuniversos de (L, s, i, 0, 1) y sus subreticulados acotados hay una biyección, y aun así no son lo mismo, porque un subreticulado es una 5-upla y un subuniverso es un conjunto. Esta nota no discute la biyección. Va por lo más crudo: que el mismo conjunto, sin cambiarle un elemento, es subuniverso de una estructura y no lo es de la de al lado.
El reticulado de abajo es el diamante: el 0 abajo de todo, el 1 arriba de todo, y a, b, c en el medio sin relación entre sí. Sobre él están paradas las tres estructuras, con ᶜ fijada en 0ᶜ = 1, 1ᶜ = 0, aᶜ = b, bᶜ = c, cᶜ = a. El dibujo es uno solo; las preguntas son tres.
Armá un S tocando los nodos. Arranca vacío. Si querés ir derecho al caso que le da sentido a la nota, el botón arma {0, a, b, 1}.
Armá {0, a, b, 1} y mirá las cuatro juntas. Las tres primeras dicen que sí: el conjunto cierra bajo s e i, tiene el 0 y el 1, y cada uno de sus cuatro elementos tiene algún complemento adentro —a y b lo son uno del otro, y el 0 y el 1 también—. La cuarta dice que no.
El renglón que lo explica es el único que hay que llevarse de esta nota:
b tiene dos complementos, a y c. a está en S. Pero ᶜ eligió c.
Que ᶜ elija es lo que quedó establecido en Complementar es elegir: cuando un elemento tiene más de un complemento, la operación se queda con uno solo, y cada elección distinta es otra estructura sobre el mismo dibujo. Acá se cobra esa cuenta. La tercera lectura pregunta por una propiedad de S —que adentro nadie se quede sin pareja— y la cuarta pregunta si S cierra bajo una función concreta. Son dos preguntas distintas, y el diamante tiene el tamaño justo para que se contradigan.
Ésa es la refutación que pide el Ejercicio 7, y por eso la tercera lectura está puesta entre las otras y no aparte: separada de la cuarta no hay nada que refutar. Juntas, una dice que sí mientras la otra dice que no.
Probá también {0, a, 1}. Ahí las dos últimas lecturas dicen que no las dos, y se parecen tanto que uno diría que son la misma pregunta: a no tiene ningún complemento adentro, así que ᶜ se le va a escapar sí o sí. Toda la gracia de {0, a, b, 1} es que las separa. Y probá {0, 1}, que dice que sí a las cuatro: es el subuniverso más chico que admite el complementado.
El Ejercicio 3 pide probar que la intersección de dos subuniversos es un subuniverso, y la prueba es tan corta que conviene tenerla antes de tocar nada. Si x e y están en S₁ ∩ S₂, entonces x s y está en S₁ porque S₁ cierra, y está en S₂ por lo mismo, así que está en la intersección; igual con i y con ᶜ. Y cada constante que el tipo pida está en los dos, así que está en la intersección. El argumento no usó en ningún renglón de qué tipo estábamos hablando: vale para los tres.
La pregunta que sigue no la hace la guía y conviene hacérsela: ¿y la unión? El argumento de arriba no se traduce, porque x puede venir de S₁ y y de S₂, y entonces x s y no tiene por qué estar en ninguno de los dos. Pero que un argumento no se traduzca no prueba nada. Hace falta el contraejemplo, y abajo se puede salir a buscarlo.
El botón elige a cuál de los dos conjuntos va lo que toques. Los nodos que están en los dos van llenos —ésa es la intersección— y los que están en uno solo van con el anillo. El rótulo de la izquierda dice en cuál.
Con S₁ = {0, a} y S₂ = {0, b} la unión es {0, a, b} y el testigo dice exactamente dónde se rompe: a s b = 1, y el 1 no está. Cada conjunto por su lado nunca tuvo que calcular ese supremo, porque a y b no se encontraban adentro de ninguno de los dos. Juntarlos los pone en la misma bolsa, y el supremo aparece afuera.
La intersección, en cambio, no se deja romper por ningún par que le pongas, y ahora ya sabés por qué: cerrar es una condición que cada conjunto cumple por separado, y quedarse con lo que los dos tienen conserva las dos garantías a la vez. La unión no conserva ninguna — conserva la unión de los elementos, que es otra cosa.
Que el mismo conjunto cambie de respuesta según el tipo no es una sutileza de notación. Es que «subuniverso» no es una propiedad de un conjunto: es una relación entre un conjunto y un tipo. Preguntar «¿{0, a, b, 1} es subuniverso?» sin decir de qué está tan incompleto como preguntar si un número es mayor, y el widget de arriba es esa pregunta contestada cuatro veces sobre la misma entrada.
Y ahí se ve para qué sirve la distinción del título. Un subuniverso es un conjunto; una subestructura es una upla, y para armarla hay que restringir las operaciones al conjunto. Restringir sólo se puede cuando lo restringido sigue cayendo adentro — eso es cerrar, y por eso hay biyección. Con {0, a, b, 1} el acotado da su 5-upla sin problema, y el complementado no da ninguna 6-upla: ᶜ restringida a ese conjunto no es una función de S en S, porque manda b afuera.
Que la tercera lectura y la cuarta se puedan contradecir es, exactamente, la diferencia entre tener la propiedad y respetar la elección. Tener la propiedad es que adentro de S nadie se quede sin complemento. Respetar la elección es que el complemento que ᶜ señaló —que es uno de los dos, y el dibujo no dice cuál— también esté adentro. Lo primero lo decide el orden; lo segundo lo decide la upla.
Eso es lo que Complementar es elegir dejó dicho y esta nota deja tocar. La misma frontera vuelve a aparecer, del otro lado, en Cada capa le pide más al homomorfismo: ahí lo que se le pregunta al tipo no es un subconjunto sino una función.
Sirve para los ejercicios 3 y 7 de la Guía 5. Las resoluciones están en parcial-2/soluciones/practico-5-reticulados-acotados.pdf del repo de Lógica.