5.7 Teoremas del filtro primo y de Rasiowa Sikorski

Un filtro de un reticulado terna (L,s,i) sera un subconjunto F⊆L tal que:

1. (1) F≠∅

2. (2) x,y∈F⇒xiy∈F

3. (3) x∈F y x≤y⇒y∈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⊆L, denotemos con [S) el siguiente conjunto {y∈L:y≥s1i...isn, para algunos s1,...,sn∈S, n≥1}

Proof. Ya que S⊆[S), tenemos que [S)≠∅. Claramente [S) cumple la propiedad (3). Veamos cumple la (2). Si y≥s1is2i...isn y z≥t1it2i...itm, con s1,s2,...,sn, t1,t2,...,tm∈S, entonces yiz≥s1is2i...isnit1it2i...itm lo cual prueba (2).  

Llamaremos a [S) el filtro generado por S en (L,s,i). Cuando S es finito, ya que existe infS, es claro que [S)={y∈L:y≥infS}. Cuando S es infinito y existe infS, en muchos casos se dara que [S)={y∈L:y≥infS} o que [S)={y∈L:y>infS}, pero no necesariamente esto sucedera siempre. Por ejemplo:

1. - Sea L=(P(N),∪,∩) y sea S={N−{n}:n∈N}. Es facil ver que infS=∅ y que [S)={A∈P(N):N−A es finito} por lo cual no se da que [S)={y∈L:y≥infS} o que [S)={y∈L:y>infS}

En general, si (L,s,i,0,1) es un reticulado acotado, diremos que F es un filtro de (L,s,i,0,1) cuando F sea un filtro de (L,s,i). Lo mismo sucedera con el concepto de filtro de un reticulado complementado (L,s,i,c,0,1). Tambien hablaremos del filtro generado po S en (L,s,i,0,1), etc.

Sea (P,≤) un poset. Un subconjunto C⊆P sera llamado una cadena si para cada x,y∈C, se tiene que x≤y o y≤x. Por ejemplo

1. (E1) {1,10,40,600} y {2n:n∈N} son cadenas del poset (N,|)

2. (E2) {−3,5,2} y el intervalo [2,3] son cadenas del poset (R,≤). De hecho todo subconjunto de R es una cadena de (R,≤)

3. (E3) C={[0,n]:n∈N} es una cadena del poset (P(R),⊆). 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 (c1,c2,...) tal que C={cn:n∈N}. Este es el caso de la cadena [0,1] del poset (R,≤), 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. (E4) Sea F={F:F es un filtro del reticulado terna (N,mcm,mcd)}. Notar que dado n∈N, el conjunto {x∈N:n|x} es un filtro de (N,mcm,mcd)}. Ya que F es no vacio tenemos que (F,⊆) es un poset. Entonces C={{x∈N:n|x}:n es potencia de 2} es una cadena de (F,⊆).

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,≤) es un poset en el cual cada cadena tiene al menos una cota superior y supongamos ademas que no hay elementos maximales en (P,≤). Tomemos x0∈P un elemento cualquiera. Ya que x0 no es maximal, hay un x1∈P tal que x0<x1. Iterando esta idea vemos que debe haber elementos x2,x3,... tales que: x0<x1<x2<x3<⋯ Pero {x0,x1,x2,x3,...} es una cadena por lo cual hay al menos una cota superior de ella en (P,≤). Sea y0 una de tales cotas. Ya que y0 no es maximal, hay un y1 tal que y0<y1. Iterando esta idea vemos que debe haber elementos y2,y3,... tales que: x0<x1<x2<x3<⋯<y0<y1<y2<y3<⋯ Pero {x0,x1,x2,x3,...,y0,y1,y2,y3,...} es una cadena por lo cual hay al menos una cota superior de ella en (P,≤). 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,s,i) sera llamado primo cuando se cumplan:

1. (1) F≠L

2. (2) xsy∈F⇒x∈F o y∈F.

Algunos ejemplos:

1. E1 Todo filtro de (R,max,min), distinto de R, es primo (justificar)

2. E2 Sea B={X⊆ω:X es finito o ω−X es finito}. Como vimos anteriormente B es cerrado bajo las operaciones ∪ y ∩. Sea P={X⊆ω:ω−X es finito}. Entonces P es un filtro primo de (B,∪,∩).

