1. Toda variable es un t´ermino.
2. Si t1 y t2 son t´erminos, entonces (t1 = t2) y (t2 ? t2) son f´ormulas. 3. Si a y ß son f´ormulas, entonces ¬a, (a ? ß), (a?ß), (a?ß), (a ? ß) son f´ormulas. 4. Si a es una f´ormula y X es una variable entonces ?Xa y ?Xa son f´ormulas. 5. Si a es una f´ormula y X es una variable, entonces X | a es un t´ermino.
Estas reglas permiten determinar sin ambig¨uedad alguna si una cadena de signos es una expresi´on (un t´ermino o una f´ormula) o si, por el contrario, es no expresiva. Por ejemplo, tenemos que las variables x e y son t´erminos por 1), luego (x = y) e (y = x) son f´ormulas por 2), luego ((x = y) ? (y = x)) es una f´ormula por 3) (y no porque signi?ca
3
algo, como dec´iamos antes). En cambio, la cadena ? = (? xy no es una expresi´on, pues la regla 4) exige que detr´as de un ? vaya una variable, y nunca un =. As´i pues, podemos a?rmar que la cadena
?X((X ? A) ? (X ? B))
tiene signi?cado: a?rma que todos los conjuntos (sea esto lo que sea) que pertenecen (sea esto lo que sea) al conjunto (slqs) A pertenecen (slqs) tambi´en al conjunto (slqs) B. Y si alg´un malicioso nos cuestiona que podamos atribuir un signi?cado a una a?rmaci´on sin atribuir un signi?cado concreto a sus signos, tenemos a nuestra disposici´on una respuesta t´ecnicamente impecable: cuando decimos que tiene signi?cado s´olo queremos decir que es una f´ormula en el sentido siguiente: X, A y B son t´erminos por la regla 1), (X ? A) y (X ? B) son f´ormulas por la regla 2), ((X ? A) ? (X ? B)) es una f´ormula por la regla 3) y ?X((X ? A) ? (X ? B)) es una f´ormula por la regla 4). Lo cual es absolutamente objetivo y no admite discusi´on. Yendo un poco m´as lejos podr´iamos atribuir un signi?cado a algunos signos, y esta- blecer que ? signi?ca “y”, ¬ signi?ca “no”, etc., es decir, podr´iamos convertir esto en a?rmaciones precisas y rigurosas. Es cuestionable si tiene sentido decir que = signi?ca “igual” o si esto es no decir nada. En cualquier caso, los signos siguientes se resisten a toda precisi´on operativa: ?, ?, ? . Como no disponemos de ninguna de?nici´on expl´icita de conjunto, no podemos explicar qu´e signi?ca “para todo conjunto se cumple que” ni “existe un conjunto tal que”. En esencia, la posibilidad de un uso puramente formal de estos tres signos nos dispensa de de?nir lo que es un conjunto y lo que es la pertenencia entre conjuntos. Ahora podr´iamos de?nir formalmente lo que es un razonamiento l´ogico aceptable, tal y como hizo (bien) el propio Frege, pero no merece la pena, pues los problemas de fundamentaci´on de la matem´atica no est´an ah´i. Despu´es de precisar meticulosamente qu´e se puede deducir y qu´e no de unas premisas dadas llegar´iamos a la noci´on intuitiva de deducci´on l´ogica que todos tenemos. A partir de aqu´i somos libres de introducir tantas de?niciones como consideremos oportuno. T´ecnicamente, una de?nici´on no es m´as que una abreviatura. Por ejemplo, podemos de?nir (antes incluso de dar ning´un axioma) la noci´on de inclusi´on de conjuntos:
A ? B = ?X((X ? A) ? (X ? B)).
Las tres rayas = indican que el miembro izquierdo es una abreviatura del miembro derecho (no una mera equivalencia l´ogica). Te´oricamente, cada vez que un matem´atico escribe A ? B podr´ia sustituir esto por el miembro derecho. T´ecnicamente ? no es un signo del lenguaje de la teor´ia de conjuntos, sino una mera abreviatura de una f´ormula que (como todas las f´ormulas) no contiene m´as que los signos admisibles que hemos indicado al principio.
4
Para terminar comentaremos que en la pr´actica relajaremos ligeramente la sintaxis impuesta por la de?nici´on de t´ermino y f´ormula, siempre que esto no lleve a confusi´on. Por ejemplo, podemos escribir ?X ? A(X = U ? X = V ), entendiendo que con ello nos referimos a la f´ormula ?X((X ? A) ? ((X = U) ? (X = V ))). 3 La Axiom´atica de Zermelo / / ´ / ´ El primer axioma de la teor´ia de conjuntos de Zermelo es el axioma de extensionalidad:
?XY (?U(U ? X ? U ? Y ) ? X = Y ).
A?rma que si dos conjuntos tienen los mismos elementos entonces son iguales (el rec´iproco es un caso particular de un principio l´ogico: si X = Y entonces todo lo que vale para X vale para Y ). Seg´un hemos comentado en la introducci´on, el problema que presenta la fundamen- taci´on de la teor´ia de conjuntos es que no podemos permitirnos el lujo de postular que toda propiedad de?ne un conjunto. En su lugar, la teor´ia de Zermelo postula la existencia de conjuntos de?nidos por ciertas propiedades inofensivas (no como X ? X). Tal vez el conjunto m´as inofensivo de todos sea el que nos da el axioma del conjunto vac´io:
?X?U U ? X.
Este axioma a?rma la existencia de un conjunto que no tiene elementos. Dicho con- junto es unico, pues dos conjuntos sin elementos tendr´ian los mismos elementos. Esto nos permite de?nir el t´ermino Ø = X | ?U U ? X. Seg´un coment´abamos en la secci´on anterior, Ø no es un signo del lenguaje de la teor´ia de conjuntos, sino una abreviatura de un t´ermino que puede eliminarse de cualquier expresi´on sin m´as que sustituirla por el miembro derecho de la de?nici´on. No volveremos a insistir en ello. En particular tenemos que existen conjuntos. El axioma del par implica entre otras cosas que existen in?nitos conjuntos:
?XY ?Z?U(U ? Z ? (U = X ? U = Y )).
Este axioma a?rma que, dados dos conjuntos X e Y , existe un tercer conjunto Z cuyos elementos son exactamente X e Y . Dicho Z es unico, pues si Z y Z cumplen lo mismo entonces ambos tienen los mismos elementos, luego son iguales. Esto nos permite de?nir el t´ermino {X,Y } = Z | ?U(U ? Z ? (U = X ? U = Y )). Nunca hemos dicho que X e Y deban ser distintos. Abreviaremos {X} = {X,X}, de modo que, para todo conjunto X tenemos justi?cada la existencia de un conjunto
5
´ {X} cuyo unico elemento es X. En particular todo conjunto pertenece a otro conjunto. Tambi´en vemos que existen in?nitos conjuntos, como Ø, {Ø}, {Ø,{Ø}}, {{Ø}}, etc. ´ ´ Notemos que los axiomas vistos hasta aqu´i no garantizan que, dados X, Y , Z, exista un conjunto {X,Y,Z} que los tenga a ellos solos como elementos. Para ello necesitamos el axioma de la uni´on:
?X?Y ?U(U ? Y ? ?V (U ? V ? V ? X)).
Este axioma a?rma que, dado un conjunto X, existe un conjunto Y cuyos elementos son los elementos de los elementos de X. De nuevo es unico, pues dos conjuntos que cumplieran lo mismo tendr´ian los mismos elementos. Esto nos permite de?nir el t´ermino
V = Y | ?U(U ? Y ? ?V (U ? V ? V ? X)). V ?X
Ahora podemos demostrar el teorema siguiente:
Teorema ?XY ?Z?U(U ? Z ? U ? X ? U ? Y ). Demostracion: Hemos de probar que, dados dos conjuntos X e Y , existe un con- junto Z que contiene a los elementos de ambos. Basta tomar Z = V. ´ V ?{X,Y }
El conjunto Z dado por el teorema anterior es unico por el axioma de extensionalidad, luego podemos de?nir el t´ermino
X ? Y = Z | ?U(U ? Z ? U ? X ? U ? Y ).
Se comprueba inmediatamente que la uni´on es asociativa, por lo que podemos de?nir uniones X1 ? ··· ? Xn sin necesidad de indicar los par´entesis. En particular podemos de?nir {X1,…,Xn} = {X1} ? ··· ? {Xn}, y es inmediato que el conjunto as´i de?nido tiene como elementos a X1,…,Xn. Otro conjunto cuya existencia necesita ser postulada es el conjunto de partes, dado, naturalmente, por el axioma de partes:
?X?Y ?U(U ? Y ? U ? X).
Recordemos que la f´ormula U ? X est´a de?nida en la secci´on anterior (esta de?nici´on no requiere ning´un axioma). Nuevamente, el axioma de extensionalidad garantiza que el
6
´ ´ / / conjunto Y cuya existencia postula este axioma es unico, por lo que podemos de?nir el t´ermino PX = Y | ?U(U ? Y ? U ? X). La teor´ia de conjuntos de Zermelo tiene in?nitos axiomas. Ello se debe a que el axioma siguiente no es un axioma, sino un esquema axiom´atico, es decir, una regla que determina in?nitas f´ormulas que la teor´ia acepta como axiomas (si bien en cada demostraci´on en concreto s´olo se podr´a usar un n´umero ?nito de casos particulares de dicha regla.) Se trata del esquema axiom´atico de especi?caci´on:
Para cada f´ormula f(U) del lenguaje de la teor´ia de conjuntos (tal vez con m´as variables libres, adem´as de X), la f´ormula siguiente es un axioma:
?X?Y ?U(U ? Y ? U ? X ? f(U)).
Una vez m´as, X es unico, luego podemos de?nir
{Y ? X | f(U)} = Y | ?U(U ? Y ? U ? X ? f(U)).
Observemos c´omo la noci´on de “propiedad” queda completamente precisada al susti- tuirla por la de “f´ormula”. Por ejemplo, si aplicamos el esquema de especi?caci´on a un conjunto X y a la f´ormula f(U) = U ? Y obtenemos la existencia del conjunto
X n Y = {U ? X | U ? Y },
que tiene la propiedad de contener exactamente a los elementos comunes de X e Y . Si aplicamos el esquema de especi?caci´on a un conjunto X y a f(U) = U ? Y obte- nemos el conjunto X Y = {U ? X | U ? Y }. En resumen, hasta aqu´i tenemos probada la existencia de Ø, X ? Y, X n Y, X Y, X ? Y. Supondremos conocidas las numerosas relaciones entre estos conceptos, pues todas se demuestran ahora f´acilmente. De?nimos (X,Y ) = {{X},{X,Y }}. Una simple rutina justi?ca el teorema siguiente:
Teorema ?XY ZW((X,Y ) = (Z,W) ? X = Z ? Y = W). Vamos a demostrar que, dados dos conjuntos A y B, existe un conjunto C cuyos elementos son los pares ordenados con primera componente en A y segunda componente en B. Formalmente:
7
Teorema ?AB?C?U(U ? C ? ?X ? A?Y ? B U = (X,Y )). ´ Demostracion: Notemos que no podemos aplicar el esquema de especi?caci´on con f(U) = ?X ? A?Y ? B U = (X,Y ) y considerar C = {U | ?X ? A?Y ? B U = (X,Y )}, pues necesitamos exigir que U pertenezca a un conjunto dado de antemano. El problema es encontrar un conjunto Z de modo que al exigir U ? Z no nos dejemos fuera ning´un par. Para ello observamos que si X ? A e Y ? B entonces {X} ? A ? A?B y {X,Y } ? A?B, luego {X},{X,Y } ? P(A ? B), luego
(X,Y ) = {{X},{X,Y }} ? PP(A ? B). Por consiguiente concluimos que el conjunto C = {U ? PP(A ? B) | ?X ? A?Y ? B U = (X,Y )} cumple el teorema. El axioma de extensionalidad garantiza que el conjunto dado por el teorema anterior ´ es unico, luego podemos de?nir A × B = C | ?U(U ? C ? ?X ? A?Y ? B U = (X,Y )). A su vez esto nos permite de?nir, para cada f´ormula f(X,Y ), el t´ermino {(X,Y ) ? A × B | f(X,Y )} = {U ? A × B | ?X ? A?Y ? B(U = (X,Y ) ? f(X,Y ))}. A partir de aqu´ipodemos de?nir y demostrar f´acilmente todos los conceptos y teoremas relacionados con relaciones y funciones. Los supondremos conocidos. ´ El ultimo axioma de la teor´ia de Zermelo postula la existencia de un conjunto in?nito (sabemos que existen in?nitos conjuntos, pero no conjuntos in?nitos). Para introducirlo adecuadamente conviene de?nir X = X ? {X}. El axioma de in?nitud a?rma que ?Y (Ø ? Y ? ?X ? Y X ? Y ). Ahora conviene introducir una notaci´on alternativa: 0 = Ø, es decir, usaremos in- distintamente 0 o Ø como abreviaturas para el conjunto vac´io. As´i, un conjunto Y en las condiciones que postula el axioma de in?nitud contiene necesariamente a 0, pero en- tonces contiene tambi´en a 1 = 0 = Ø ? {Ø} = {0}, pero entonces contiene tambi´en a 2 = 1 = 1?{1} = {0,1}, y tambi´en a 3 = 2 = {0,1,2}, etc. En suma, Y es un conjunto in?nito. Podemos precisar a´un m´as. De?namos Y inductivo = Ø ? Y ? ?X ? Y X ? Y. 8
En estos t´erminos, el axioma de in?nitud a?rma que existe un conjunto inductivo Y . Podemos construir entonces el conjunto N = {U ? Y | ?Z ? Y (Z inductivo ? U ? Z)}, es decir, N es el conjunto de los elementos de Y que pertenecen a todos los subconjuntos inductivos de Y . Vamos a probar que N es inductivo y que est´a contenido en todo conjunto inductivo. Para probar que N es inductivo demostramos en primer lugar que 0 ? N. En efecto, 0 ? Y y si Z es un subconjunto inductivo de Y entonces 0 ? Z por de?nici´on de conjunto inductivo. Esto prueba que 0 ? N. Supongamos ahora que X ? N, y hemos de probar que X ? N. Por de?nici´on de N tenemos que X ? Y . Como Y es inductivo, X ? Y . Ahora hemos de ver que si Z ? Y es inductivo, entonces X ? Z. Ahora bien, por de?nici´on de N tenemos que X ? Z, y por de?nici´on de conjunto inductivo X ? Z como quer´iamos probar. Ahora supongamos que I es un conjunto inductivo cualquiera (no necesariamente contenido en Y ), y vamos a probar que N ? I. En efecto, se demuestra inmediatamente que Z = InY es un conjunto inductivo contenido en Y , luego por de?nici´on de N tenemos que N ? I n Y ? I. Con esto hemos demostrado el teorema siguiente: Teorema ?N(N inductivo ? ?Y (Y inductivo ? N ? Y )). ´ Este conjunto N es claramente unico, pues si N y N cumplen lo mismo, entonces N ? N (porque N es inductivo) y N ? N (porque N lo es). Esto nos permite de?nir N = N | (N inductivo ? ?Y (Y inductivo ? N ? Y )). En otras palabras, el conjunto de los n´umeros naturales se de?ne como el menor conjunto inductivo. A partir de aqu´i es f´acil demostrar los axiomas de Peano: Teorema (Axiomas de Peano) 1. 0 ? N, 2. ?n ? N n ? N, 3. ¬?n ? N 0 = n , 4. ?mn ? N(m = n ? m = n), 5. ?X ? N((0 ? X ? ?m ? X m ? X) ? X = N). No entraremos en los detalles de la de?nici´on de la suma y el producto de n´umeros naturales. A partir de aqu´i pueden de?nirse de la forma habitual todos los conceptos matem´aticos (n´umeros enteros, racionales, reales, complejos, sucesiones, n-tuplas, etc. 9
4 Variantes sobre la teor´ia de Zermelo ˜ ˜ ´ ˜ La teor´ia de Zermelo presenta ciertas lagunas a la hora de obtener resultados m´as profundos en teor´ia de conjuntos, concretamente al trabajar con ordinales y cardinales in?nitos. Fraenkel arregl´o el problema anadiendo el esquema axiom´atico del reemplazo:
Para toda f´ormula f(X,Y ), tal vez con m´as variables libres, la f´ormula si- guiente es un axioma:
?A(?X ? A?Y Z(f(X,Y ) ? f(X,Z) ? Y = Z) ? ?B?Y (Y ? B ? ?X ? Af(X,Y )). Este esquema a?rma que si la f´ormula f(X,Y ) de?ne una funci´on sobre un subconjunto de A, es decir, si a cada X ? A le podemos asociar a lo sumo un conjunto Y que cumpla f(X,Y ), entonces existe un conjunto B que contiene a todos los conjuntos Y que podemos asignar de este modo a los elementos de A. En otros t´erminos, si llamamos C = {X ? A | ?Y f(X,Y )} y llamamos
F = {(X,Y ) | X ? A ? f(X,Y )},
entonces F es una aplicaci´on y el conjunto B cuya existencia postula el esquema de reemplazo es simplemente B = F[C]. El problema es que la existencia de F no puede probarse a partir de los axiomas de Zermelo. Una vez tenemos asegurada la existencia del conjunto B, entonces s´i podemos de?nir
F = {(X,Y ) ? A × B | f(X,Y )},
pero sin tener a B la de?nici´on anterior no es correcta, pues no indicamos ning´un conjunto del cual F sea un subconjunto, y no podemos aplicar el esquema de especi?caci´on. A partir del esquema del reemplazo puede demostrarse el esquema de especi?caci´on, por lo que la teor´ia de conjuntos de Zermelo-Fraenkel (ZF) es la que resulta de sustituir la especi?caci´on por el reemplazo. A los axiomas de ZF puede anadirse el axioma de regularidad de von Neumann:
?X?Y (Y ? X ? Y n X = Ø).
Este axioma no es necesario para demostrar ning´un teorema importante, pero proh´ibe la existencia de “monstruos” tales como un conjunto X = {X}, o un par de conjuntos X = {Y }, Y = {X} o cosas peores. Garantiza, por el contrario, que todo conjunto puede construirse a partir del conjunto vac´io en una cantidad ?nita o in?nita de pasos (obs´ervese, por ejemplo, c´omo hemos construido el conjunto de los n´umeros naturales a partir del conjunto vac´io). Por ultimo, podemos anadir el axioma de elecci´on: ?X?F(F : X -? V ?X V ? ?U ? X(U = Ø ? F(U) ? U)). 10
Este axioma a?rma que para toda familia X de conjuntos existe una “funci´on de elecci´on” F que asigna a cada uno de ellos U uno de sus elementos (siempre que U = Ø). Al contrario que el axioma de regularidad, este axioma es crucial para la demostraci´on de muchos resultados importantes, como la existencia de bases en espacios vectoriales, la existencia de clausura algebraica, el teorema de Tychono? sobre la compacidad de un producto de espacios topol´ogicos, el teorema de Hann-Banach sobre extensi´on de funcionales lineales, etc.). 5 Clases / / La axiom´atica de Zermelo (o de Zermelo-Fraenkel) evita las paradojas de la teor´ia de conjuntos negando la existencia de los conjuntos que las provocan. Por ejemplo:
Teorema ¬?R?X(X ? R ? X ? X). La prueba de este teorema es trivial: si existiera un R en estas condiciones tendr´iamos la consabida contradicci´on. La diferencia con la teor´ia de Frege es que ´esta postulaba la existencia de R, mientras que los axiomas de ZF no lo hacen. Como consecuencia tenemos lo siguiente:
Teorema ¬?V ?X X ? V . Es decir, no existe ning´un conjunto que contenga a todos los conjuntos. La demos- traci´on es la siguiente: Si existiera V podr´iamos de?nir
R = {X ? V | X ? X},
por el esquema de especi?caci´on. Pero este conjunto contradice al teorema anterior.
M´as en general, no podemos de?nir el complementario de un conjunto X, es decir, no existe un conjunto X cuyos elementos sean los conjuntos que no pertenecen a X. Si exis- tiera, entonces el conjunto V = X ?X contendr´ia a todos los conjuntos, en contradicci´on con el teorema anterior. Georg Cantor desarroll´o una teor´ia de cardinales in?nitos que extiende a la bien cono- cida teor´ia de cardinales ?nitos. Seg´un esta teor´ia, la sucesi´on de los cardinales contin´ua m´as all´a de los n´umeros naturales: 0, 1, 2, … ?0, ?1, ?2, … ´ de modo que a cada conjunto X se le puede asignar un unico cardinal |X| en esta sucesi´on con la propiedad de que |X| = |Y | si y s´olo si existe una aplicaci´on F : X -? Y biyectiva. Otro ejemplo cl´asico de “conjunto que no existe” es el conjunto de todos los cardinales, es decir, si suponemos la existencia de tal conjunto llegamos a una contradicci´on.
11
De estos hechos se desprende una consecuencia ?los´o?ca muy interesante: si estamos dispuestos a admitir que la palabra “conjunto” signi?ca algo, hemos de tener bien claro que no signi?ca “colecci´on de objetos”. En efecto, admitamos que los axiomas de la teor´ia de conjuntos (y, con ellos, sus teoremas) hablan de unos objetos llamados conjuntos. Entonces, la colecci´on de todos esos conjuntos es sin duda una colecci´on de objetos, pero no se corresponde con ninguno de esos conjuntos. As´i pues, podr´iamos admitir que existen unos objetos llamados conjuntos que satisfacen los axiomas de ZF, y que cada uno de ellos puede verse como una colecci´on de objetos, a saber, aquellos otros conjuntos que le pertenecen seg´un el (presunto) signi?cado de la relaci´on de pertenencia; pero lo que es inadmisible es postular el rec´iproco, es decir, que toda colecci´on de conjuntos constituya la extensi´on de un conjunto, es decir, que haya un conjunto que los tenga a ellos por elementos y s´olo a ellos. Por ejemplo, si en alg´un sentido existen los conjuntos, la colecci´on de todos aquellos conjuntos que no cumplen la de?nici´on de n´umero natural es ciertamente una colecci´on de conjuntos, pero no hay ning´un conjunto que los tenga a ellos y s´olo a ellos por elementos (ser´ia el complementario de N, y ya hemos demostrado que no existe). ´ Sin embargo, el hecho de que no exista el conjunto de todos los conjuntos, o el conjunto de todos los cardinales, o el complementario del conjunto de los n´umeros naturales no es obst´aculo para que podamos hablar de ellos. El unico arte que ello requiere es que tengamos bien claro lo que hacemos. Concretamente, podemos hacer lo siguiente: Para cada f´ormula f(X), convendremos en que la notaci´on C = {X | f(X)} (que leeremos “C es la clase de todos los conjuntos que cumplen f(X)”) sig- ni?car´a simplemente que X ? C es una forma alternativa de escribir f(X). De este modo, una clase es esencialmente lo mismo que una f´ormula. Por ejemplo, podemos de?nir V = {X | X = X}, de modo que V es la clase de todos los conjuntos. Sabemos que V no existe, en el sentido de que no existe ning´un conjunto que contenga a todos los conjuntos, pero podemos usar V en el sentido limitado en virtud del cual X ? V es una forma c´omoda de expresar que X = X, es decir, que X es un conjunto cualquiera. Igualmente, podemos de?nir V × V = {X | ?Y Z X = (Y,Z)}, de modo que V × V es la clase de todos los pares ordenados. Es f´acil probar que no existe ning´un conjunto que contenga a todos los pares ordenados (ejercicio), pero no hay ning´un problema en escribir X ? V × V como abreviatura de ?Y Z X = (Y,Z). En realidad podemos usar clases en un contexto m´as general que las meras f´ormulas de tipo X ? C. Por ejemplo, pese a que ni existe V ni existe V ×V , podemos interpretar la a?rmaci´on V ×V ? V como una f´ormula v´alida en ZF. Basta recordar la de?nici´on de la inclusi´on, seg´un la cual V × V ? V es equivalente a ?X(X ? V × V ? X ? V ). 12
| Página siguiente |