Un filtro de un reticulado terna \((L,\mathsf{s},\mathsf{i})\) será un subconjunto \(F\subseteq L\) tal que:
adhocprefix(1)adhocsufix \(F\neq\emptyset\)
adhocprefix(2)adhocsufix para cada \(x,y\in F\text{ se tiene que }x\;\mathsf{i\;}y\in F\)
adhocprefix(3)adhocsufix para cada \(x,y\in L\), si \(x\in F\) y \(x\leq y\text{ entonces }y\in F\)
El nombre "filtro" es inspirado por la propiedad (3) ya que si un filtro o colador atrapa a cierto objeto \(x\), entonces claramente atrapara a todos los objetos mas grandes que \(x\).
Dado un conjunto \(S\subseteq L\), denotemos con \([S)\) el siguiente conjunto \[\{y\in L:y\geq s_{1}\;\mathsf{i\;}...\;\mathsf{i\;}s_{n}\text{, para algunos }s_{1},...,s_{n}\in S\text{, }n\geq1\}\]
5.27. Sea \((L,\mathsf{s},\mathsf{i})\) un reticulado terna. Supongamos \(S\subseteq L\) es no vacío. Entonces \([S)\) es un filtro de \((L,\mathsf{s},\mathsf{i})\). Mas aun si \(F\) es un filtro de \((L,\mathsf{s},\mathsf{i})\) y \(F\supseteq S\), entonces \(F\supseteq[S)\). Es decir, \([S)\) es el menor filtro de \((L,\mathsf{s},\mathsf{i})\) que contiene a \(S\).
Proof. Ya que \(S\subseteq[S)\), tenemos que \([S)\neq\emptyset\). Claramente \([S)\) cumple la propiedad (3). Veamos cumple la (2). Si \(y\geq s_{1}\;\mathsf{i\;}s_{2}\;\mathsf{i\;}...\;\mathsf{i\;}s_{n}\) y \(z\geq t_{1}\;\mathsf{i\;}t_{2}\;\mathsf{i\;}\)...\(\;\mathsf{i\;}t_{m}\), con \(s_{1},s_{2},...,s_{n}\), \(t_{1},t_{2},...,t_{m}\in S\), entonces \[y\;\mathsf{i\;}z\geq s_{1}\;\mathsf{i\;}s_{2}\;\mathsf{i\;}...\;\mathsf{i\;}s_{n}\;\mathsf{i\;}t_{1}\;\mathsf{i\;}t_{2}\;\mathsf{i\;}...\;\mathsf{i\;}t_{m}\] lo cual prueba (2).
Llamaremos a \([S)\) el filtro generado por \(S\) en \((L,\mathsf{s},\mathsf{i})\). Cuando \(S\) es finito, ya que existe \(\inf(S)\), es claro que \([S)=\{y\in L:y\geq\inf(S)\}\). Cuando \(S\) es infinito y existe \(\inf(S)\), en muchos casos se dará que \([S)=\{y\in L:y\geq\inf(S)\}\) o que \([S)=\{y\in L:y>\inf(S)\}\), pero no necesariamente esto sucederá siempre. Por ejemplo:
adhocprefix-adhocsufix Sea \(\mathbf{L}=(\mathcal{P}(\mathbf{N}),\cup,\cap)\) y sea \(S=\{\mathbf{N}-\{n\}:n\in\mathbf{N}\}\). Es fácil ver que \(\inf(S)=\emptyset\) y que \([S)=\{A\in\mathcal{P}(\mathbf{N}):\mathbf{N}-A\) es finito\(\}\) por lo cual no se da que \([S)=\{y\in L:y\geq\inf(S)\}\) o que \([S)=\{y\in L:y>\inf(S)\}\)
En general, si \((L,\mathsf{s},\mathsf{i},0,1)\) es un reticulado acotado, diremos que \(F\) es un filtro de \((L,\mathsf{s},\mathsf{i},0,1)\) cuando \(F\) sea un filtro de \((L,\mathsf{s},\mathsf{i})\). Lo mismo sucederá con el concepto de filtro de un reticulado complementado \((L,\mathsf{s},\mathsf{i},^{c},0,1)\). También hablaremos del filtro generado por \(S\) en \((L,\mathsf{s},\mathsf{i},0,1)\), etc.
Sea \((P,\leq)\) un poset. Un subconjunto \(C\subseteq P\) será llamado una cadena si para cada \(x,y\in C\), se tiene que \(x\leq y\) o \(y\leq x\). Por ejemplo
adhocprefix(E1)adhocsufix \(\{1,10,40,600\}\) y \(\{2^{n}:n\in\mathbf{N}\}\) son cadenas del poset \((\mathbf{N},|)\)
adhocprefix(E2)adhocsufix \(\{-3,5,2\}\) y el intervalo \([2,3]\) son cadenas del poset \((\mathbf{R},\leq)\). De hecho todo subconjunto de \(\mathbf{R}\) es una cadena de \((\mathbf{R},\leq)\)
adhocprefix(E3)adhocsufix \(C=\{[0,n]:n\in\mathbf{N}\}\) es una cadena del poset \((\mathcal{P}(\mathbf{R}),\subseteq)\). Nótese que cada elemento de \(C\) es un conjunto (i.e. un intervalo).
Es importante notar que las cadenas pueden ser infinitas y que dada una cadena infinita \(C\) puede no existir una infinitupla \((c_{1},c_{2},...)\) tal que \(C=\{c_{n}:n\in\mathbf{N}\}\). Este es el caso de la cadena \([0,1]\) del poset \((\mathbf{R},\leq)\), ya que el bien conocido argumento diagonal de Cantor nos dice que no existe una manera de enumerar los elementos del intervalo \([0,1]\). Esto nos obliga a pensar con cierta madurez a las cadenas y no caer en la falacia de pensar que sus elementos forman necesariamente una "filita discreta".
También es importante para entender la prueba del Teorema del Filtro Primo que viene a continuación, imaginar las cadenas de posets que sus elementos son conjuntos y su orden es la inclusión, es decir dichas cadenas serán un conjunto de conjuntos \(C\) con la propiedad que dados dos cualesquiera elementos de \(C\) siempre alguno contiene al otro. Un ejemplo de este tipo de cadenas es dado en (E3). Otro ejemplo:
adhocprefix(E4)adhocsufix Sea \(\mathcal{F}=\{F:F\) es un filtro del reticulado terna \((\mathbf{N},mcm,mcd)\}\). Notar que dado \(n\in\mathbf{N}\), el conjunto \(\{x\in\mathbf{N}:n|x\}\) es un filtro de \((\mathbf{N},mcm,mcd)\}\). Ya que \(\mathcal{F}\) es no vacío tenemos que \((\mathcal{F},\subseteq)\) es un poset. Entonces \[C=\{\{x\in\mathbf{N}:n|x\}:n\text{ es potencia de }2\}\] es una cadena de \((\mathcal{F},\subseteq)\).
El siguiente resultado es una herramienta fundamental en el álgebra moderna.
5.28 (Lema de Zorn). Sea \((P,\leq)\) un poset y supongamos cada cadena de \((P,\leq)\) tiene al menos una cota superior. Entonces hay un elemento maximal en \((P,\leq)\).
Obviamente en cada poset con universo finito hay al menos un elemento maximal. O sea que el Lema de Zorn es interesante para el caso en que \(P\) es un conjunto infinito. Un argumento para creer en la veracidad del lema podría ser el siguiente razonamiento por el absurdo:
Supongamos que \((P,\leq)\) es un poset en el cual cada cadena tiene al menos una cota superior y supongamos además que no hay elementos maximales en \((P,\leq)\). Tomemos \(x_{0}\in P\) un elemento cualquiera. Ya que \(x_{0}\) no es maximal, hay un \(x_{1}\in P\) tal que \(x_{0}<x_{1}\). Iterando esta idea vemos que debe haber elementos \(x_{2},x_{3},...\) tales que: \[x_{0}<x_{1}<x_{2}<x_{3}<\cdots\] Pero \(\{x_{0},x_{1},x_{2},x_{3},...\}\) es una cadena por lo cual hay al menos una cota superior de ella en \((P,\leq)\). Sea \(y_{0}\) una de tales cotas. Ya que \(y_{0}\) no es maximal, hay un \(y_{1}\) tal que \(y_{0}<y_{1}\). Iterando esta idea vemos que debe haber elementos \(y_{2},y_{3},...\) tales que: \[x_{0}<x_{1}<x_{2}<x_{3}<\cdots<y_{0}<y_{1}<y_{2}<y_{3}<\cdots\] Pero \(\{x_{0},x_{1},x_{2},x_{3},...,y_{0},y_{1},y_{2},y_{3},...\}\) es una cadena por lo cual hay al menos una cota superior de ella en \((P,\leq)\). Esto nos permite seguir agrandando la cadena usando la misma idea usada recién lo cual muestra que tenemos un procedimiento abstracto constructivo que nos permite ir agrandando indefinidamente nuestra cadena. Esto huele a absurdo!
De todas maneras para dar una prueba formal del Lema de Zorn es necesario madurar algunos conceptos para poder escribir en forma precisa el argumento antes descripto. Esto no lo haremos en el apunte.
Un filtro \(F\) de un reticulado terna \((L,\mathsf{s},\mathsf{i})\) será llamado primo cuando se cumplan:
adhocprefix(1)adhocsufix \(F\neq L\)
adhocprefix(2)adhocsufix para cada \(x,y\in L\), si \(x\;\mathsf{s\;}y\in F\text{ entonces }x\in F\) o \(y\in F\).
Algunos ejemplos:
adhocprefix(E1)adhocsufix Todo filtro de \((\mathbf{R},\max,\min)\), distinto de \(\mathbf{R}\), es primo (justificar)
adhocprefix(E2)adhocsufix Sea \(B=\{X\subseteq\omega:X\) es finito o \(\omega-X\) es finito\(\}\). Como vimos anteriormente \(B\) es cerrado bajo las operaciones \(\cup\) y \(\cap\). Sea \(P=\{X\subseteq\omega:\omega-X\) es finito\(\}\). Entonces \(P\) es un filtro primo de \((B,\cup,\cap)\).
5.3 (Teorema del Filtro Primo). Sea \((L,\mathsf{s},\mathsf{i})\) un reticulado terna distributivo y \(F\) un filtro. Supongamos \(x_{0}\in L-F\). Entonces hay un filtro primo \(P\) tal que \(x_{0}\notin P\) y \(F\subseteq P\).
Proof. Sea \[\mathcal{F}=\{F_{1}:F_{1}\text{ es un filtro, }x_{0}\notin F_{1}\text{ y }F\subseteq F_{1}\}.\] Nótese que \(\mathcal{F}\neq\emptyset\), por lo cual \((\mathcal{F},\subseteq)\) es un poset. Veamos que cada cadena en \((\mathcal{F},\subseteq)\) tiene una cota superior. Sea \(C\) una cadena. Si \(C=\emptyset\), entonces cualquier elemento de \(\mathcal{F}\) es cota de \(C\). Supongamos entonces \(C\neq\emptyset\). Sea \[G=\{x:x\in F_{1}\text{, para algún }F_{1}\in C\}.\] Veamos que \(G\) es un filtro. Es claro que \(G\) es no vacío. Supongamos que \(x,y\in G\). Sean \(F_{1},F_{2}\in\mathcal{F}\) tales que \(x\in F_{1}\) y \(y\in F_{2}\). Si \(F_{1}\subseteq F_{2}\), entonces ya que \(F_{2}\) es un filtro tenemos que \(x\;\mathsf{i\;}y\in F_{2}\subseteq G\). Si \(F_{2}\subseteq F_{1}\), entonces tenemos que \(x\;\mathsf{i\;}y\in F_{1}\subseteq G\). Ya que \(C\) es una cadena, tenemos que siempre \(x\;\mathsf{i\;}y\in G\). En forma análoga se prueba la propiedad restante por lo cual tenemos que \(G\) es un filtro. Además \(x_{0}\notin G\), por lo que \(G\in\mathcal{F}\) es cota superior de \(C\). Por el lema de Zorn, \((\mathcal{F},\subseteq)\) tiene un elemento maximal \(P\). Veamos que \(P\) es un filtro primo. Supongamos \(x\;\mathsf{s\;}y\in P\) y \(x,y\notin P\). Nótese que \([P\cup\{x\})\) es un filtro el cual contiene propiamente a \(P\). Entonces ya que \(P\) es un elemento maximal de \((\mathcal{F},\subseteq)\), tenemos que \(x_{0}\in[P\cup\{x\})\). Análogamente tenemos que \(x_{0}\in[P\cup\{y\})\). Ya que \(x_{0}\in[P\cup\{x\})\), tenemos que hay elementos \(p_{1},...,p_{n}\in P\), tales que \[x_{0}\geq p_{1}\;\mathsf{i\;}...\;\mathsf{i\;}p_{n}\;\mathsf{i\;}x\] (se deja como ejercicio justificar esto). Ya que \(x_{0}\in[P\cup\{y\})\), tenemos que hay elementos \(q_{1},...,q_{m}\in P\), tales que \[x_{0}\geq q_{1}\;\mathsf{i\;}...\;\mathsf{i\;}q_{m}\;\mathsf{i\;}y\] Si llamamos \(p\) al siguiente elemento de \(P\) \[p_{1}\;\mathsf{i\;}...\;\mathsf{i\;}p_{n}\;\mathsf{i\;}q_{1}\;\mathsf{i\;}...\;\mathsf{i\;}q_{m}\] tenemos que \[\begin{aligned} x_{0} & \geq p\;\mathsf{i\;}x\\ x_{0} & \geq p\;\mathsf{i\;}y \end{aligned}\] Se tiene entonces que \(x_{0}\geq(p\;\mathsf{i\;}x)\;\mathsf{s\;}(p\;\mathsf{i\;}y)=p\;\mathsf{i\;}(x\;\mathsf{s\;}y)\in P\), lo cual es absurdo ya que \(x_{0}\notin P\).
5.2. Sea \((L,\mathsf{s},\mathsf{i},0,1)\) un reticulado acotado distributivo. Si \(\emptyset\neq S\subseteq L\) es tal que \(s_{1}\;\mathsf{i\;}s_{2}\;\mathsf{i\;}...\;\mathsf{i\;}s_{n}\neq0\), para cada \(s_{1},...,s_{n}\in S\), entonces hay un filtro primo que contiene a \(S\).
Proof. Nótese que \([S)\neq L\) por lo cual se puede aplicar el Teorema del filtro primo.
5.29. Sea \((B,\mathsf{s},\mathsf{i},^{c},0,1)\) un álgebra de Boole. Entonces para un filtro \(F\subsetneq B\) las siguientes son equivalentes:
adhocprefix(1)adhocsufix \(F\) es primo
adhocprefix(2)adhocsufix \(x\in F\) o \(x^{c}\in F\), para cada \(x\in B\).
Proof. (1)\(\Rightarrow\)(2). Ya que \(x\;\mathsf{s\;}x^{c}=1\in F\), (2) se cumple si \(F\) es primo.
(2)\(\Rightarrow\)(1). Ya sabemos por hipótesis que \(F\) es un filtro y que \(F\neq B\). Supongamos que \(x\;\mathsf{s\;}y\in F\) y que \(x\not\in F\). Entonces por (2), \(x^{c}\in F\) y por lo tanto tenemos que \[y\geq x^{c}\;\mathsf{i\;}y=(x^{c}\;\mathsf{i\;}x)\;\mathsf{s\;}(x^{c}\;\mathsf{i\;}y)=x^{c}\;\mathsf{i\;}(x\;\mathsf{s\;}y)\in F,\] lo cual dice que \(y\in F\).
Necesitaremos el siguiente lema.
5.30. Sea \((B,\mathsf{s},\mathsf{i},^{c},0,1)\) un álgebra de Boole. Supongamos que \(b\neq0\) y \(a=\inf(A)\), con \(A\subseteq B\). Entonces si \(b\;\mathsf{i\;}a=0\), existe un \(e\in A\) tal que \(b\;\mathsf{i\;}e^{c}\neq0\).
Proof. Supongamos que para cada \(e\in A\), tengamos que \(b\;\mathsf{i\;}e^{c}=0\). Entonces tenemos que para cada \(e\in A\), \[b=b\;\mathsf{i\;}(e\;\mathsf{s\;}e^{c})=(b\;\mathsf{i\;}e)\;\mathsf{s\;}(b\;\mathsf{i\;}e^{c})=b\;\mathsf{i\;}e,\] lo cual nos dice que \(b\) es cota inferior de \(A\). Pero entonces \(b\leq a\), por lo cual \(b=b\;\mathsf{i\;}a=0\), contradiciendo la hipótesis.
Es claro que si \(P\) es un filtro primo de un álgebra de Boole \((B,\mathsf{s},\mathsf{i},^{c},0,1)\), entonces cualquiera sea el conjunto finito \(S\) contenido en \(P\), se tiene que \(\inf(S)\in P\). Cuando tomamos un subconjunto \(S\subseteq P\) el cual es infinito, la cosa cambia sustancialmente. Primero cabe destacar que puede suceder que \(S\) no tenga ínfimo en \((B,\mathsf{s},\mathsf{i},^{c},0,1)\). Pero también puede pasar que \(S\) tenga ínfimo pero que \(\inf(S)\) no pertenezca a \(P\). Por ejemplo, si tomamos el álgebra de Boole \((B,\cup,\cap,^{c},\emptyset,\omega)\), donde \[B=\{X\subseteq\omega:X\text{ es finito o }\omega-X\text{ es finito}\}\] podemos observar que \[P=\{X\subseteq\omega:\omega-X\text{ es finito}\}\] es un filtro primo y que \[S=\{\omega-\{n\}:n\in\omega\}\] esta contenido en \(P\) pero \(\inf(S)=\emptyset\) no pertenece a \(P\).
El siguiente teorema será clave en nuestra prueba del Teorema de Completitud de la lógica de primer orden.
5.4 (Teorema de Rasiowa y Sikorski). Sea \((B,\mathsf{s},\mathsf{i},^{c},0,1)\) un álgebra de Boole. Sea \(a\in B\), \(a\neq0\). Supongamos que \((A_{1},A_{2},...)\) es una infinitupla de subconjuntos de \(B\) tal que existe \(\inf(A_{j})\), para cada \(j=1,2....\) Entonces hay un filtro primo \(P\) el cual cumple:
adhocprefix(a)adhocsufix \(a\in P\)
adhocprefix(b)adhocsufix \(P\supseteq A_{j}\Rightarrow P\ni\inf(A_{j})\), para cada \(j=1,2,....\)
Proof. Sean \(a_{j}=\inf(A_{j})\), \(j=1,2,...\). Construiremos inductivamente una infinitupla \((b_{0},b_{1},...)\) de elementos de \(B\) tal que:
adhocprefix(1)adhocsufix \(b_{0}=a\)
adhocprefix(2)adhocsufix \(b_{0}\;\mathsf{i\;}\)...\(\;\mathsf{i\;}b_{n}\neq0\), para cada \(n\geq0\)
adhocprefix(3)adhocsufix \(b_{j}=a_{j}\) o \(b_{j}^{c}\in A_{j}\), para cada \(j\geq1\).
Definamos \(b_{0}=a\). Supongamos ya definimos \(b_{0},...,b_{n}\), veamos como definir \(b_{n+1}\). Si \((b_{0}\;\mathsf{i\;}...\;\mathsf{i\;}b_{n})\;\mathsf{i\;}a_{n+1}\neq0\), entonces definamos \(b_{n+1}=a_{n+1}\). Si \((b_{0}\;\mathsf{i\;}...\;\mathsf{i\;}b_{n})\;\mathsf{i\;}a_{n+1}=0\), entonces por el lema anterior, tenemos que hay un \(e\in A_{n+1}\) tal que \((b_{0}\;\mathsf{i\;}...\;\mathsf{i\;}b_{n})\;\mathsf{i\;}e^{c}\neq0\), lo cual nos permite definir \(b_{n+1}=e^{c}\).
Usando (2) se puede probar que el conjunto \(S=\{b_{0},b_{1},...\}\) satisface la hipótesis del primer corolario del Teorema del filtro primo, por lo cual hay un filtro primo \(P\) tal que \(\{b_{0},b_{1},...\}\subseteq P\). Es claro que \(a\in P\) y es fácil chequear usando (3) que \(P\) satisface la propiedad (b).
Cerramos la sección con una convención notacional que se usara mas que nada en los ejercicios y la tómbola.
Convención Notacional: Nótese que hemos definido distintos tipos de estructuras (i.e. posets, reticulados ternas, etc) y en todas ellas su primera coordenada es llamada el universo de dicha estructura. En general usaremos letras mayúsculas en bold para denotar una estructura dada y en tal caso usaremos la convención de que su correspondiente mayúscula en itálica denotará el universo de dicha estructura. Por ejemplo si decimos "sea \(\mathbf{L}\) un reticulado acotado", entonces ya queda implícita la información de que denotaremos con \(L\) al universo de \(\mathbf{L}\). Además debería quedar claro que en tal caso \(\mathbf{L}\) es una 5-upla. También si \(\mathbf{L}^{\prime}\) denota una estructura, \(L^{\prime}\) denotará su universo. Similarmente si \(\mathbf{\tilde{L}}\) denota una estructura, \(\tilde{L}\) denotará su universo, etc. Nótese que entonces, si escribimos "Sea \(F:\mathbf{L}\rightarrow\mathbf{L}^{\prime}\) es un homomorfismo de reticulados complementados", estaremos suponiendo que \(\mathbf{L}\) y \(\mathbf{L}^{\prime}\) son reticulados complementados (i.e. ciertas 6-uplas) y que \(F\) es una función de \(L\) en \(L^{\prime}\) la cual es un homomorfismo de \(\mathbf{L}\) en \(\mathbf{L}^{\prime}\). Aquí hay que tener cuidado ya que \(D_{F}\) es \(L\) y no \(\mathbf{L}\) lo cual seria imposible ya que \(\mathbf{L}\) no es un conjunto! También nótese que si \(\mathbf{L}\) denota un reticulado acotado y \(\theta\) es una congruencia de \(\mathbf{L}\), entonces \(\mathbf{L}/\theta\) denotará el cociente de \(\mathbf{L}\) sobre \(\theta\), a saber cierto reticulado acotado cuyo universo es \(L/\theta\). Es decir que \(Ti(\mathbf{L}/\theta)=5\mathrm{-UPLA}\) y \(Ti(L/\theta)=\mathrm{CONJUNTO}\)