Proof. Sea F={F1:F1 es un filtro, x0∉F1 y F⊆F1}. Notese que F≠∅, por lo cual (F,⊆) es un poset. Veamos que cada cadena en (F,⊆) tiene una cota superior. Sea C una cadena. Si C=∅, entonces cualquier elemento de F es cota de C. Supongamos entonces C≠∅. Sea G={x:x∈F1, para algun F1∈C}. Veamos que G es un filtro. Es claro que G es no vacio. Supongamos que x,y∈G. Sean F1,F2∈F tales que x∈F1 y y∈F2. Si F1⊆F2, entonces ya que F2 es un filtro tenemos que xiy∈F2⊆G. Si F2⊆F1, entonces tenemos que xiy∈F1⊆G. Ya que C es una cadena, tenemos que siempre xiy∈G. En forma analoga se prueba la propiedad restante por lo cual tenemos que G es un filtro. Ademas x0∉G, por lo que G∈F es cota superior de C. Por el lema de Zorn, (F,⊆) tiene un elemento maximal P. Veamos que P es un filtro primo. Supongamos xsy∈P y x,y∉P. Notese que [P∪{x}) es un filtro el cual contiene propiamente a P. Entonces ya que P es un elemento maximal de (F,⊆), tenemos que x0∈[P∪{x}). Analogamente tenemos que x0∈[P∪{y}). Ya que x0∈[P∪{x}), tenemos que hay elementos p1,...,pn∈P, tales que x0≥p1i...ipnix (se deja como ejercicio justificar esto). Ya que x0∈[P∪{y}), tenemos que hay elementos q1,...,qm∈P, tales que x0≥q1i...iqmiy Si llamamos p al siguiente elemento de P p1i...ipniq1i...iqm tenemos que x0≥pixx0≥piy Se tiene entonces que x0≥(pix)s(piy)=pi(xsy)∈P, lo cual es absurdo ya que x0∉P.  

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

Proof. (1)⇒(2). Ya que xsxc=1∈F, (2) se cumple si F es primo.

(2)⇒(1). Ya sabemos por hipotesis que F es un filtro y que F≠B. Supongamos que xsy∈F y que x∉F. Entonces por (2), xc∈F y por lo tanto tenemos que y≥xciy=(xcix)s(xciy)=xci(xsy)∈F, lo cual dice que y∈F.  

Necesitaremos el siguiente lema.

Proof. Supongamos que para cada e∈A, tengamos que biec=0. Entonces tenemos que para cada e∈A, b=bi(esec)=(bie)s(biec)=bie, lo cual nos dice que b es cota inferior de A. Pero entonces b≤a, por lo cual b=bia=0, contradiciendo la hipotesis.  

Es claro que si P es un filtro primo de un algebra de Boole (B,s,i,c,0,1), entonces cualquiera sea el conjunto finito S contenido en P, se tiene que infS∈P. Cuando tomamos un subconjunto S⊆P el cual es infinito, la cosa cambia sustancialmente. Primero cabe destacar que puede suceder que S no tenga infimo en (B,s,i,c,0,1). Pero tambien puede pasar que S tenga infimo pero que infS no pertenesca a P. Por ejemplo, si tomamos el algebra de Boole (B,∪,∩,c,∅,ω), donde B={X⊆ω:X es finito o ω−X es finito} podemos observar que P={X⊆ω:ω−X es finito} es un filtro primo y que S={ω−{n}:n∈ω} esta contenido en P pero infS=∅ no pertenece a P.

El siguiente teorema sera clave en nuestra prueba del Teorema de Completitud de la logica de primer orden.

Proof. Sean aj=inf(Aj), j=1,2,.... Construiremos inductivamente una infinitupla (b0,b1,...) de elementos de B tal que:

1. (1) b0=a

2. (2) b0i...ibn≠0, para cada n≥0

3. (3) bj=aj o bcj∈Aj, para cada j≥1.

Definamos b0=a. Supongamos ya definimos b0,...,bn, veamos como definir bn+1. Si (b0i...ibn)ian+1≠0, entonces definamos bn+1=an+1. Si (b0i...ibn)ian+1=0, entonces por el lema anterior, tenemos que hay un e∈An+1 tal que (b0i...ibn)iec≠0, lo cual nos permite definir bn+1=ec.

Usando (2) se puede probar que el conjunto S={b0,b1,...} satisface la hipotesis del primer corolario del Teorema del filtro primo, por lo cual hay un filtro primo P tal que {b0,b1,...}⊆P. Es claro que a∈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. Convencion notacional: 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 L un reticulado acotado", entonces ya queda implicita la informacion de que denotaremos con L al universo de L. Ademas deberia quedar claro que en tal caso L es una 5-upla. Tambien si L′ denota una estructura, L′ denotara su universo. Similarmente si ˜L denota una estructura, ˜L denotara su universo, etc. Notese que entonces, si escribimos "Sea F:L→L′ es un homomorfismo de reticulados complementados", estaremos suponiendo que L y L′ son reticulados complementados (i.e. ciertas 6-uplas) y que F es una funcion de L en L′ la cual es un homomorfismo de L en L′. Aqui hay que tener cuidado ya que DF es L y no L lo cual seria imposible ya que L no es un conjunto! Tambien notese que si L denota un reticulado acotado y θ es una congruencia de L, entonces L/θ denotara el cociente de L sobre θ, a saber cierto reticulado acotado cuyo universo es L/θ. Es decir que Ti(L/θ)=5−UPLA y Ti(L/θ)=CONJUNTO