5.7 Teoremas del filtro primo y de Rasiowa Sikorski

Un filtro de un reticulado terna \((L,\mathsf{s},\mathsf{i})\) sera un subconjunto \(F\subseteq L\) tal que:

1. adhocprefix(1)adhocsufix \(F\neq\emptyset\)

2. adhocprefix(2)adhocsufix \(x,y\in F\Rightarrow x\;\mathsf{i\;}y\in F\)

3. adhocprefix(3)adhocsufix \(x\in F\) y \(x\leq y\Rightarrow 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\}\]

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\). 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 dara que \([S)=\{y\in L:y\geq\inf S\}\) o que \([S)=\{y\in L:y>\inf S\}\), pero no necesariamente esto sucedera siempre. Por ejemplo:

1. adhocprefix-adhocsufix Sea \(\mathbf{L}=(\mathcal{P}(\mathbf{N}),\cup,\cap)\) y sea \(S=\{\mathbf{N}-\{n\}:n\in\mathbf{N}\}\). Es facil 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 sucedera con el concepto de filtro de un reticulado complementado \((L,\mathsf{s},\mathsf{i},^{c},0,1)\)

Sea \((P,\leq)\) un poset. Un subconjunto \(C\subseteq P\) sera llamado una cadena si para cada \(x,y\in C\), se tiene que \(x\leq y\) o \(y\leq x\). Por ejemplo

1. adhocprefix(E1)adhocsufix \(\{1,10,40,600\}\) y \(\{2^{n}:n\in\mathbf{N}\}\) son cadenas del poset \((\mathbf{N},|)\)

2. 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)\)

3. adhocprefix(E3)adhocsufix \(C=\{[0,n]:n\in\mathbf{N}\}\) es una cadena del poset \((\mathcal{P}(\mathbf{R}),\subseteq)\). Notese 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".

Tambien es importante para entender la prueba del Teorema del Filtro Primo que viene a continuacion, imaginar las cadenas de posets que sus elementos son conjuntos y su orden es la inclusion, es decir dichas cadenas seran 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:

1. 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 vacio 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 algebra moderna.

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 podria 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 ademas 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 usada recien 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 agunos 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})\) sera llamado primo cuando se cumplan:

1. adhocprefix(1)adhocsufix \(F\neq L\)

2. adhocprefix(2)adhocsufix \(x\;\mathsf{s\;}y\in F\Rightarrow x\in F\) o \(y\in F\).

Algunos ejemplos:

1. adhocprefixE1adhocsufix Todo filtro de \((\mathbf{R},\max,\min)\), distinto de \(\mathbf{R}\), es primo (justificar)

2. adhocprefixE2adhocsufix 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)\).

Proof. Sea \[\mathcal{F}=\{F_{1}:F_{1}\text{ es un filtro, }x_{0}\notin F_{1}\text{ y }F\subseteq F_{1}\}.\] Notese 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 algun }F_{1}\in C\}.\] Veamos que \(G\) es un filtro. Es claro que \(G\) es no vacio. 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 analoga se prueba la propiedad restante por lo cual tenemos que \(G\) es un filtro. Ademas \(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\). Notese 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\})\). Analogamente 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\).  

Proof. Notese que \([S)\neq L\) por lo cual se puede aplicar el Teorema del filtro primo.  

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 hipotesis 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.

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 hipotesis.  

Es claro que si \(P\) es un filtro primo de un algebra 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 infimo en \((B,\mathsf{s},\mathsf{i},^{c},0,1)\). Pero tambien puede pasar que \(S\) tenga infimo pero que \(\inf S\) no pertenesca a \(P\). Por ejemplo, si tomamos el algebra 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 sera clave en nuestra prueba del teorema de completitud de la logica de primer orden.

Proof. Sean \(a_{j}=\inf(A_{j})\), \(j=1,2,...\). Construiremos inductivamente una infinitupla \((b_{0},b_{1},...)\) de elementos de \(B\) tal que:

1. adhocprefix(1)adhocsufix \(b_{0}=x\)

2. adhocprefix(2)adhocsufix \(b_{0}\;\mathsf{i\;}\)...\(\;\mathsf{i\;}b_{n}\neq0\), para cada \(n\geq0\)

3. adhocprefix(3)adhocsufix \(b_{j}=a_{j}\) o \(b_{j}^{c}\in A_{j}\), para cada \(j\geq1\).

Definamos \(b_{0}=x\). 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 hipotesis 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 \(x\in P\) y es facil chequear usando (3) que \(P\) satisface la propiedad (b).  

Cerramos la seccion con una convencion notacional que se usara mas que nada en los ejercicios y la tombola.

1. adhocprefixConvencion notacional:adhocsufix Notese 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 mayusculas en bold para denotar una estructura dada y en tal caso usaremos la convension de que su correspondiente mayuscula en italica denotara el universo de dicha estructura. Por ejemplo si decimos "sea \(\mathbf{L}\) un reticulado acotado", entonces ya queda implicita la informacion de que denotaremos con \(L\) al universo de \(\mathbf{L}\). Ademas deberia quedar claro que en tal caso \(\mathbf{L}\) es una 5-upla. Tambien si \(\mathbf{L}^{\prime}\) denota una estructura, \(L^{\prime}\) denotara su universo. Similarmente si \(\mathbf{\tilde{L}}\) denota una estructura, \(\tilde{L}\) denotara su universo, etc. Notese 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 funcion de \(L\) en \(L^{\prime}\) la cual es un homomorfismo de \(\mathbf{L}\) en \(\mathbf{L}^{\prime}\). Aqui 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! Tambien notese que si \(\mathbf{L}\) denota un reticulado acotado y \(\theta\) es una congruencia de \(\mathbf{L}\), entonces \(\mathbf{L}/\theta\) denotara 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}\)